gcd(2^m − 1, 2^n − 1): the proof, and how to spot it

Nobody gets stuck on this problem because the algebra is hard. Every line of the proof is a factorisation you already know. People get stuck because they try to attack $2^m - 1$ and $2^n - 1$ as numbers, factoring them, hunting for primes, and the numbers are the wrong thing to look at.

The whole proof is one observation: the Euclidean algorithm on the exponents produces the Euclidean algorithm on the numbers, step for step. Once you see that, the identity

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

stops being a fact to memorise and becomes something you can rebuild in two minutes in an exam. This guide shows the proof, a second proof by orders, and the problems where it quietly does the work.

Believe it first

Take $m = 18$ and $n = 12$. Then $2^{18} - 1 = 262143$ and $2^{12} - 1 = 4095$. Run Euclid on those: $262143$ leaves remainder $63$ on division by $4095$, and $4095 = 63 \cdot 65$, so the gcd is $63$.

Now look at the exponents. $\gcd(18, 12) = 6$, and $2^6 - 1 = 63$. Same answer.

Look closer at that first remainder. Euclid on the exponents says $18 = 1 \cdot 12 + 6$, remainder $6$. Euclid on the numbers gave remainder $63 = 2^6 - 1$. The remainder on the numbers is $2$ to the remainder on the exponents, minus one. That is not a coincidence, and it is the entire proof.

The one fact you need

If $d$ divides $n$, then $2^d - 1$ divides $2^n - 1$. Write $n = dk$ and $x = 2^d$; then $2^n - 1 = x^k - 1$, and $x - 1$ always divides $x^k - 1$, because

$$x^k - 1 = (x - 1)(x^{k-1} + x^{k-2} + \dots + 1).$$

You have probably met this already. It is the same factorisation that shows if $2^n - 1$ is prime then $n$ is prime: a composite exponent hands you a proper factor for free.

The proof

Take $m \ge n$ and divide: $m = qn + r$ with $0 \le r < n$. Split off the remainder in the exponent:

$$2^m - 1 = 2^r\left(2^{qn} - 1\right) + \left(2^r - 1\right).$$

Expand the right side if you doubt it: $2^{r+qn} - 2^r + 2^r - 1$. Now $n$ divides $qn$, so by the fact above $2^n - 1$ divides $2^{qn} - 1$. That kills the first term modulo $2^n - 1$, leaving

$$2^m - 1 \equiv 2^r - 1 \pmod{2^n - 1}.$$

And a gcd does not change when you replace one number by its remainder modulo the other. So

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

The pair of exponents went from $(m, n)$ to $(n, r)$, which is exactly one step of Euclid on $m$ and $n$. Repeat. The exponents follow Euclid's algorithm all the way down until the remainder is $0$, at which point the exponent pair is $(\gcd(m,n), 0)$, and the numbers are $2^{\gcd(m,n)} - 1$ and $2^0 - 1 = 0$. The gcd of anything with $0$ is itself. Done.

On the example: $(18, 12) \to (12, 6) \to (6, 0)$ on the exponents, and $(262143, 4095) \to (4095, 63) \to (63, 0)$ on the numbers. Every exponent $e$ on the left becomes $2^e - 1$ on the right.

This is the problem in the archive, and when you write it up, the marker is looking for two things: the congruence with a reason attached, and an honest ending at remainder $0$ rather than "and so on".

A second proof, by orders

The first proof is the one to write. This one is worth knowing because it generalises to problems where Euclid has nothing to run on, and it is pure modular thinking.

Let $g = \gcd(2^m - 1, 2^n - 1)$. Then modulo $g$ we have both $2^m \equiv 1$ and $2^n \equiv 1$. Any power of $2$ built by adding and subtracting multiples of $m$ and $n$ is therefore also $\equiv 1$. By Bézout, $\gcd(m,n)$ can be written as $am - bn$ with $a, b \ge 0$ (for $18$ and $12$: $18 - 12 = 6$). So $2^{am} \equiv 2^{bn} \cdot 2^{\gcd(m,n)}$, and since both $2^{am}$ and $2^{bn}$ are $\equiv 1$, we get $2^{\gcd(m,n)} \equiv 1 \pmod g$. That is, $g$ divides $2^{\gcd(m,n)} - 1$.

The other direction is the one fact from earlier: $\gcd(m,n)$ divides both $m$ and $n$, so $2^{\gcd(m,n)} - 1$ divides both numbers, hence divides $g$. Each divides the other, so they are equal.

How to spot it next time

The identity hides behind several disguises. Reach for it when you see:

• Two numbers one less than a power, same base, like $a^m - 1$ and $a^n - 1$. Nothing about $2$ is special. The same proof gives $\gcd(a^m - 1, a^n - 1) = a^{\gcd(m,n)} - 1$ for any integer $a \ge 2$.
• Repunits. $111\ldots1$ with $k$ ones is $\tfrac{10^k - 1}{9}$, so the gcd of the repunits with $m$ and $n$ ones is the repunit with $\gcd(m,n)$ ones. The repunits with $12$ and $18$ ones share exactly $111111$.
• "Show these are coprime." Since $2^1 - 1 = 1$, the numbers $2^m - 1$ and $2^n - 1$ are coprime exactly when $m$ and $n$ are. Take $2^p - 1$ over all primes $p$: they are pairwise coprime, so each one contributes a prime the others lack, and that is a proof there are infinitely many primes.
• An exponent that is clearly a gcd or lcm in disguise. If the answer to a question is $2^6 - 1$ and the inputs mention $18$ and $12$, you now know where the $6$ came from.

What to write in the exam

Four lines are enough:

1. Divide with remainder: $m = qn + r$.
2. State the congruence $2^m - 1 \equiv 2^r - 1 \pmod{2^n - 1}$, with the factorisation as its reason.
3. Conclude the gcd is unchanged when $(m, n)$ becomes $(n, r)$.
4. Say the process is Euclid's algorithm on the exponents and finishes at $(\gcd(m,n), 0)$.

If you can produce those four lines from memory, you do not need to remember the formula. You need to remember that exponents run Euclid too.