Nous supposons $a \ge b$ . Nous allons montrer que faire l’algorithme d’Euclide pour le couple $(2^a-1,2^b-1)$ revient à faire l’algorithme d’Euclide pour $(a,b)$ . Tout d’abord rappellons la formule qui est à la base de l’algorithme d’Euclide : $\pgcd(a,b) = \pgcd(a-b,b)$ . Appliqué à $2^a-1$ et $2^b-1$ cela donne directement $\pgcd(2^a-1,2^b-1) = \pgcd(2^a-2^b,2^b-1)$ . Mais $2^a-2^b = 2^b(2^{a-b}-1)$ d’où $\pgcd(2^a-1,2^b-1) = \pgcd(2^b(2^{a-b}-1),2^b-1) = \pgcd(2^{a-b}-1,2^b-1)$ . La dernière égalité vient du fait $2^b$ et $2^b-1$ sont premiers entre eux (deux entiers consécutifs sont toujours premiers entre eux).

Nous avons montrer : $\pgcd(2^a-1,2^b-1) =\pgcd(2^{a-b}-1,2^b-1)$ . Cette formule est à mettre en parallèle de $\pgcd(a,b) = \pgcd(a-b,b)$ . En itérant cette formule nous obtenons que si $a=bq+r$ alors : $\pgcd(2^a-1,2^b-1) = \pgcd(2^{a-bq}-1,2^b-1) = \pgcd(2^r-1,2^b-1)$ à comparer avec $\pgcd(a,b)=\pgcd(a-bq,b)=\pgcd(r,b)$ . Nous avons notre première étape de l’algorithme d’Euclide. En itérant l’algorithme d’Euclide pour $(a,b)$ , nous nous arêtons au dernier reste non nul: $\pgcd(a,b) = \pgcd(b,r) = \cdots = \pgcd(r_n,0)=r_n$ . Ce qui va donner pour nous $\pgcd(2^a-1,2^b-1) = \pgcd(2^b-1,2^r-1) = \cdots = \pgcd(2^{r_n}-1,2^0-1) = 2^{r_n}-1$ .

Bilan : $\pgcd(2^a-1,2^b-1) = 2^{\pgcd(a,b)}-1$ .

exo7 336