A] Définition
1) Définition et théorème
a et b sont deux entiers naturels non nuls.
Un entier naturel qui divise a et qui divise b est appelé diviseur commun à a et b.
L'ensemble des diviseurs communs de a et b possède un plus grand élément que l'on appelle le plus grand commun diviseur de a et de b, on le note PGCD(a;b)
2) Remarque
a étant un entier naturel, l'ensemble des diviseur de a est égal à l'ensemble des diviseur de -a. On pourra étendre, la notion de PGCD à des nombres entiers relatifs. On dira par exemple que PGCD(-15;12) = PGCD(15;12) = 3.
3) propriété
Soient a et b deux entiers naturels non nuls. On a PGCD(a;b) = PGCD(b;a)
Si b divise a, on a PGCD(a;b) = b
En particulier PGCD(a;1) = 1 et PGCD(a;a) = a
B] Détermination du PGCD de deux nombres
1) Lemme d'euclide
Soient a et b deux entiers naturels non nuls.
Si a = b x q + r avec r≠0, alors PGCD(a;b) = PGCD(b;r)
2) Algorithme d'euclide
Théorème : Soient a et b deux entiers naturels non nuls. On définit la suite rn d'entier naturels de la façon suivante: ro = b; r1 est le reste de la division euclidienne de a par b.
Pour n>1 : si rn = 0 alors r(n+1) = 0
et si rn ≠ 0 alors r(n+1) est le reste de la division euclidienne de r(n-1) pa rn.
Alors il existe un entier no tel que r(no) tel que r(no) ≠ 0 et pour tout n > no , rn = 0 , on a PGCD(a;b) = r(no)
3) Conséquence
En effectuant ainsi des division euclidienne successive de a par b, puis du diviseur par le reste, le dernier reste non nul est le PGCD de a et de b. C'est l'algorithme d'euclide.
C] Ensemble des diviseurs communs à deux nombres.
Les diviseurs communs à deux entiers naturels non nuls sont les diviseur de leur PGCD.
D] Propriété du PGCD.
1) Écriture de PGCD de deux entiers comme combinaison linéaire de ces entiers.
Théorème: Si d le PGCD de deux entiers naturels a et b non nuls alors il existe des entiers relatifs u et v tels que: au + bv = d
2) PGCD(ka;kb)
Théorème: Si on multiplie deux entiers naturels a et b non nuls par un même entier naturel k non nul alors leur PGCD est multiplié par k, c'est à dire PGCD(a;b)= k PGCD(a;b)
II. Nombre premier entre eux
A] Définition.
a et b sont deux entiers relatifs non nuls, a et b sont premiers entre eux si leur PGCD est égale à 1 ou -1.
B] Théorème de Bezout et conséquences.
1) théorème: Soit a et b deux entiers relatifs non nuls. a et b sont premier entre eux équivaut à dire qu'il existe deux entiers relatifs u et v tels que: au +bv = 1.
2) Conséquences
a. Théorème 1: a et b sont des entiers relatifs non nuls et d un entier naturel non nul. d = PGCD(a;b) équivaut à dire qu'il existe des entiers non nuls a' et b' premier entre eux tels que a = da' et b = db'.
b. Théorème 2: Si un entier a est premier avec deux entiers b et c alors a est premier avec leur produit bc.
c. Théorème 3: n est un entier naturel non nul, si a et b sont deux entiers premiers entre eux alors a est premier avec b puissance n.
C] Théorème de Gauss.
Soient a et b deux entiers naturels non nuls et c un entier relatif. Si a divise bc et si a est premier avec b, alors a divise c.
Théorème 4: a et b sont deux entiers relatifs non nuls et soit n un entier naturel. Si n est divisible par deux entier a et b premier entre eux, alors n est divisible par leur produit ab.
III. PPCM
1) Définition
L'ensemble des multiples strictement positifs communs à a et b possède un plus petit élément. Ce plus petit élément est appelé "pus petit commun multiple" de a et b. On le note PPCM(a;b)
2) théorème fondamental
a et b étant deux entier naturels non nuls, on a PGCD(a;b) x PPCM(a;b) = ab
3) Conséquence
L'ensemble des multiples communs à a et b est l'ensemble des multiple de leur PPCM. Si a et b sont premier entre eux, on a PPCM(a;b) = ab
Théorème: Si on multiplie deux entiers naturels a et b non nuls par un même entier naturel k non nul alors leur PPCM est multiplier par k, c'est à dire PPCM(ka;kb) = k PPCM(a;b)
