PGCD de deux entiers, 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).

 

Tu veux réviser 2x plus vite ?

Découvre les offres des Bons Profs avec :