Algorithme d'Euclide et théorème de Bezout

I) Présentation

1) Objectif

  Etant donnés deux entiers non nuls a et b , on calcule un couple ( x , y ) d'entiers relatifs tels que a x + by = pgcd ( a , b ) .

L'existence d'un tel couple solution s'appelle le théorème de Bezout (parfois de Bachet-Bezout).
On utilisera l'algotithme d'Euclide pour le calcul du pgcd de deux entiers.

def pgcd(a, b):
    """ Calcul itératif du pgcd par l'algorithme d'Euclide"""
    while b > 0:
        a, b = b, a % b
    return a

2) Un exemple, deux façons de mener le calcul

Avec a = 105 et b =16, l'algorithme d'Euclide s'écrit:

105 = 6×16 + 9
16 = 1×9 + 7
9 = 1×7 + 2
7 = 3×2 + 1
2 = 2×1 + 0
Donc d = pgcd(105, 16) = 1

a) Première méthode (Descente de l'algorithme d'Euclide)

On écrit à chaque étape le reste comme combinaison linéaire de a et b, en exploitant les deux étapes précédentes

9 = 105 - 6×16
7 = 16 - 1×9 = 16 -1×(105 - 6×16) = 7×16 - 1×105
2 = 9 - 1×7 = (105 - 6×16) - (7×16 - 1×105) = 2×105 - 13× 16
1 = 7 - 3×2 = (7×16 - 1×105) - 3×(2×105 - 13× 16) =  46×16 - 7×105
Le couple ( x , y ) = ( - 7 , 46 ) est un couple solution de l'équation 105 x + 16 y = 1 .

b) Seconde méthode (Remontée de l'algorithme d'Euclide)

On peut aussi “remonter” l'algorithme depuis la fin, en exploitant l'étape précédente:

1
= 7 - 3×2
= 7 - 3×(9 - 1×7) = 4×7 - 3×9
= 4×(16 - 1×9) - 3×9 = 4×16 - 7×9
= 4×16 - 7×(105 - 6×16) = 46×16 - 7×105
Le couple ( x , y ) = ( - 7 , 46 ) est un couple solution de l'équation 105 x + 16 y = 1 .

Q1) Calculer des deux façons un couple ( x , y ) solution de l'équation 55 x + 32 y = 1

II) Algorithmes

1) Préparation des algorithmes

Notons a n et b n les valeurs des paramètres a et b après la n ième itération de l'algorithme .
On a: { a 0 = a b 0 = b et { a n + 1 = b n b n + 1 = a n % b n pour n N , tant que b n > 0 .

Notons, si b n > 0 , (1): a n = b n q n + r n la division euclidienne de a n par b n .

Pour n N ,     r n = a n % b n = b n + 1 = a n + 2   et q n = ( a n // b n ) = ( a n // a n + 1 ) , alors  l'égalité (1) s'écrit    a n = a n + 1 q n + a n + 2 .

La suite ( a n ) vérifie la relation de récurrence double (2): a n + 2 = a n - a n + 1 q n , valable pour n N , (tant que a n + 1 0 ), avec q n = ( a n // a n + 1 ) .

On a donc: a 0 = a et a 1 = b 0 = b et n N , a n + 2 = a n - a n + 1 ( a n // a n + 1 ) , (tant que a n + 1 0 ).
Le pgcd de a et b est le dernier terme non nul a N (avec N 1 ) de cette suite ( a n ) .

En effet, la première fois que a n + 1 = b n = 0 , alors d = pgcd ( a , b ) = b n - 1 = a n .

2) Première méthode (descente de l'algorithme d'Euclide)

On va calculer pour n N les entiers relatifs x n et y n tels que a n = x n a + y n b .
Pour n = N , on aura pgcd ( a , b ) = a N = x N a + y N b . Le couple ( x , y ) = ( x N , y N ) sera solution de notre problème.

Pour n=0 : a 0 = a = 1 a + 0 b ; le couple ( x 0 , y 0 ) = ( 1 , 0 ) convient.
Pour n = 1 : a 1 = b = 0 a + 1 b ; le couple ( x 1 , y 1 ) = ( 0 , 1 ) convient.

  Si aux rangs n et n + 1 on a:   a n = x n a + y n b et   a n + 1 = x n + 1 a + y n + 1 b , alors:
a n + 2 = a n - a n + 1 q n = x n a + y n b - ( x n + 1 a + y n + 1 b ) q n = ( x n - x n + 1 q n ) a + ( y n - y n + 1 q n ) b avec q n = ( a n // a n + 1 ) .
  Au rang n + 2 le couple ( x n + 2 , y n + 2 ) = ( x n - x n + 1 q n , y n - y n + 1 q n ) convient.

  On calcule ainsi de proche en proche les couples ( x n , y n ) jusqu'à notre solution ( x N , y N )

3) Seconde méthode (Remontée de l'algorithme d'Euclide)

  On commence par calculer et stocker dans une liste liste_a les valeurs successives a 0 , a 1 , a 2 , ... , a N jusqu'à la dernière valeur non nulle a N = pgcd ( a , b ) .
  Puis on calcule pour n { N , N , N - 1 , ... , 2 } les entiers relatifs x n et y n tels que a N = x n a n - 2 + y n a n - 1 .

Pour n = 2 on aura pgcd ( a , b ) = a N = x 2 a 0 + y 2 a 1 = x 2 a + y 2 b .  Le couple ( x , y ) = ( x 2 , y 2 ) sera solution de notre problème.
Pour n = N on a a N = a N - 2 - q N - 2 a N - 1 et le couple ( x N , y N ) = ( 1 , - q N - 2 ) convient, avec q N - 2 = a N - 2 // a N - 1

  Si au rang n { N , ... , 3 } on a: a N = x n a n - 2 + y n a n - 1 , alors a N = x n a n - 2 + y n a n - 1 = x n a n - 2 + y n ( a n - 3 - a n - 2 q n - 3 ) = y n a n - 3 + ( x n - y n q n - 3 ) a n - 2 .
  Au rang n - 1 le couple ( x n - 1 , y n - 1 ) = ( y n , x n - y n q n - 3 ) convient  (avec q n - 3 = a n - 3 // a n - 2 )

On calcule ainsi de proche en proche les couples ( x n , y n ) jusqu'à notre solution ( x 2 , y 2 ) .

Q2) Ecrire une fonction bezout_descente(a,b) calculant une solution ( x , y ) de l'équation a x + b y = pgcd ( a , b ) en exploitant la première méthode décrite.

Q3) Ecrire une fonction bezout_remontee(a,b) calculant une solution ( x , y ) de l'équation a x + b y = pgcd ( a , b ) en exploitant la seconde méthode décrite.

© 2014 - Eric Obermeyer      Powered by      Corrigé