PGCD et algorithme d'Euclide

Le PGCD de deux entiers est le plus grand entier qui les divise tous les deux. Le décomposer en facteurs premiers marche, mais c'est lent. Euclide a trouvé bien mieux, il y a vingt-trois siècles.

L'idée de l'algorithme

Tout repose sur une observation simple. Si a = b q + r (division euclidienne de a par b), alors :

PGCD(a , b) = PGCD(b , r)

En effet, tout diviseur commun à a et b divise r = a - bq ; et réciproquement, tout diviseur commun à b et r divise a = bq + r. Les deux paires ont donc exactement les mêmes diviseurs communs.

Or r est strictement plus petit que b : on remplace un problème par un problème plus petit, jusqu'à tomber sur un reste nul.

L'algorithme en action

PGCD(1071 , 462) :

   1071 = 2 × 462 + 147
    462 = 3 × 147 +  21
    147 = 7 ×  21 +   0     <- reste nul, on s'arrête

   PGCD = 21     (le dernier reste NON nul)

Trois divisions. La décomposition en facteurs premiers aurait demandé de factoriser 1071 et 462 — beaucoup plus long, et impraticable sur de grands nombres.

Pourquoi c'est rapide

Le nombre de divisions est de l'ordre du nombre de chiffres des entiers, pas de leur taille. Le pire cas se produit pour deux termes consécutifs de la suite de Fibonacci — un résultat démontré par Lamé en 1844, et la première analyse de complexité de l'histoire.

deux nombres de 1000 chiffres  ->  quelques milliers de divisions

C'est pourquoi l'algorithme d'Euclide reste, aujourd'hui encore, une brique de base de tous les systèmes cryptographiques.

Les propriétés utiles

PGCD(a , 0) = a
PGCD(a , b) = PGCD(b , a)
PGCD(ka , kb) = k × PGCD(a , b)
PGCD(a , b) × PPCM(a , b) = a × b

Entiers premiers entre eux

Deux entiers a et b sont premiers entre eux lorsque PGCD(a , b) = 1.

Attention : cela ne signifie pas qu'ils sont premiers. 8 et 9 sont premiers entre eux et aucun des deux n'est premier — ils n'ont simplement aucun facteur en commun.

PGCD(8 , 9)  = 1     premiers entre eux
PGCD(12 , 18) = 6    non

Rendre une fraction irréductible, c'est précisément diviser numérateur et dénominateur par leur PGCD :

   1071        1071/21        51
  ------  =  ----------  =  ------
    462        462/21         22

En résumé

• PGCD(a , b) = PGCD(b , r) où r est le reste de a par b.
• L'algorithme d'Euclide enchaîne les divisions jusqu'à un reste nul ; le PGCD est le dernier reste non nul.
• Son coût dépend du nombre de chiffres, pas de la taille des entiers.
• PGCD × PPCM = a × b.
• a et b sont premiers entre eux si PGCD(a , b) = 1 — sans être premiers eux-mêmes.