Remontée de l’algorithme d’Euclide

On dispose de deux nombres entiers positifs premiers entre eux a > b, et on cherche un couple de nombres entiers (u,v) qui satisfasse l’équation :

au+ bv = 1.

1 Petit rappel sur la division euclidienne

Par division euclidienne, on désigne la division usuelle des entiers, telle qu’on l’apprend en primaire, non poussée. Par exemple, la division euclidienne de 255 par 7 donne :

| 2 5 5 -7--- 4 5 |3 6 3 |

c’est à dire

255 = 7 × 36+ 3.

Le nombre 36 est le quotient de la division, et 3 en est le reste.

2 Remontée de l’algorithme d’Euclide

Pour deux entiers a > b premiers entre eux, on note a₀ = a et a₁ = b, et on commence par effectuer la division euclidienne de a₀ par a₁,

a = a b + a . 0 1 1 2

Le reste de cette division est noté a₂, et son quotient b₁.

En effectuant les divisions euclidiennes successives de a_n par a_n+1, on construit ainsi deux suites (a_n)_n et (b_n)_n d’entiers :

La suite (a_n) est celle des restes successifs des divisions euclidiennes : a_n+2 est le reste de la division euclidienne de a_n par a_n+1.
La suite (b_n) est celle des quotients des divisions euclidiennes successives : b_n+1 est le quotient entier de la division de a_n par a_n+1.

an = an+1bn+1 + an+2.

On peut montrer qu’en procédant ainsi, on arrive toujours à a_k = 1 pour un certain indice k. A ce moment là, on arrête l’algorithme, et on va pouvoir le “remonter”.

Pour remonter l’algorithme et trouver les coefficients de Bezout (u,v) dans

au+ bv = 1,

on se sert de nos deux suites en gardant en permanence a₀ = a et a₁ = b en évidence, et en cherchant les coefficients qui se trouvent devant ces deux quantités. On part de 1 = a_k = a_k-2 - b_k-1a_k-1 et on remonte dans la suite des divisions euclidiennes, exprimant les termes des deux suites en fonction des termes précédents jusqu’à n’avoir plus que 1 = a₀u + a₁v.

On y verra plus clair sur des exemples

3 Deux exemples

Soient a = a₀ = 165 et b = a₁ = 56. Alors, les divisions euclidiennes successives s’écrivent
$a0 = 2× a1 + 53 a1 = 1× 53 + 3 53 = 17× 3 + 2 3 = 1× 2 + 1.$
La remontée va s’effectuer de la façon suivante :
$1 = 3- 1× 2 1 = 3- 1× [53- 17 × 3] 1 = {a1 - 1× 53} - 1× [53 - 17× {a1 - 1× 53 }] 1 = {a1 - 1× (a0 - 2a1 )} - 1× [(a0 - 2a1 )- 17× {a1 - 1 × (a0 - 2a1)}]$ et après simplification de la dernière ligne, on obtient $1 = 56a1 - 19a0,$ donc u = -19 et v = 56.
Avec a = a₀ = 7590 et b = a₁ = 1547, on cherche à remonter l’algorithme d’Euclide suivant $a = 4× a + 1402 0 1 a1 = 1× 1402+ 145 1402 = 9 × 145+ 97 145 = 1 × 97+ 48 97 = 2 × 48+ 1,$ d’où la remontée $1 = 97- 2 × 48 1 = 97- 2 × (145- 1× 97) 1 = [1402 - 9 × 145]- 2× (145 - 1 × [1402 - 9× 145]) 1 = [1402 - 9 × {a1 - 1 × 1402}]- 2 × ({a1 - 1 × 1402} - 1× [1402- 9 × {a1 - 1× 1402}]) 1 = [(a - 4a )- 9 × {a - 1 × (a - 4a )}] 0 1 1 0 1 - 2× ({a1 - 1× (a0 - 4a1)} - 1 × [(a0 - 4a1)- 9× {a1 - 1 × (a0 - 4a1)}]),$

et on trouve finalement

1 = 32a - 157b,

donc u = 32 et v = -157.

Version pdf de ce document : cliquez ici

Retour à l'article des Mathématiques