Fiche de cours
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 euclid