Prove that for any two positive integers n amd m,
$\displaystyle gcd(2^n - 1, 2^m -1) = 2^{gcd(n,m)}-1$
Not sure how to approach this problem .
let d=gcd(n,m), then there exist positive integers k,s, such that n=kd,m=sd,(k,s)=1.
Obviously, $\displaystyle 2^d-1$ is a common divisor of the two number.
And, it is easy to prove that $\displaystyle 1+2^d+2^{2d}+...+2^{(k-1)d}$ and $\displaystyle 1+2^d+2^{2d}+...+2^{(s-1)d}$ are relatively prime if (k,s)=1.
thus the result is proved!
Thank you. I am confused though. Why do you wish to prove $\displaystyle 1+2+2^2+...+2^k$ and $\displaystyle 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?
$\displaystyle 2^n-1 = (2^d-1)(1+2^d+2^{2d}+...+2^{(k-1)d})$
$\displaystyle 2^m-1 = (2^d-1)(1+2^d+2^{2d}+...+2^{(s-1)d})$
So $\displaystyle 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 $\displaystyle 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 $\displaystyle x,y$ such that $\displaystyle x \left( \sum _{i=0} ^ {k-1} 2^{id} \right) - y \left( \sum _{i=0} ^ {s-1} 2^{id} \right) = 1$.
First, notice that
$\displaystyle \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 $\displaystyle \gcd(k,s)=1$ then by definition there are positive numbers $\displaystyle q,r$ such that $\displaystyle q k - r s = 1$.
It is easy to verify that $\displaystyle x= \sum _{j=0} ^ {q-1} 2^{jkd} $
and
$\displaystyle y= 2^{d}\left(\sum _{j=0} ^ {r-1} 2^{jkd} \right)$
satisfies the equation above, proving the result.
Thank you. However, $\displaystyle \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.
$\displaystyle
\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}
$
$\displaystyle
= 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)
$