# I need help finishing a gcd proof

• Sep 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(2n - 1, 2m - 1) = 2d - 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, (2n - 1, 2m - 1) = (2dq - 1, 2dp - 1)
2dq - 1 = 2d - 1(2d(q-1) + 2d(q-2) +...+ 2d + 1) = (2d - 1)(s) for some integer s.
2dp - 1 = 2d - 1(2d(p-1) + 2d(p-2) +...+ 2d + 1) = (2d - 1)(t) for some integer t.

so (2d - 1) is a divisor of (2n - 1, 2m - 1), however I do not know how to show that it is the gcd(2n - 1, 2m - 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.
• Sep 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?
• Sep 25th 2012, 10:53 PM
johnsomeone
Re: I need help finishing a gcd proof
You've proven that, if \$\displaystyle d = gcd(a,b)\$, then \$\displaystyle (2^d - 1)\$ divides the \$\displaystyle gcd((2^a - 1), (2^b-1))\$.

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

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

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

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