# Math Help - Proof involving GCD

1. ## Proof involving GCD

Prove that for any two positive integers n amd m,
$gcd(2^n - 1, 2^m -1) = 2^{gcd(n,m)}-1$

Not sure how to approach this problem .

2. let d=gcd(n,m), then there exist positive integers k,s, such that n=kd,m=sd,(k,s)=1.
Obviously, $2^d-1$ is a common divisor of the two number.
And, it is easy to prove that $1+2^d+2^{2d}+...+2^{(k-1)d}$ and $1+2^d+2^{2d}+...+2^{(s-1)d}$ are relatively prime if (k,s)=1.
thus the result is proved!

3. Thank you. I am confused though. Why do you wish to prove $1+2+2^2+...+2^k$ and $1+2+2^2+...+2^s$ are relatively prime?

Also, why is it obvious that 2^d-1 is a factor of those two numbers?

4. Originally Posted by icecube
Thank you. I am confused though. Why do you wish to prove $1+2+2^2+...+2^k$ and $1+2+2^2+...+2^s$ are relatively prime?

Also, why is it obvious that 2^d-1 is a factor of those two numbers?

$2^n-1 = (2^d-1)(1+2^d+2^{2d}+...+2^{(k-1)d})$
$2^m-1 = (2^d-1)(1+2^d+2^{2d}+...+2^{(s-1)d})$

So $gcd(2^n-1,2^m-1) = (2^d-1).gcd((1+2^d+2^{2d}+...+2^{(k-1)d}),(1+2^d+2^{2d}+...+2^{(s-1)d}))$

So if you show $gcd((1+2^d+2^{2d}+...+2^{(k-1)d}),(1+2^d+2^{2d}+...+2^{(s-1)d}))=1$ under the condition that (s,k)=1 we will be done. So can you do that? (You can infact replace 2 with any prime power, p^n)

5. I see, I see! I forgot about that.
I should be able to prove that though it's late so I'll try later tomorrow or this week. Thanks a lot.

6. Originally Posted by Shanks
let d=gcd(n,m), then there exist positive integers k,s, such that n=kd,m=sd,(k,s)=1.
Obviously, $2^d-1$ is a common divisor of the two number.
And, it is easy to prove that $1+2+2^2+...+2^k$ and $1+2+2^2+...+2^s$ are relatively prime if (k,s)=1.
thus the result is proved!

Shanks I think there is an errata in your post. Powers should be (k-1) and (s-1). As a counterexample to your claim consider k=5 and s=7

7. Yeah, I made a careless mistake.I forgot to the common divisor d and the k-1 things,.
what I mean is the quotient of the number when divided by $2^d-1$, but I write down the wrong representation.
Thank you for your reminding me.

8. Originally Posted by Shanks
Yeah, I made a careless mistake.I forgot to the common divisor d and the k-1 things,.
what I mean is the quotient of the number when divided by $2^d-1$, but I write down the wrong representation.
Thank you for your reminding me.
Yep that's exactly the approach I followed. Thanks (Enjoyed this question!)

9. Originally Posted by aman_cc
$2^n-1 = (2^d-1)(1+2^d+2^{2d}+...+2^{(k-1)d})$
$2^m-1 = (2^d-1)(1+2^d+2^{2d}+...+2^{(s-1)d})$

So $gcd(2^n-1,2^m-1) = (2^d-1).gcd((1+2^d+2^{2d}+...+2^{(k-1)d}),(1+2^d+2^{2d}+...+2^{(s-1)d}))$

So if you show $gcd((1+2^d+2^{2d}+...+2^{(k-1)d}),(1+2^d+2^{2d}+...+2^{(s-1)d}))=1$ under the condition that (s,k)=1 we will be done. So can you do that? (You can infact replace 2 with any prime power, p^n)

Exactly,

Once you get to this part you can proceed as follows.

It suffices to show that there exist two numbers $x,y$ such that $x \left( \sum _{i=0} ^ {k-1} 2^{id} \right) - y \left( \sum _{i=0} ^ {s-1} 2^{id} \right) = 1$.

First, notice that

$\left( \sum _{j=0} ^ {r-1} 2^{jsd} \right) \left( \sum _{i=0} ^ {s-1} 2^{id} \right) = \sum _{i=0} ^ {rs-1} 2^{id}$

So suppose that $\gcd(k,s)=1$ then by definition there are positive numbers $q,r$ such that $q k - r s = 1$.

It is easy to verify that $x= \sum _{j=0} ^ {q-1} 2^{jkd}$

and

$y= 2^{d}\left(\sum _{j=0} ^ {r-1} 2^{jkd} \right)$

satisfies the equation above, proving the result.

10. Thank you. However, $\left( \sum _{j=0} ^ {r-1} 2^{jkd} \right) \left( \sum _{i=0} ^ {s-1} 2^{id} \right) = \sum _{i=0} ^ {rs-1} 2^{id}$ is clear to me but my professor would like us to make a complete proof, so I would have to prove this @_@. How would one go about proving this as well?
I'm currently working on it as well though I'm stuck.

-Several hours later-
Still no closer to proving this.

11. $

\sum _ {i=0} ^{rs-1} 2^{id} = 2^0 + ... + 2^{s-1} + 2^{s} + ... + 2^{2s-1} + 2^{2s} + ... + 2^{3s-1} + ... + 2^{(r-1)s} + ... + 2^{rs-1}
$

$
= 2^{0s} \sum _ {i=0} ^ {s-1} 2^i + 2^{s} \sum _ {i=0} ^ {s-1} 2^i + ... + 2^{(r-1)s} \sum _ {i=0} ^ {s-1} 2^i = \left( \sum _ {i=0} ^ {s-1} 2^i \right) \left( \sum _{i=0} ^ {r-1} 2^{i s d}\right)
$

12. O_O thank you. I'm just curious. Was this something you knew previously or did you just derive this relationship yourself? =O