# GCD of two powers of 2, minus 1

1. Aug 31, 2011

### CantorSet

Hi everyone, this is not a homework question just a math puzzle I came across.

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

I'm thinking of double induction on $a$ and $b$ but I'm having trouble with the inductive steps.

Does any know how to do this? If so, any hints?

2. Aug 31, 2011

### micromass

Hint: Write

$$2^n-1=2^{n-1}+2^{n+2}+...+2+1$$

3. Sep 1, 2011

### dodo

I'd try to base a proof on the fact that $2^m-1$ divides $2^n-1$ whenever $m$ divides $n$. This is very visually seen if you multiply 100010001 by 1111, for example. So, divisibility properties of numbers of the form $2^n-1$ 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 $\frac {10^n-1} 9$ (i.e. numbers like 111111 in base 10).

4. Sep 1, 2011

### CantorSet

Thanks for the responses guys, those seem like really helpful hints. But I still could not proceed with the proof. =(

5. Sep 1, 2011

### micromass

Let me do an example. I claim that $2^5-1$ divides $2^{10}-1$. I write

$$2^{10}-1=2^9+2^8+2^7+2^6+2^5+2^4+2^3+2^2+2^1+2^0$$

and

$$2^5-1=2^4+2^3+2^2+2^1+2^0$$

Then

$$(2^{10}-1)-(2^5-1)=2^9+2^8+2^7+2^6+2^5$$

Thus

$$(2^{10}-1)-(2^5-1)-2^4(2^5-1)=0$$

Hence

$$2^{10}-1=(2^5-1)(1+2^4)$$

Can you do something similar in the general case?

6. Sep 1, 2011

### dodo

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.

7. Sep 2, 2011

### Staff: Mentor

Hm, my calculator doesn't agree. But

$$(2^{10}-1)-(2^5-1)-2^5(2^5-1)=0$$

should work.

Not that I understand anything, just playing with numbers.

8. Sep 2, 2011

### micromass

Oops, of course, Borek. I'm bad at arithmatic

9. Sep 2, 2011

### disregardthat

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
10. Sep 3, 2011

### CantorSet

That's very interesting. But how do we justify the step

$$(2^{a}-1-(2^{r}-1)(2^{b}-1),2^{b}-1)=(2^{r}-1,2^{b}-1)$$

11. Sep 3, 2011

### CantorSet

Got it.

Thanks to everyone who responded on this thread. I bow before true masters of numbers. :shy:

12. Sep 3, 2011

### disregardthat

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)).

13. Sep 4, 2011

### RamaWolf

Let d = GCD($2^{n}-1,2^{m}-1)$ (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 $(2^{n}-1) - (2^{m}-1)$ = $2^{n} - 2^{m}$ , we have

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

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

d | $(2^{s} - 1)$; etc

But the process on the exponents (n,m) -> (n-m.m) etc is purely Euclidean's algorithm for the GCD