# Catalan’s conjecture

Posted by Jason Polak on 25. November 2017 · Write a comment · Categories: number-theory · Tags: ,

If you write out all the $n$th powers of natural numbers for $n \gt 1$ (“higher powers”) in increasing order you get a sequence like this:

1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, …

If you keep computing more numbers in this sequence, once in a while you’ll find two consecutive terms quite close together. For instance:
$$1138^2 – 109^3 = 15$$
But no matter how far you go, it seems that the only two terms that are just one apart are 8 and 9. Eugène Catalan conjectured that 8 and 9 are the only two numbers in this sequence just one apart, and this conjecture became known as Catalan’s conjecture.

If you only allowed powers of 2 and 3 in the sequence, then the proof that 8 and 9 are the only consecutive powers is not difficult. In fact, it just requires the difference of squares identity: $a^2 – b^2 = (a – b)(a + b)$. Let’s see how it works! If only powers of 2 and 3 are allowed, then the question becomes: when is it possible that $3^m – 2^n = 1$ or that $2^n – 3^m = 1$?

Let’s suppose $3^m – 2^n = 1$. If this happens, just by checking the list we gave we see that at the very least, we can say that $n\geq 3$. So that means that $3^m – 1$ is a multiple of 8. What are the possible remainders when $3^m – 1$ is divided by 8? Well, $3^2 – 1= 8$. And to get from $3^m – 1$ to $3^{m+1} – 1$ we apply the map $x\mapsto 3x + 2$. So, the remainders of $3^m – 1$ from $m=2$ onwards look like $0,2,0,2,\dots$. In other words if $m\geq 2$ then $3^m – 1$ is divisible by $8$ exactly when $m$ is even. So we can conclude that $m = 2k$ for some $k$. This is where we use the difference of squares identity.

Now we have the equation $2^n = 3^{2k} – 1 = (3^k-1)(3^k + 1)$. By unique factorisation we can write
$$3^k – 1 = 2^\ell \\ 3^k + 1 = 2^{n – \ell}$$
for some $\ell \lt n$. Subtracting these two equations gives:
$$2 – 2^\ell(2^{n-2\ell} – 1).$$
That means that $\ell = 1$ and $n – 2\ell = 1$ so that $n = 2$. Therefore, the only possibility if the two consecutive powers are $2^n\lt 3^m$ is 8 and 9. You can apply pretty much the same reasoning for the case $3^m\lt 2^n$ to show that there are no such solutions. Thus 8 and 9 are the only possibilities.

So we see that 8 and 9 are the only consecutive powers in the sequence of higher powers of 2 and 3. But remember, Catalan’s conjecture was that these are the only consecutive powers if we include the higher powers of all natural numbers.

In fact this conjecture was only proven recently by Preda Mihăilescu in 2003. The proof is accessible to someone with a good foundation of algebraic number theory and a streamlined presentation has been written by René Schoof in his book Catalan’s Conjecture (Springer-Verlag, 2008), and runs just over 100 pages.