Prove that $\gcd(2^a - 1, 2^b - 1) = 2^{\gcd(a,b)} - 1$ I have two questions about a prove that I have to do for my mathematic study. I'm now thinking about it the whole day, but can't find the prove.
Let $a,b \in \mathbb Z_{>0}$.

(a) Prove: $\gcd(2^a - 1, 2^b - 1) = 2^{\gcd(a,b)} - 1$
(b) Is this also true when you replace $2$ with a number $c > 2, c \in \mathbb Z$?

For (b), I think it's true, but I can't explain why.
Thanks in advance!

Without loss of generality, let us assume that $a>b$.
You can write $2^a-1 = 2^b2^{a-b} - 2^{a-b} + 2^{a-b} - 1 = 2^{a-b}(2^b-1) + 2^{a-b}-1$.
$\therefore gcd(2^a-1,2^b-1) = gcd(2^b-1,2^{a-b}-1).$
You can now continue the proof on the same lines as Euclid's proof for gcd of two integers.
There is no significance of the number '2' here, so this would be correct also for all integers greater than 2 also.
EDIT : We can continue reducing the larger number, till we get to a point such that $gcd(2^a-1,2^b-1) = gcd(2^k-1,2^k-1)$ for some $k$ after which point we can't further reduce and we get $gcd(2^a-1,2^b-1) = 2^k-1$ . From the equation, it is clear that $k$ will always be a linear combination of $a$ and $b$. The smallest positive number which is a linear combination of $a$ and $b$ is the gcd of $a$ and $b$. Hence, $k=gcd(a,b)$. Hence, $gcd(2^a-1,2^b-1)=2^{gcd(a,b)}-1$.
