Pré-requis :
Ensemble de nombres
Plan du cours
1. Divisibilité dans Z
2. Congruence
3. Plus grand commun diviseur
1. Divisibilité dans Z
Dans tout ce qui suit, on se place dans l'ensemble des entiers relatifs Z.
A. Diviseur
Définitions :
Soient a et b deux entiers relatifs.
On dit que a divise b, ou que a est un diviseur de b, s'il existe un entier relatif k tel que b=k×a.
On dit que b est un multiple de a, s'il existe un entier relatif k tel que b=k×a.
On note a | b. Ex : 3 est un diviseur de 18. 18 est un multiple de 3.
5 est un diviseur de -25. -25 est un multiple de 5.
Propriétés :
Soient a, b et c trois entiers relatifs.
- Si a divise b alors a divise kb pour tout k∈"Z" .
- Si a divise b et b divise c, alors a divise c.
- Si a divise b et a divise c, alors a divise kb+k'c pour tout k∈"Z" et tout k'∈"Z" .
B. Division euclidienne
Propriété :
Soient a un entier relatif et b un entier relatif non nul.
Il existe une unique manière d'écrire b sous la forme b=a×q+r telle que q∈"Z" , r∈"N" et r<|b|.Ex : 27=6×4+3
Lorsque l'on se place dans l'ensemble des entiers naturels N, on retrouve la division euclidienne vu auparavant, q étant le quotient, et r le reste.
Remarque :
Si a divise b, alors b=a×q+r avec r=0.
C. Nombres premiers
Définition :
Un nombre premier est un entier naturel qui n'admet que deux diviseurs : 1 et lui-même.
Ex : 1, 2, 3, 17 sont des nombres premiers.
Il y a une infinité de nombres premiers.
Propriété :
Soit n un entier naturel.
Si n n'est pas un nombre premier, alors il admet pour diviseur au moins un nombre premier p tel que p<√n.Décomposition en produit de facteurs premiers :
Soit n un entier naturel.
Il existe une unique manière d'écrire n sous la forme d'une décomposition de facteurs premiers :n=p_1×p_2×…×p_k
Si plusieurs de ces facteurs sont identiques, on peut écrire la décomposition avec des puissances de facteurs premiers.
Ex : 120=2^3×3×5
Corollaire :
Tout produit partiel de ces facteurs divise n.
Ex : 12=2^2×3 divise 120.
2. Congruence
A. Nombres congrus
Définition :
Soient a et b deux entiers relatifs. Soit n un entier naturel non nul.
On dit que b est congru à a modulo n, si la différence b-a est un multiple de n (si n divise b-a).