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 :

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 :

ao ^ bo = a1 ^ b1 = a2 ^ b2 = a3 ^ b3 = ... avec :

Par construction, la suite (an) = {ao, a1, a2, ...} est strictement décroissante et positive. On procède à au plus (a - 1) étapes (auquel cas aa-1 = 1). au cours de des étapes :

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

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 :

<FORM ACTION="" METHOD=POST>
<CENTER>
<INPUT TYPE=button NAME=Bouton VALUE="Lancer le programme" onclick="go()">
</CENTER>
</FORM>

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 :

A 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 :


© Serge Mehl - www.chronomath.com