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

GCD of two powers of 2, minus 1

  1. Aug 31, 2011 #1
    Hi everyone, this is not a homework question just a math puzzle I came across.

    Let [itex]a[/itex] and [itex]b[/itex] be any two natural numbers. And let [itex] (m,n) [/itex] denote the GCD of [itex]m[/itex] and [itex]n[/itex] as usual. Prove [tex] (2^{a}-1,2^{b}-1) = 2^{(a,b)}-1 [/tex]

    I'm thinking of double induction on [itex]a[/itex] and [itex]b[/itex] but I'm having trouble with the inductive steps.

    Does any know how to do this? If so, any hints?
     
  2. jcsd
  3. Aug 31, 2011 #2
    Hint: Write

    [tex]2^n-1=2^{n-1}+2^{n+2}+...+2+1[/tex]
     
  4. Sep 1, 2011 #3
    I'd try to base a proof on the fact that [itex]2^m-1[/itex] divides [itex]2^n-1[/itex] whenever [itex]m[/itex] divides [itex]n[/itex]. This is very visually seen if you multiply 100010001 by 1111, for example. So, divisibility properties of numbers of the form [itex]2^n-1[/itex] map nicely to divisibility properties of the exponents.

    By the way, this is true for repunits in general: the same goes, say, for numbers of the form [itex]\frac {10^n-1} 9[/itex] (i.e. numbers like 111111 in base 10).
     
  5. Sep 1, 2011 #4
    Thanks for the responses guys, those seem like really helpful hints. But I still could not proceed with the proof. =(
     
  6. Sep 1, 2011 #5
    Let me do an example. I claim that [itex]2^5-1[/itex] divides [itex]2^{10}-1[/itex]. I write

    [tex]2^{10}-1=2^9+2^8+2^7+2^6+2^5+2^4+2^3+2^2+2^1+2^0[/tex]

    and

    [tex]2^5-1=2^4+2^3+2^2+2^1+2^0[/tex]

    Then

    [tex](2^{10}-1)-(2^5-1)=2^9+2^8+2^7+2^6+2^5[/tex]

    Thus

    [tex](2^{10}-1)-(2^5-1)-2^4(2^5-1)=0[/tex]

    Hence

    [tex]2^{10}-1=(2^5-1)(1+2^4)[/tex]

    Can you do something similar in the general case?
     
  7. Sep 1, 2011 #6
    Another hint (again, of a visual nature - you are most encouraged to fill in the formal argument as micromass suggests) may be the following:

    If you remember the Euclidean algorithm, it was based on the fact that GCD(a,b) = GCD(b, a mod b). Now, what is "a mod b" when both a and b are repunits? See one example: 11111111111111 (that's 14 ones) = 10001000100 x 1111 + 11.
     
  8. Sep 2, 2011 #7

    Borek

    User Avatar

    Staff: Mentor

    Hm, my calculator doesn't agree. But

    [tex](2^{10}-1)-(2^5-1)-2^5(2^5-1)=0[/tex]

    should work.

    Not that I understand anything, just playing with numbers.
     
  9. Sep 2, 2011 #8
    Oops, of course, Borek. I'm bad at arithmatic :frown:
     
  10. Sep 2, 2011 #9

    disregardthat

    User Avatar
    Science Advisor

    Use the euclidean algorithm:

    Assume a > b, and write a = qb+r. Then (a,b) = (r,b), and

    (2^a-1,2^b-1) = (2^a-1-2^(a-bq)(2^b-1),2^b-1) = (2^r-1,2^b-1). Now we know that b > r, and we do the anologous thing again (this is the euclidean algorithm) until we arrive at (2^a-1,2^b-1) = (2^(a,b)-1,2^s-1) for some s (or with the entries switched) with ((a,b),s) = (a,b). But now we know that (2^a-1,2^b-1) >= 2^(a,b)-1. Furthermore, 2^(a,b)-1 divides both 2^a-1 and 2^b-1 which can be shown by factorization, and we are done.

    Another alternative is by induction on the largest exponent. If they are equal, the result is obvious, so we assume they are not equal. If it's a, we arrive at (2^a-1,2^b-1) = (2^r-1,2^b-1) where (a,b) = (r,b) and a > b > r. Now b is the largest exponent, so by induction (2^a-1,2^b-1) = (2^r-1,2^b-1) = 2^(r,b)-1 = 2^(a,b)-1 and we are done. If b was the largest one, a similar argument proves the inductive step. It remains to show the base case: a = b = 1, but this is trivial of course.
     
    Last edited: Sep 2, 2011
  11. Sep 3, 2011 #10
    That's very interesting. But how do we justify the step

    [tex] (2^{a}-1-(2^{r}-1)(2^{b}-1),2^{b}-1)=(2^{r}-1,2^{b}-1) [/tex]
     
  12. Sep 3, 2011 #11
    Got it.

    Thanks to everyone who responded on this thread. I bow before true masters of numbers. :shy:
     
  13. Sep 3, 2011 #12

    disregardthat

    User Avatar
    Science Advisor

    Oh, a mistake on my part there. Forget the first part, and focus on the proof by induction, where we instead transform the gcd as such:

    (2^a-1,2^b-1) = (2^a-1-2^(a-b)(2^b-1),2^b-1) = (2^(a-b)-1,2^b-1), where gcd(a,b) = gcd(a-b,b), and so the inductive step is proved (since the largest of a-b and b is less than a (if a > b)).
     
  14. Sep 4, 2011 #13
    Let d = GCD([itex]2^{n}-1,2^{m}-1)[/itex] (with m < n) and

    Lemma1: d is odd

    Lemma2: If d divides b and d divides a, then d divdides (b-a) (with a < b)



    Since [itex](2^{n}-1) - (2^{m}-1)[/itex] = [itex]2^{n} - 2^{m}[/itex] , we have

    d | [itex](2^{n}-1)[/itex] and d | [itex](2^{m}-1)[/itex] -> d | [itex](2^{n} - 2^{m})[/itex] (Lemma2); and with n = s+m:

    d | [itex](2^{n} - 2^{m})[/itex] -> d | [itex]2^{m}*(2^{s} - 1)[/itex]; and from Lemma 1 it follows:

    d | [itex](2^{s} - 1)[/itex]; etc

    But the process on the exponents (n,m) -> (n-m.m) etc is purely Euclidean's algorithm for the GCD
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook