I need help to prove this theory

1. Dec 16, 2008

HussamLawen

Hi

i need help to prove this theory:
GCD(n.m)=1 <=> GCD((2^n)-1,(2^m)-1)=1

n,m real numbers

2. Dec 17, 2008

HussamLawen

sorry n,m Integers****

3. Dec 17, 2008

dodo

I don't have yet a proof (thus I'm not completely convinced of the fact yet), but I believe this is a start:

The polynomial $x^k-1$ is divisible by $x-1$; actually, $x^k-1$ factors as $(x-1)(x^{k-1}+x^{k-2}+ ... +x^3+x^2+x+1)$. Applying this with $x = 2^n$ you deduce that $2^n-1$ divides $2^{k n}-1$.

4. Dec 17, 2008

robert Ihnot

If an integer r divides 2^m-1 and 2^n-1, then $$2^m\equiv2^n\equiv1\bmod r$$

By the Euculidean algorithm, since m and n are relatively prime, there exists a and b such that am+bn=1.

Thus $$2^{am+bn}\equiv2\equiv(2^{am})(2^{bn})\equiv(1^a)(1^b)\equiv1\bmod r$$ Thus r equals 1.

Last edited: Dec 17, 2008