Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I need help to prove this theory

  1. Dec 16, 2008 #1

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

    n,m real numbers
  2. jcsd
  3. Dec 17, 2008 #2
    sorry n,m Integers****
  4. Dec 17, 2008 #3
    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 [itex]x^k-1[/itex] is divisible by [itex]x-1[/itex]; actually, [itex]x^k-1[/itex] factors as [itex](x-1)(x^{k-1}+x^{k-2}+ ... +x^3+x^2+x+1)[/itex]. Applying this with [itex]x = 2^n[/itex] you deduce that [itex]2^n-1[/itex] divides [itex]2^{k n}-1[/itex].
  5. Dec 17, 2008 #4
    If an integer r divides 2^m-1 and 2^n-1, then [tex]2^m\equiv2^n\equiv1\bmod r[/tex]

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

    Thus [tex]2^{am+bn}\equiv2\equiv(2^{am})(2^{bn})\equiv(1^a)(1^b)\equiv1\bmod r[/tex] Thus r equals 1.
    Last edited: Dec 17, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook