Gcd of two Mersenne numbers

Let $a$ and $b$ be two positive integers. Show that

$gcd\left(2^a-1,2^b-1\right)=2^{gcd(a,b)}-1.$

I solved itMark it done Add to my listKeep it in your list

Solutions

Reveal solutionsAre you sure? Give it a try first.

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$ .

Solution by jlzetaFR

Discussions0 useful votes

pgcd(a,b)=d alors il existe k1 et k2 entiers positifs distincts et premiers entre eux tels que a=k1.d et b=k2.d

2^a-1=(2^d)^k1-1=(2^d-1)(1+(2^d)+(2^d)^2 +..+(2^d)^(k1-1))
2^b-1=(2^d)^k2-1=(2^d-1)(1+(2^d)+(2^d)^2 +..+(2^d)^(k2-1))

d’où le pgcd(2^a-1, 2^b-1)=2^pgcd(a,b)-1

Report