PGCD (Plus Grand Commun Diviseur)
Rappel :
Tout idéal de
est principal, donc de la forme
où
.
Si
ou
, alors
ou
.
Pour tous les entiers
et
non tous nuls, l'ensemble
est un idéal de
non réduit à
.
Définition :
Le PGCD de deux entiers
et
non tous nuls est l'unique entier
tel que
.
On le note :
.
Fondamental :
Propriétés :
Pour tous
et
entiers non tous nuls, il existe deux entiers
et
tels que
.Un entier
divise
et
si et seulement si
divise
.Pour tous
,
et
entiers non nuls :
. Pour tous
,
et
entiers non nuls :
.-
si et seulement si
,
et
. Pour tous
,
et
entiers non nuls :
.Si
est le reste de la division d'un entier
par un entier
, alors :
.
Méthode :
Calcul de
par l'algorithme d'Euclide :
On calcule le reste
de la division de
par
, puis le reste
de la division de
par
, puis le reste
de la division de
par
, ...
Le PGCD de
et
est le dernier reste non nul.
Exemple :
Exemple : Pour déterminer le PGCD de
et
, on effectue les divisions successives :
.
.
.
.
.
Le dernier reste non nul est
. Donc le PGCD de
et
est
.
Définition :
On définit le PGCD de
entiers par récurrence.
Pour tout entier
et tous les entiers
,
, ...,
non nuls :
.
