Notes on Catalan’s Conjecture

Alright so I’ve been a bit busy lately with school and all the homework and such, leaving me with much less time to study and write about mathematics than during the summer. But after a three week break I’m now blogging again. Yay. Anyways.

Catalan’s conjecture is an interesting conjecture in number theory. In this equation

x^a - y^b = 1

The only solution with x, y, a, b > 1 is 3^2 - 2^3 = 1. That is to say, there are no two other powers with a difference of 1.

This was conjectured in 1844, but only recently proven in 2002 by Mihăilescu, so it’s known also as Mihăilescu’s theorem. Mihăilescu’s proof of the theorem uses some very sophisticated techniques, and is beyond the scope of this blog post.

It turns out that Catalan’s conjecture is useful for solving some interesting number theory problems. We can sometimes reduce a problem down to a very specific instance of Catalan’s conjecture, then apply the proof, essentially overkilling the problem. Here are some examples.

Problem 1

Find all triples of positive integers (a,b,c) where

a^2 + 2^{b+1} = 3^c


We look at powers modulo 4. It can be seen that 4 | 2^{b+1} when b is positive, thus 2^{b+1} \equiv 0 \mod 4 and a^2 \equiv 3^c \mod 4.

Next note that 3 \equiv -1 \mod 4 so 3^c \equiv (-1)^c \mod 4. As 3^c is always odd and 2^{b+1} is always even, a^2 must be odd hence a must be odd. Taking the modulo 4, a^2 \equiv 1 \mod 4 (if a \equiv 1 or a \equiv 3). Thus (-1)^c \equiv 1 \mod 4, implying that c is even.

Then c can be written as 2m for some m. The equation is then a^2 + 2^{b+1} = 3^{2m}, and with differences of squares,

2^{b+1} = 3^{2m} - a^2 = (3^m+a) (3^m-a) .

The product of 3^m+a and 3^m-a is a power of 2, so both must themselves be powers of 2. Then there exists x and y where x,y \in \mathbb{N}_0 and x<y such that

3^m - a = 2^x

3^m + a = 2^y

x+y = b+1

Adding the first two yields

2 \cdot 3^m = 2^x + 2^y

Putting x=0 causes a parity error. If x \geq 2 then the RHS is divisible by 4 while the LHS clearly isn’t. This makes x=1, giving

3^m = 1 + 2^{y-1} .

This is a case of Catalan’s conjecture. The only solutions to (m,y) are (1,2) and (2,4). Now we can just substitute the solutions for (m,y) to get solutions for (a,b,c). They are (1,2,2) and (7,4,4).

Problem 1a

Here is a very similar problem: find all integer solutions to

3^a + 4^b = c^2

The solution is left to the reader.

Hint: rewrite as a difference of squares and subtract

Problem 2

Find all triples (x,y,n) of non-negative integers such that

x^n = y^4 + 4


Obviously n cannot be 0. We first look at n=1. Then, x = y^4 + 4, and any triple (y^4+4, y, 1) satisfies the equation.

Next we consider when n=2. Then x^2 = y^4 + 4, or as a difference of squares, (x+y^2) (x-y^2) = 4. The solution then is x=2 and y=0, or (2,0,2).

Now we try n>2. Suppose that y is even. Then in the equation x^n = y^4 + 4, 4 | y^4 and 4 | RHS so 4 | LHS, thus x is even. Then x^n = 2^n k^n for some k, and it is clear that n \leq 2, which is a contridiction.

So y must be odd. The RHS, y^4 + 4, can be written as y^4 + 4y^2 + 4 - 4y^2, or (y+2+2y)(y+2-2y). This gives us

x^n = (y^2 + 2y + 2) (y^2 - 2y + 2) .

We claim that for odd y, y^2 + 2y + 2 \perp y^2-2y+2. Let k be the GCD of y^2+2y+2 and y^2-2y+2 so that k | y^2+2y+2 and k | y^2-2y+2. Then k|4y (the difference). As y^2+2y+2 is odd, and k divides it, k must be odd so k|y. But y^2+2y+2 = y(y+2)+2 so k|y and k|y(y+2)+2, thus k=1.

Hence for some integers u and v where uv=x,

u^n = y^2 + 2y + 2

v^n = y^2 - 2y + 2

Alternatively, u^n = (y+1)^2 + 1 and v^n = (y-1)^2 + 1.

From Catalan’s conjecture, the equation x^a - y^2 = 1 with a>2 has no solutions other than 1^n-0^2=1. But we have the simultaneous equations u^n - (y+1)^2 = 1 and v^n - (y-1)^2 = 1. This is clearly impossible.

Thus the only solutions are (y^4+4,y,1) and (2,0,2).