PGCD de 2 entiers et algorithme d'Euclide
PGCD de 2 entiers et algorithme d'Euclide
PGCD de 2 entiers et algorithme d’Euclide
Définition
On considère deux entiers $a$ et $b$.
On appelle alors PGCD de $a$ et de $b$ le plus grand des diviseurs communs à $a$ et à $b$.
Exemple
Si l’on veut déterminer le PGCD de $8$ et de $12$. Il faut chercher les diviseurs de ces deux entiers
$8$ a pour diviseurs : $\{1;2;4;8\}$
$12$ a pour diviseurs : $\{1;2;3;4;6;12\}$
On en déduit que le plus grand diviseur commun à $8$ et $12$ est $4$.
Algorithme d’Euclide
Lorsqu’on manipule des entiers relativement grands, comme 1015 et 714 par exemple, on peut trouver leur PGCD en appliquant l’algorithme d’Euclide.
L’algorithme d’Euclide fonctionne de la manière suivante :
- Si $a$ est un entier alors $PGCD(a,0)=a$
- Si $a$ et sont deux entiers (avec $a>b$) et si $r$ est le reste de la division euclidienne de $a$ par $b$ alors $PGCD(a;b)=PGCD(b;r)$
On commence par écrire la division euclidienne du plus grand des deux entiers par le plus petit.
Ici supposons que $a>b$ :
On écrit a sous la forme : $a = b\times q + r$ où r est le reste de la division euclidienne de $a$ par $b$ et $q$ le quotient.
Ensuite, on écrit la division euclidienne de $b$ par $r$. On répète cette étape avec les restes successifs.
Lorsqu’on l’on obtient un reste non nul, il suffit alors de regarder la valeur du dernier reste non nul : c’est le $PGCD$ de $a$ et de $b$.
Exemple :
Appliquons cette méthode à 1015 et 714 :
$1015 = 714 \times 1 + 301$
$714 = 301 \times 2 + 112$
$301 = 112 \times 2 + 77$
$112 = 77 \times 1 + 35$
$77 = 35 \times 2 +7$
$35 = 7\times 5 + 0$
Le PGCD de $1015$ et $714$ est donc $7$ (dernier reste non nul).