Thread: I need help finishing a gcd proof

the question was to prove:
if m and n are positive integers and gcd(m, n) = d, then gcd(2ⁿ - 1, 2^m - 1) = 2^d - 1.

my approach was the following:

given gdc(m,n) = d, the d|m and d|n also m = dp and n = dq for some integers p and q.
so, (2ⁿ - 1, 2^m - 1) = (2^dq - 1, 2^dp - 1)
2^dq - 1 = 2^d - 1(2^d(q-1) + 2^d(q-2) +...+ 2^d + 1) = (2^d - 1)(s) for some integer s.
2^dp - 1 = 2^d - 1(2^d(p-1) + 2^d(p-2) +...+ 2^d + 1) = (2^d - 1)(t) for some integer t.

so (2^d - 1) is a divisor of (2ⁿ - 1, 2^m - 1), however I do not know how to show that it is the gcd(2ⁿ - 1, 2^m - 1) or how to show that
gcd(s,t) = 1.

my instructor suggested proof by induction showing true for m + n < s, then true for m + n = s. I can not see how to start the proof
using his suggestion. any help would be appreciated.

Hey bskcase98.

If something is a greatest divisor (let alone a greatest common divisor), then it means that all divisors must be less than that divisor. In other words if you have n and the greatest divisor of n is a then if n = ab then b <= a. From this can you show that this holds?

You've proven that, if , then divides the .

If you could prove that divides , then you'd be done, since they'd then be equal.

Recall in a previous thread of yours called "need help with an Eucledian algorthim and gcd involving factorials and large exponets", I gave a long derivation? In there I wrote:
"Proposition: If d divides and d divides , then d divides . Rather than work out a proof, I'll run through it step by step for this problem."
Well, now that proposition is exactly what you need. Switching the labelling back to the current problem, you'd be done if you could prove:

Lemma: If divides and divides , then divides .

If you can prove that Lemma, then, since = divides both and , it would follow that

divides .

And since you already have shown that divides the , you'd then be done.

That insane calculation I did in that other problem lays out - perhaps - the way for you to prove the above Lemma.

By the way, that insane calculation is, I believe, called Euclid's Algorithm for finding the gcd.

Just a thought. Good luck.