# Proving that $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n )} - 1$

Somewhere on Stack Exchange I saw the equation

$$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1.$$

I had never seen this before, so I started trying to prove it. Without success...

Can anyone explain me (so actually prove) why this equation is true?

And can we say the same when replacing the '$2$' by any integer number '$a$'?

• Let $m\lt n$. We have $2^n-1=2^{n-m}(2^m-1)+(2^{n-m}-1)$. So our $\gcd$ is $\gcd(2^{n-m}-1, 2^m-1)$. Note how this mirrors the Euclidean Algorithm, subtraction version. – André Nicolas Oct 30 '12 at 16:53
• – punctured dusk Feb 20 '15 at 9:06

## 5 Answers

In general, if $p=\gcd(m,n)$ then $p=mx+ny$ for some integers $x,y$.

Now, if $d = \gcd(2^m-1,2^n-1)$ then $2^m \equiv 1 \pmod d$ and $2^n \equiv 1\pmod d$ so $$2^p = 2^{mx+ny} = (2^m)^x(2^n)^y \equiv 1 \pmod d$$

So $d\mid 2^p-1$.

On the other hand, if $p\mid m$ then $2^p-1\mid 2^m-1$ so $2^p-1$ is a common factor.

And yes, you can replace $2$ with any $a$.

• Thanks, this explains it. It's of course the first part of the proof that was the problem: proving that $d|2^p-1$. – punctured dusk Oct 30 '12 at 16:29
• To anyone who doesn't know about why if $p \mid m, 2^p-1 \mid 2^m-1$. – Postal Model Mar 18 '18 at 10:02

Suppose $x$, $m$ and $n$ are positive integers with $m$ and $n$ coprime. First let us show that $$r = 1 + x + {x^2} + \ldots + {x^{m - 1}}$$ and $$s = 1 + x + {x^2} + \ldots + {x^{n - 1}}$$ are relatively prime. If $d$ is a common divisor of $r$ and $s$, then $d$ is relatively prime to $x$ because $r$ and $s$ are one more than a multiple of $x$. Let $m$ be greater than $n$ (or vice versa) and consider $$r - s = {x^n} + {x^{n - 1}} + \ldots + {x^{m - 2}} + {x^{m - 1}} = {x^n}(1 + x + \ldots + {x^{m - n - 1}})$$ and notice that $d$ divides $r - s$ and so must be a divisor of $1 + x + \ldots + {x^{m - n - 1}}$. Observe that $m - n$ is relatively prime to both $m$ and $n$, so we can likewise use geometric sums which eventually becomes shorter and shorter until we conclude that $d$ must divide 1 i.e. $d = 1$. Now if we let $$d' = \gcd (m',n')$$ with $m' = md'$ and $n' = nd'$, then $m$ and $n$ are coprime and $${2^{m'}} - 1 = ({2^{d'}} - 1)(1 + {2^{d'}} + {2^{2d'}} + \cdots + {2^{(m - 1)d'}})$$ $${2^{n'}} - 1 = ({2^{d'}} - 1)(1 + {2^{d'}} + {2^{2d'}} + \cdots + {2^{(n - 1)d'}})$$ which are geometric sums with $x = {2^{d'}}$ and we showed that $\gcd (r,s) = 1$. This completes the proof.

• "..., so we can likewise use geometric sum which eventually becomes shorter and shorter until we conclude that d must divide 1...". You may mean this: $d|\frac{x^{m-n}-1}{x-1}$. Let $a=m-n$, then we have $d|1+x+...+x^a$ and $d|1+x+...+x^n$, so we can repeat this over and over, letting $b=|n-a|$, ... Right? (Nice alternative solution, but I must confess I prefer Thomas' proof. Anyway, +1) – punctured dusk Oct 30 '12 at 16:39

Hint $$\rm\bmod d\!:\ a^{\large m}\!\equiv 1\equiv a^{\large n}\!\iff order(a)\mid m,n\iff order(a)\mid(m,n)\iff a^{\large (m,n)}\!\equiv 1$$

Therefore $$\rm\ \ d\mid a^{\large m}\!-1,\,a^{\large n}\!-1$$ $$\iff$$ $$\rm\:d\mid a^{\large (m,n)}\!-1,\ \,$$ hence $$\rm\,\ \ (a^{\large m}\!-1,\,a^{\large n}\!-1)\, =\, a^{\large (m,n)}-1$$

Yes, you can say the same when replacing $2$ with an integer $a \geqslant 2$.

Lemma. Suppose that $a \geqslant 2$, $m, n \in \mathbb{N}$ and $\gcd(m, n)=1$. Then $\gcd(a^m-1, a^n-1)=a-1$.

Proof. It is obvious that $(a-1) | \gcd(a^m-1, a^n-1)$. So, we only need to prove that $\gcd(a^m-1, a^n-1) | (a-1)$.

It is well known that if $\gcd(m, n)=1$, then there exist $k, l \in \mathbb{N}$ such that $mk-nl=1$. If is obvious that $(a^n-1)|(a^{nl}-1)$, therefore $$\gcd(a^m-1, a^n-1) | (a^{nl}-1),$$ and for the same reason $$\gcd(a^m-1, a^n-1) | (a^{mk}-1).$$

Now we just observe that $$(a^{mk}-1)-a\cdot(a^{nl}-1) = (a^{nl+1}-1)-(a^{nl+1}-a) = a - 1,$$ therefore $$\gcd(a^m-1, a^n-1) | (a-1),$$ QED.

Now we can prove the main statement: for $b \geqslant 2$ we have: $$\gcd(b^m-1, b^n-1) = b^{\gcd(m,n)}-1.$$ Proof. Set $a = b^{\gcd(m, n)}$, $m'=m/\gcd(m,n)$ and $n'=n/\gcd(m,n)$. Clearly, $\gcd(m',n')=1$, and by the lemma we have $$\gcd(a^{m'}-1,a^{n'}-1) = a-1,$$ which is exactly what we need, QED.

let (m,n)=p, then p|m, and p|n, then $m=m_1p$, $n=n_1p$, $(m_1,n_1)=1$, then $(2^{m_1p}-1,2^{n_1p}-1)=((2^{p})^{m_1}-1,(2^{p})^{n_1}-1)=((2^{p}-1)(.....),(2^{p}-1)(.....))=(2^{p}-1)$

• I don't understand the last step. Why can't $(...)$ and $(...)$ have a common divisor? (I do know what the dots mean) – punctured dusk Oct 30 '12 at 16:12
• The dots are an unspecified polynomial, which is the remainder after factorising out $2^p-1$. They cannot have a common divisorsince otherwise $(m_1, n_1) \neq 0$ (i.e. we could factorise the power of 2 again). – Simon Hayward Oct 30 '12 at 16:15
• So it is a polynomial of the form $2^{m_1}+(\text{lower order terms})$ – Simon Hayward Oct 30 '12 at 16:21
• You've only shown that $2^p-1$ is a common factor, not the greatest common factor. – Thomas Andrews Oct 30 '12 at 16:22
• How do you know that there are no other common factors? You've just asserted without proof that the terms in the ellispes ($\dots$) have no common factor. – Thomas Andrews Oct 30 '12 at 17:59