Algorithme d'Euclide étendu en python

Algorithme d'Euclide

L'algorithme d'Euclide permet de calculer le PGCD de deux entiers par la méthodes des divisions successives. Il repose sur la propriété fondamentale suivante : étant donné deux entiers \(a\) et \(b\) et avec \(r\) le reste de la division euclidienne de \(a\) par \(b\), on a :

\[PGCD(b;r)=PGCD(a;b)\]

Cette propriété permet de construire par divisions successives une suite strictement décroissante d'entiers naturels qui est nécessairement finie. Le \(PGCD(a;b)\) est alors le dernier reste non nul. Pour plus de détail sur l'algorithme d'Euclide, suivre ce lien.

Sa programmation en python est toute simple (tester le code ci-dessous) :

Théorème de Bézout - Coefficients de Bézout

Étant donné deux entiers \(a\) et \(b\) et \(d=PGCD(a;b)\), le théorème de Bézout affirme l'existence de deux entiers \(u\) et \(v\) tels que :

\[au+bv=d\]

Ces entiers \(u\) et \(v\) sont appelés coefficients de Bézout.

Pour obtenir ces coefficients de Bézout, on utilise l'algorithme d'Euclide qui permet de calculer le \(PGCD\) \(d\) de \(a\) et de \(b\). Pour cela, on exprime, à chaque étape de l'algorithme, le reste obtenu en fonction de \(a\) et de \(b\) par une expression de la forme :

\[au_n+bv_n=r_n\quad (1)\]

À la fin de l'algorithme, le dernier reste non nul est le \(PGCD\) de \(a\) et de \(b\), la relation (1) ci-dessus donne donc les coefficients de Bézout recherchés.

Écrivons la relation (1) à deux rangs consécutifs \(n-1\) et \(n\) :

\[\left\{\begin{matrix}au_{n-1}+bv_{n-1}=r_{n-1}\\ au_n+bv_n=r_n\end{matrix}\right.\]

L'étape suivante dans l'algorithme d'Euclide, si \(r_n\neq 0\), consiste à effectuer la division euclidienne de \(r_{n-1}\) et de \(r_n\) : \(r_{n-1}=qr_n+r_{n+1}\) avec \(0\leqslant r_{n+1}<r_n\).

On a donc :

\[\begin{align}r_{n+1} & = r_{n-1}-qr_n\\ & = au_{n-1}+bv_{n-1}-q(au_n+bv_n)\\ & = a(u_{n-1}-qu_n)+b(v_{n-1}-qv_n)\end{align}\]

On pose donc :

\[\left\{\begin{align}u_{n+1} &= u_{n-1}-qu_n \\ v_{n+1} &= v_{n-1}-qv_n\end{align}\right. \quad (2)\]

Il s'agit d'une récurrence double.

Cela conduit à l'algorithme suivant, écrit en python.

On initialise en posant :

\[\left\{\begin{align}u_{0}=1 &\textrm{ et } v_0=0 \quad \textrm{ car } 1\times a+0\times b=a\\ u_1=0 &\textrm{ et } v_1=1 \quad \textrm{ car } 0\times a+1\times b=b\end{align}\right.\]

Traduction matricielle

Les relations de récurrence (2) peuvent s'écrire sous forme matricielle.

Pour tout \(n\in\mathbb{N}\), posons :

\[M_n=\left(\begin{matrix}u_{n-1} & v_{n-1} \\ u_n & v_n\end{matrix}\right) \textrm{ et } P=\left(\begin{matrix}0 & 1 \\ 1 & -q\end{matrix}\right)\]

où \(q\) est le quotient de la division euclidienne de \(r_{n-1}\) par \(r_n\).

Les relations (2) sont alors équivalentes à : \(M_{n+1}=P\times M_n\).

En initialisant comme précédemment la suite \((M_n)\) avec \(M_0=\left(\begin{matrix} 1 & 0 \\ 0 & 1\end{matrix}\right)\), on obtient l'algorithme suivant :

import numpy as np

def bezout_matrice(a,b):
  m0 = np.array([[1,0],[0,1]])
  while b != 0:
    r = a % b
    q = a// b
    a, b = b, r
    p = np.array([[0,1],[1,-q]])
    m0 = p @ m0
  return (a, m0[0])

Mais on peut aller un peu plus loin : on remarque que les calculs permettant d'obtenir \(u_{n+1}\) à partir de \(u_{n-1}\) et de \(u_n\) sont les mêmes que ceux qui permettent d'obtenir \(r_{n+1}\) à partir de \(r_{n-1}\) et de \(r_n\) par division euclidienne. On peut donc aussi inclure le calcul du \(PGCD\) dans le calcul matriciel. Il suffit pour cela d'ajouter une troisième colonne à la matrice \(M_n\) et de poser \(M_0=\left(\begin{matrix} 1 & 0 & a\\ 0 & 1 & b\end{matrix}\right)\). Cet algorithme est mis en œuvre ci-dessous.