PGCD de deux nombres de Mersenne

Attention les yeux, ma solution utilise une petite astuce ! Supposons que $b\geqslant a$. On effectue la division euclidienne de $b$ par $a$ et on écrit $b=aq+r$. On remarque ensuite que
$$2^{b}-1=(2^{a}-1)(2^{b-a}+2^{b-2a}+\cdots+2^{b-qa})+(2^{r}-1).$$Ainsi, on a la division euclidienne de $2^{b}-1$ par $2^{a}-1$. Ensuite, lorsqu’on continue l'algorithme d’Euclide étendu, on va finir par obtenir $2^{pgcd(a,b)}-1$ car on va retrouver dans l’exposant les mêmes termes que pour l’algorithme appliqué à $a$ et $b$.