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