37
F I C H E 8 – A r i t h m é t i q u e d a n s Z
© Dunod – La photocopie non autorisée est un délit.
8
Algorithme d'Euclide
Si q 1 et r 1 sont respectivement 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
(avec b = / 0) 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 (avec b
= / 0). C'est la forme irréductible de r.
• 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.
Théorème
PGCD (a,b)×PPCM (a,b) = |a b|.
• 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.
• Théorème de Gauss
Soit a, b, c trois entiers relatifs tels que a divise bc, et a premier avec b. Alors a
divise c.