Dans tout ce qui suit, on désigne par D(x) l'ensemble des diviseurs d'un entier x donné.

Définition

Soit a et b entiers relatifs non nuls.

Le Plus Grand Commun Diviseur (ou PGCD) de a et b est l'entier égal au plus grand élément de  D(a)D(b) .

On le note   pgcd(a,b)   ou   ab .

Propriété

Soit a et b deux entiers non tous les deux nuls, on a :

ab = |a||b|

Propriété

Soit a et b deux entiers non tous les deux nuls. Si a divise b, on a :

ab = |a|

Propriété

Soit a et b deux entiers, on a :

D(a) D(b) = D(ab)

Propriété

Soit a, b et k des entiers naturels non nuls, on a :

(ka)(kb) = k(ab)

Propriété

Soit a, b deux entiers divisibles par d. On a :

Théorème

Soit a, b, q et r des entiers, avec a 0 .

Si   a = bq + r   alors   ab = br .

Formule   Algorithme d'Euclide

Algorithme permettant de calculer le PGCD de a et b.

1) Division euclidienne de a par b : a = bq1 + r1   avec 0 r1 < b

2) Si r1 0 , division euclidienne de b par r1 : b = q2r1 + r2   avec 0 r2 < r1

3) Si r2 0 , division euclidienne de r1 par r2 : r1 = q3r2 + r3   avec 0 r2 < r1

i) ...

k) Quand on a rk = 0 , alors  pgcd(a,b) = rk-1

Remarque :

Cet algorithme aboutit toujours ! Il découle du théorème précédent. :

On a  rk = 0 , donc  rk-2 = qkrk-1 ,

donc rk-1 est un diviseur de rk-2 et on a alors   rk-2rk-1 = rk-1 .

Or, d'après le théorème précédent, on a :

ab = br1 = r1r2 = ... = rk-2rk-1 = rk-1

donc on a bien   pgcd(a,b) = rk-1 .

Dans tout ce qui suit, on désigne par M(x) l'ensemble des multiples strictement positifs d'un entier x donné.

Définition

Soit a et b entiers non nuls.

Le Plus Petit Commun Multiple (ou PPCM) de a et b est l'entier égal au plus petit élément de  M(a)M(b) . C'est donc un nombre positif.

On le note   ppcm(a,b)   ou   ab .

Théorème

pgcd(a,b) ppcm(a,b) = ab

Propriété

Soit a, b et k des entiers naturels non nuls, on a :

(ka)(kb) = k(ab)