Algorithme d'Euclide étendu

Identité de Bezout

L'identité de Bezout (ou théorème de Bezout ou relation de Bezout ou encore lemme de Bezout) peut être définie comme suit:

Soient N et P, deux entiers non nuls ayant d comme plus grand commun diviseur, c'est à dire,

`PGCD ( N , P ) = d`

Alors, il existe 2 entiers u et v tels que,

`N*u + P*v = d`

Exemples de coefficients de Bezout

Exemple 1 : N = 65 et P = 39, alors u = -1 et v = 2 car,

`65 * (-1) + 39 * 2 = PGCD(65,39) = 13`

Exemple 2 : N = 195 et P = 154, alors u = -15 et v = 19 car,

`195 * (-15) + 154 * 19 = PGCD(195,154) = 1`

Comment trouver les coefficients de Bezout ?

Les coefficients de Bezout peuvent être calculés à l'aide de l'algorithme d'Euclide étendu.
Cet algorithme consiste à appliquer l'algorithme d'Euclide pour trouver le PGCD et ensuite de réécrire les équations en "repartant du bas". On reprend l'exemple 2 ci-dessus :

Soit N = 195 et P = 154. On calcule le PGCD selon l'algorithme d'Euclide :

`195 = (1) 154 + 41`
`154 = (3) 41 + 31`
`41 = (1) 31 + 10`
`31 = (3) 10 + 1`
`10 = (1) 10 + 0`

PGCD( 195 , 154 ) = 1 (dernier reste non nul)

On réécrit les équations (sauf la dernière avec reste nul) de manière à isoler le reste de la division euclidienne,

`41 = 195 - (1)154`
`31 = 154 - (3) 41`
`10 = 41 - (1) 31`
`1 = 31 - (3) 10`

On part de la dernière division et on remplace cette fois les quotients en utilisant la division "au dessus" et ainsi de suite :
On remplace 10,
`1 = 31 - (3) (41 - (1) 31) = (4) 31 - (3) 41`

On remplace 31,
`1 = (4) (154 - (3) 41) - (3) 41 = (4) 154 - (15) 41`

On remplace 41,
`1 = (4) 154 - (15) (195 - (1) 154) = (19) 154 -(15) 195`

On obtient bien le même résultat que ci-dessus à savoir,

u = -15 et v = 19

Quelques conséquences de l'identité de Bezout

- Soit N et P, deux entiers non nuls et d leur PGCD, alors les multiples de d s'écrivent N.x + P.y (x et y sont des entiers)

- Si N et P sont premiers entre eux alors il existe deux entiers u et v tels que N.u + P.v = 1

- Une conséquence de cette dernière propriété (en appliquant modulo N en aux deux membres) est la suivante,
Soit N et P, deux entiers non nuls, premiers entre eux alors, il existe un entier v tel que,
`P.v\equiv 1\mod N` (v est l'inverse modulaire de P modulo N)
Dit autrement, si N et P sont premiers entre eux alors l'inverse modulaire de P modulo N existe.
On peut d'ailleurs montrer l'inverse et conclure que si N et P sont premiers entre eux si et seulement si l'inverse modulaire de P modulo N existe.

Programmation

Python

Ce programme en python calcule les coefficients de l'identité de Bezout (algorithme d'Euclide étendu).

La fonction bezout(a , b) retourne un triplet ( u , v , pgcd(a,b) ) , u et v étant les coefficients de Bezout qui vérifient :
`a * u + b * v = pgcd (a , b)`

Cette fonction utilise la notion de récursivité, c'est à dire qu'elle s'appelle elle-même ( bezout( b , r ) ).

def bezout(a, b):
    if b == 0:
        return 1, 0, a
    else:
        q = a//b
        r = a%b
        x, y, g = bezout(b, r)
        return y, x - q * y, g

Voir aussi

PGCD
Division euclidienne
Inverse modulaire