Initiation à l'arithmétique/PGCD

Algorithme d’Euclide : une méthode pour trouver le PGCD

Le mot algorithme vient du mathématicien arabe du Modèle:S Al-Khwarizmi.

Euclide est un savant grec du Modèle:S avant J.C., auteur des fameux Éléments.

Un algorithme est une procédure automatisée qui permet de trouver un résultat « sans réfléchir ». Par exemple, quand on pose une opération, on applique un algorithme.

L'algorithme d'Euclide est une méthode pour trouver le PGCD de deux nombres entiers par divisions euclidiennes successives.

Propriété de transmission du PGCD

Modèle:Exemple

Algorithme d’Euclide : exemple

On veut le PGCD de $702$ et $273$.

On effectue les divisions successives :

$702=273\times 2+156$ ;

$273=156\times 1+117$ ;

$156=117\times 1+39$ ;

$117=39\times 3+0$.

Le dernier reste non nul est $39$ donc $\mathrm{pgcd}(702,273)=39$.

Applications du PGCD

Nombres premiers entre eux

Exemple

25 et 36 sont premiers entre eux (bien qu’aucun des deux ne soit premier !) car leur PGCD vaut 1.

Contre-exemple

24 et 36 ne sont pas premiers entre eux, car leur PGCD vaut 12 (leurs diviseurs communs sont donc : 1, 2, 3, 4, 6, 12).