C'est le plus grand commun diviseur de a et de b. On le note PGCD (a,b), ou
a ∨ b.
On a |a|Z + |b|Z = dZ.
• Algorithme d'Euclide
Si q 1 et r 1 sont le quotient et le reste de la division euclidienne de a par b, on a :
a ∨ b = b ∨ r 1 .
On recommence avec b et r 1 . Le dernier reste non nul de ce processus est le PGCD
de a et de b.
• Nombres premiers entre eux
Si PGCD (a,b) = 1, on dit que a et b sont premiers entre eux.
Soit r =
a
b
un nombre rationnel. Si d désigne le PGCD de a et de b, on a a = da
et b = db
, avec a
et b
premiers entre eux. On peut alors écrire r =
a
b · C'est la
forme irréductible de r.
2.2 ppcm
• Définition
Soit a et b deux entiers relatifs non nuls. L'ensemble des nombres de N
∗ qui sont
multiples à la fois de a et de b, admet un plus petit élément m, pour la relation
d'ordre de divisibilité.
C'est le plus petit commun multiple de a et de b. On le note PPCM (a,b), ou a ∧ b.
On a |a|Z ∩ |b|Z = mZ.
• Théorème
PGCD (a,b)× PPCM (a,b) = |a b|.
2.3 Théorème de Bézout
Pour que deux entiers relatifs non nuls a et b soient premiers entre eux, il faut, et
il suffit, qu'il existe u et v dans Z tels que :
au + bv = 1 .
On obtient u et v avec l'algorithme d'Euclide.
© Dunod – La photocopie non autorisée est un délit.
Arithmétique dans Z 45
145
Algèbre générale
9782100549245-fredon-C37-51.qxd 18/06/10 10:33 Page 145