2
$\begingroup$

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!

$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you very much. But how could I end up with 2^(gcd(a,b)) − 1 if I use Euclids proof? Do I have to use induction? or is there an easier way? $\endgroup$
    – Peter
    Nov 16, 2014 at 17:12
  • $\begingroup$ Thanks mate! It's completely clear to me now. Now you have the best answer. $\endgroup$
    – Peter
    Nov 16, 2014 at 17:41
  • $\begingroup$ Glad that I was of help! $\endgroup$
    – Ojas
    Nov 16, 2014 at 17:42

Not the answer you're looking for? Browse other questions tagged .