How to Prove GCD of Two Powers of 2 Minus 1?

[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?

 

[micromass]

Hint: Write

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

 

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

 

[CantorSet]

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

 

[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?

 

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

 

[Borek]

Thus

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

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.

 

[micromass]

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

 

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

 

[CantorSet]

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.

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

 

[CantorSet]

Got it.

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

 

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

 

[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