PGCD par différences

ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Calcul d'un PGCD par la méthode des différences
» programme , algorithme par division euclidienne , programme sur tableur

Soit à rechercher le PGCD, noté a ^ b, de deux entiers naturels (non nuls) a et b en supposant a ≥ b . Cette méthode par différences est parfois appelée anthyphérésie ou anthyphérèse (du grec anthy = à son tour, tour à tour et aphairesis = action d'enlever, supprimer). Elle est due à Euclide, dans le livre septième de ses Éléments, proposition 2.

Plus généralement, on applique un processus à deux nombres a et b, a > b, puis par division ou soustractions successives, ayant constaté que le processus peut être itéré, ce dernier s'arrête et on tombe soit sur un résultat attendu soit sur une contradiction (usage du raisonnement par l'absurde cher à Aristote).

Anthyphérésie et irrationalité de √2 : » Fractions continues : »

Si d est un diviseur commun aux deux entiers a et b, alors d divise également a - b. Inversement si d est un diviseur commun aux deux entiers b et a - b, alors d divise a. Ainsi les diviseurs communs du couple (a,b) sont les diviseurs communs du couple (a - b, b) :

a ^ b = ( a - b) ^ b

Le PGCD de a et b est aussi celui de b et a : a ^ b = b ^ a. Ainsi, s'il s'avère que a - b est inférieur à b, on continuera les calculs en écrivant :

a ^ b = b ^ ( a - b)

Par ailleurs, il est clair que si a = b, alors a ^ b = a. D'où l'algorithme illustré par l'exemple ci-dessous :

Exemples :

24 ^ 18 = 6 ^ 18

18 ^ 6 = 12 ^ 6

12 ^ 6 = 6 ^ 6

Le PGCD de 24 et 18 est donc 6

Discussion de l'algorithme :

! Notons que la méthode est à éviter si a est "proche" de b... : cela risque de durer longtemps ! On préférera alors l'algorithme d'Euclide par division qui lui est équivalent mais plus rapide.

➔ Mais arrivera-t-on toujours à la forme a ^ a ? si, au départ a = b, alors c'est terminé, on a bien la forme a ^ a. Si maintenant a > b, écrivons notre suite de calculs sous la forme :

a_o ^ b_o = a₁ ^ b₁ = a₂ ^ b₂ = a₃ ^ b₃ = ... avec :

a_o = a , b_o = b

a_n = Max {b_n-1 , a_n-1 - b_n-1}

b_n = Min {b_n-1 , a_n-1 - b_n-1}

b_n≤ a_n

Par construction, la suite (a_n) = {a_o, a₁, a₂, ...} est strictement décroissante et positive. On procède à au plus (a - 1) étapes (auquel cas a_a-1 = 1). au cours de des étapes :

ou bien, on a obtenu a_n = b_n = k pour un certain n < a - 1 : auquel cas le pgcd est k (éventuellement 1, les nombres a et b sont alors premiers entre eux :

22 ^ 17 = 17 ^ 5 = 12 ^ 5 = 6 ^ 5 = 5 ^ 1 = 4 ^ 1 = 3 ^ 1 = 2 ^1 = 1

ou bien, on est arrivé à a_a-1 = 1, sans égalité de a_i et b_i pour tout i (sinon on aurait arrêté) et par suite b_a-1 est non nul mais vérifiant toujours b_a-1 ≤ a_a-1, donc b_a-1 = 1. C'est dire que le pgcd est 1 ^ 1 = 1 : les nombres a et b sont premiers entre eux.

➔ Plutôt que de prendre, dans les calculs, le max et le min comme décrit ci-dessus, il est plus simple, lorsque a > b, d'écrire : a ^ b = b ^ |a - b|. On remarquera que l'on part de a < b, on retrouvera le cas a > b à la première itération. Exemple : 18 ^ 24 = 24 ^ 6.

Programme JavaScript de calcul d'un PGCD par différences :

➔ Code HTML du formulaire permettant de lancer les calculs à la demande :

Exemples d'exécution :

➔ Remarquer que le programme reste valide si a < b vu la présence de la valeur absolue. Ce programme peut calculer le PPMC de a et b (plus petit multiple commun, dit aussi PPCM...). Il suffit d'appliquer la formule "bien connue" :

ab = PGDC(a,b) × PPMC(a,b)

<SCRIPT LANGUAGE=JavaScript>
function go()
{
a=24 ; a=prompt("a = ",a)
if (a==null) {return} else {a=eval(a)}
b=18 ; b=prompt("b = ",b)
if (b==null) {return} else {b=eval(b)}
x=a ; y=b;
r=Math.abs(a-b) r = |a - b|
wdow=open("","calculs","height=450,width=450","scrollbars=yes")
wdow.document.write("<PRE>")

while (r > 0)
{
wdow.document.writeln("a = "+a+"\tb = "+b+"\tdiff. = "+r) \t sert à tabuler pour une bonne présentation
a=b ; b=r;
r=Math.abs(a-b)
}
wdow.document.writeln("")
wdow.document.writeln("PGCD("+x+" , "+y+") = "+a)
return
} </SCRIPT>

! Les limites de la machine...

Dans la recherche d'un PGCD de grands nombres, on dépasse rapidement la capacité de traitement de l'ordinateur : voici un cas difficile (à éviter en classe...) dont il est fait état dans la revue pédagogique Puissance 324, n°7, Ac. de Créteil) :

a = 12345678910111213 b = 10000000000000007

Aucun programme ne donne la bonne solution car nous dépassons ici 15 chiffres significatifs. La méthode par différences doit être faite à la main ou avec une calculatrice de forte capacité de traitement (TI-92, ...) ou encore avec de puissants logiciels (Dérive, Mathematica, Mapple, ...) jusqu'à n'avoir que 15 chiffres significatifs au plus. On obtient successivement :

12345678910111213 , 10000000000000007
10000000000000007 , 2345678910111206
7654321089888801 , 2345678910111206
7654321089888801 , 5308642179777595
5308642179777595 , 2345678910111206
...
123458528109526 , 8280992447

➔ à ce niveau, on obtient immédiatement par l'algorithme d'Euclide : PGCD(123458528109526 , 8280992447) = 113. On peut aussi vérifier que :

a = 12345678910111213 = 113 × 109253795664701 , b = 113 × 88495575221239

et que PGCD(109253795664701 , 88495575221239) = 1

PGCD par division euclidienne : » Nombres premiers : »