Algorithme d'Euclide étendu, Théorème de Bézout

La notion principale de cette partie du cours et celle du plus grand commun diviseur ou pgcd de deux entiers.

Le plus grand commun diviseur ou pgcd de deux entiers et non nuls est le plus grand entier qui divise à la fois et .

Exemple pgcd.

Si les nombres sont suffisament petits, il est possible de calculer leur pgcd à l’aide de la factorisation.

Exemple Calculer le pgcd de et de .

On peut alors conclure que pgcd

Cependant, lorsque les nombres sont grands, factoriser n’est pas toujours calculatoirement possible. Un algorithme plus efficace doit être utilisé. Un tel algorithme existe et est connu sous le nom de algorithme d’Euclide. Cet algorithme est basé sur une observation simple. Si et sont deux entiers tels que , alors

Cette observation peut être demontrée facilement. De manière générale, pour montrer l’égalité de deux entiers, il suffit de montrer qu’ils se divisent mutuellement.

On note . Par la définition du symbole mod, il existe un entier tel que . Comme est le plus grand commun diviseur de et , divise à la fois et . Il existe alors des entiers et tels que et . On a:

et on conclue alors que divise . Puisque divise à la fois et alors divise .

Le sens réciproque se montre de façon similaire.

Remarque Puisque , on réduit le problème de trouver le pgcd de deux entiers donnés, à celui de trouver le pgcd de deux entiers plus petits.

Description de l’algorithme

Voir Algorithme d’Euclide

Exemple Calculer le

Donc,

Théorème de Bézout

Identité de Bézout Soient . Il existe deux entiers tels que .

L’existence des entiers et est donnée par l’algorithme d’Euclide étendu (voir section suivante).

Théorème de Bézout Soient . Les entiers sont premiers entre eux si et seulement s’il existe deux entiers et tels que .

Démonstration. Si , par l’identité de Bézout, il existe deux entiers et tels que . Réciproquement, si on a une relation de la forme , alors un diviseur commun à et à , divise , divise donc , et vaut alors . On a bien montré que les entiers et sont premiers entre eux.

Algorithme d’Euclide étendu

L’algorithme d’Euclide étendu est une variante de l’algorithme d’Euclide qui permet, à partir de deux entiers et , de calculer non seulement leur plus grand commun diviseur (pgcd), mais aussi un couple de coefficients de Bézout, c’est-à-dire deux entiers et tels que

Cet algorithme est particulièrement utilisé lorsque on souhaite calculer l’inverse multiplicatif d’un entier.

La question importante est comment calcule-t-on les coefficients et . L’idée principale de l’algorithme est d’effectuer les mêmes étapes que pour l’algorithme d’Euclide, mais en exprimant à chaque itération le reste comme une combinaison linéaire de et . Puisque le dernier reste est le pgcd, celui-ci sera alors exprimé comme une combinaison linéaire de et .

Déroulement de l’algorithme

On note et . On cherche et tels que .

De cette façon, , et .

Exemple On appliquera l’algorithme d’Euclide étendu pour et . Pour cela, on effectuera à gauche les étapes de l’algorithme d’Euclide (calcul des restes et des quotients .) En même temps on écrira à droite les calculs pour et , tels que .

 
 
 
 
 
 
 

Nous avons alors

On remarque en appliquant cette procédure que les combinaisons linéaires de la partie droite sont construites à l’aide des combinaisons linéaires précédentes. On va dériver maintenant des relations récursives pour calculer et .

Relation récursive des coefficients de Bézout

Supposons qu’on se trouve à l’itération . Pendant les deux itérations précédentes nous avons calculé:

Pendant l’itération on calcule d’abord le quotient et le nouveau reste à partir de et :

Cette équation peut se réécrire ainsi:

Notre but est de représenter le nouveau reste comme une combinaison linéaire de et . L’étape qui nous permet de faire cela est de substituer dans la dernière équation de la première équation et de la deuxième équation:

En réarrangeant les termes on obtient:

Ces formules récursives sont valables pour . On pose et .

Calcul des inverses multiplicatifs modulo

On peut utiliser l’algorithme d’Euclide étendu afin de calculer l’inverse modulaire d’un entier. Avant de continuer, on va démontrer un résultat crucial pour la démarche.

Proposition Un entier est inversible modulo si et seulement si .

Démonstration On suppose d’abord que l’entier est inversible modulo . Il existe alors tel que . De cette congruence on voit alors qu’il existe un entier tel que . Par le théorème de Bézout on peut alors conclure que .

Réciproquement, on suppose que . Par le théorème de Bézout, il existe des entiers tels que . Par conséquent, et est alors l’inverse de modulo .

Supposons maintenant qu’on veut calculer l’inverse de

On vient de montrer que si cet inverse existe, alors forcement . En appliquant l’algorithme d’Euclide étendu on obtient un couple tels que . On a alors

La dernière équation est la définition de l’inverse. Ceci vaut dire que est l’inverse de :

Exercice Calculer

Solution On applique l’algorithme d’Euclide étendu pour trouver le de et .

Le pgcd de et est alors bien .

On cherche les coefficients de Bézout.

Nous avons alors

est un corps est premier

On va montrer maintenant que si est un nombre premier alors est un corps.

Proposition Si est un nombre premier, alors est un corps.

Démonstration On a déjà vu que est un anneau commutatif. Il suffit juste de montrer que tous les éléments non-nuls de sont inversibles. Les éléments non-nuls de sont les éléments . Puisque est premier, tous les éléments non-nuls strictement inférieurs à sont premiers avec . Par conséquent, ils sont inversibles modulo .

Montrer que si est un corps, alors est un nombre premier est laissé comme exercice.

Fork me on GitHub