I need help finishing a gcd proof

Printable View

September 25th 2012, 07:39 PM
bskcase98

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.
September 25th 2012, 08:18 PM
chiro

Re: I need help finishing a gcd proof

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?
September 25th 2012, 10:53 PM
johnsomeone

Re: I need help finishing a gcd proof

You've proven that, if $d = gcd(a,b)$ , then $(2^d - 1)$ divides the $gcd((2^a - 1), (2^b-1))$ .

If you could prove that $gcd((2^a - 1), (2^b-1))$ divides $(2^d - 1)$ , 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 $(b^y - 1)$ and d divides $(b^y - 1)$ , then d divides $(b^{gcd(x, y)} - 1)$ . 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 $c$ divides $(2^a - 1)$ and $c$ divides $(2^b - 1)$ , then $c$ divides $(2^{gcd(a, b)} - 1)$ .

If you can prove that Lemma, then, since $c$ = $gcd((2^a - 1), (2^b-1))$ divides both $(2^a - 1)$ and $(2^b - 1)$ , it would follow that

$c = gcd((2^a - 1), (2^b-1))$ divides $(2^{gcd(a, b)} - 1)$ .

And since you already have shown that $(2^{gcd(a,b)} - 1)$ divides the $gcd((2^a - 1), (2^b-1))$ , 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.