Is the only solution of the equation where are integers?
Alright, buckle up. I'm going use this little problem as an excuse to introduce the wonders of Algebraic Number Theory, at least a small portion of it.
Ready?
Ok. We're trying to solve
3^n = m^2+2
where m,n are positive integers (the question posits "integers", but it's easy to see that n must be positive and m might as well be assumed to be positive). Forgive my change of variable names, it's a bit more common this way.
Let's make a few quick observations: First of all, the left hand side is always odd, therefore the right hand side must also be odd, which means that m must be odd. Remember that. We will need it, down the line.
Another thing we should do when looking at such equations is just try out some small numbers. We immediately find two solutions:
3^1 = 1^2+2
3^3 = 5^2+2.
Further attempts don't seem to yield anything, so we are led to hypothesize that these are the only solutions. This turns out to be the case, but we have some work to do in order to prove it.
Theorem: If m,n are positive integers and 3^n=m^2+2 then either (m,n)=(1,1) or (m,n)=(5,3).
Note: if you're familiar with basic notions of algebraic number theory, the first half of the proof is quite short and straightforward. The long tale below is not meant to be a compact proof, but rather a motivated investigation into this equation and the way algebraic number theory is naturally born as a result of such investigations.
Step 1: Factoring the Right Hand Side
Consider the equation again:
3^n = m^2+2.
On the left we have a product (of 3's), and on the right we have a sum. It's hard to compare products and sums, so our first goal is to turn the expression on the right into a product as well.
Trouble is, we don't know how to factor m^2+2. In school you've learned that m^2-1 = (m-1)(m+1), for instance, but you may have been told that m^2+2 is "irreducible".
Well, it is — over the rational numbers. But if we introduce the complex number \sqrt{-2}, then m^2+2 factors right away:
\displaystyle m^2+2 = (m+\sqrt{-2})(m-\sqrt{-2}).
We are therefore led to switch the domain of discourse from mere integers into the realm of numbers of the form a+b\sqrt{-2} where a,b are integers.
Why a+b\sqrt{-2} and not some other expression? And why do we insist that a,b should be integers?
Well, we need \sqrt{-2} to factor our right hand side, and we want to do arithmetic — we're going to need to add, subtract and multiply. So our best bet is to start with the integers we know and love, throw in \sqrt{-2}, and then keep adding and subtracting and multiplying things until we stop finding any new numbers. The result is the set of numbers a+b\sqrt{-2} where a,b are arbitrary integers.
You can easily verify that adding, subtracting and multiplying two numbers of this form yields another number of the same form. For example,
\displaystyle (2+3\sqrt{-2})(4+5\sqrt{-2}) = 8+10\sqrt{-2}+12\sqrt{-2}+15\cdot (-2) =
= -22+22\sqrt{-2}.
Like the integers, these numbers cannot always be divided by each other. For example, we just saw that -22+22\sqrt{-2} is divisible by 4+5\sqrt{-2}, and the quotient is 2+3\sqrt{-2}. But you can see that-21+22\sqrt{-2} is not divisible by 4+5\sqrt{-2}, because there will be a remainder of 1 left over. To be sure, try solving (a+b\sqrt{-2})(4+5\sqrt{-2})=-21+22\sqrt{-2} and observe that no integers a,b make this true.
If we allow a,b to be arbitrary real or complex numbers, we can no longer do arithmetic. Everything can be divided by everything else and we have too much freedom. Our goal is to prove that a certain equation has no solutions in integers other than the ones we know. We should stay as close to integers as we can.
The set of numbers of the form a+b\sqrt{-2} is an example of a "commutative ring", which is a collection of things that can be added, subtracted and multiplied with the usual rules of arithmetic still applying (for instance x(y+z)=xy+xz.) This particular ring is named the ring of integers of \mathbb{Q}(\sqrt{-2}), or \mathbb{Z}[\sqrt{-2}], but we will simply call it R.
As soon as you come across a ring like R you should immediately investigate its number theoretic properties: its primes, its units (things that can be multiplied by something to yield 1), whether it has unique factorization, etc. We will investigate these properties as we need them here, because one of the things I hope to do is reveal why number theorists care about these things.
Step 2: Oh look, the Left Hand Side got Factored as well
Let's go back to our equation. It now looks like this:
\displaystyle 3^n = (m+\sqrt{-2})(m-\sqrt{-2}).
This looks very promising. Why? Well, imagine we were working with the ordinary integers, and we were looking at the equation
3^n = ab.
We can immediately conclude from this that a,b must both be powers of 3. Right? Neither of them can have any other prime factor; if a were divisible by 17, then the product ab would also be divisible by 17, but 3^n is not divisible by 17, obviously. So we can conclude that a,b are both powers of 3.
Can we do the same here? Hopefully not! We are looking at 3^n = (m+\sqrt{-2})(m-\sqrt{-2}) and neither of the things on the right looks anything like a power of 3. That would have been ok if we thought our equation has no solutions at all, but it does! So how come, for example, that 3^1=1^2+2 works? Does it not contradict our factorization? Let's see what happens when n=m=1:
\displaystyle 3^1 = (1+\sqrt{-2})(1-\sqrt{-2}).
Oh. Bummer. Over the ordinary integers, 3^n=ab implies that a,b must be powers of 3, but in our ring R this obviously is no longer the case. You see, when we elevated the discussion from integers into R, we managed to factor not only our right-hand side, but inadvertently our left-hand side as well...
Indeed,
\displaystyle 3 = (1+\sqrt{-2})(1-\sqrt{-2})
so
\displaystyle 3^n = (1+\sqrt{-2})^n(1-\sqrt{-2})^n.
Ok. So really, our equation in R is
(1+\sqrt{-2})^n(1-\sqrt{-2})^n = (m+\sqrt{-2})(m-\sqrt{-2}).
This is still very promising. On the left we have a product (of nth powers), and on the right we have a product. It looks like this:
A^n B^n = XY.
It would be really nice if we could argue that X must be A^n and Y must be B^n (or vice versa). If that were so, we would know that (1+\sqrt{-2})^n = m+\sqrt{-2}, and we could investigate the powers of 1+\sqrt{-2} to see that they are very rarely of this form. This will indeed be our final step, but first we have to ensure that we can actually draw that conclusion.
Discussion: When One Product Equals Another
If you have one product that equals another product, can you conclude that the factors are the same?
Well, it's not that simple.
Suppose I tell you that AB=XY. Can you infer that X=A and Y=B (or the other way around)? There are several ways this can fail; some pretty obvious, some more subtle.
One obvious way is this: consider 3 \times 4 = 2 \times 6. Two different pairs of numbers have the same product. How does this happen? Well, the number 12 can be broken down into prime factors as 12=2 \times 2 \times 3, and we can group these factors in different ways to get (2 \times 2) \times 3 or 2 \times (2 \times 3). So, if you just know that AB = XY, you should be worried if A,B,X,Y can further be broken down into products of smaller things.
What if the numbers involved cannot be broken down into products? There's another problem: every number can be written as a product in silly ways. For example, if I told you that 2 \times 3 = XY, despite the fact that 2 and 3 are prime, you still couldn't infer that X,Y=2,3. Maybe X,Y=1,6? Or X,Y=-1, -6? We have to ensure that our numbers can't be units, which are things like 1 or -1 that can be multiplied together to make 1's. We can always plug 1's and -1's into products.
Ok, but there's another, even most subtle difficulty. suppose I tell you that AB=XY, and I promise you that none of these numbers is a unit, and that all of these numbers are irreducible, meaning they cannot further be split into products. Now we should be able to conclude that A,B and X,Y are the same numbers, right? Right?
Well, yes... provided unique factorization holds true. This is a very familiar property of ordinary integers: When you write down a number, such as 92, as a product of primes, as in 92 = 2 \times 2 \times 23, you know that there's one and only one way to do that. You can't find some other way of writing 92 as a product of primes, as in "92 = 7 \times 13". This last equality is false, thankfully. But how do we know this can't happen?
Incredibly, when we venture out beyond the integers, it can happen. For example if we work with the numbers a+b\sqrt{-5} where a,b are integers, then 2 \times 3 = (1+\sqrt{-5})(1-\sqrt{-5}), and all of the numbers here are irreducible: they cannot be broken down into products any further. In the ring \mathbb{Z}[\sqrt{-5}], unique factorization doesn't hold.
(In 1847, a guy called Gabriel Lamé announced a proof of Fermat's Last Theorem. It was wrong, and the reason it was wrong was that he implicitly assumed unique factorization holds in rings where it does not).
Incidentally, when unique factorization fails, we have to make a careful distinction between "irreducible numbers" which can't be written as products and "prime numbers" which divide a product only when they divide one of the factors. Luckily, in our ring R, this will not be a concern.
Step 4: Analyzing the Product in Our Ring
Let's go back to our equation.
(1+\sqrt{-2})^n(1-\sqrt{-2})^n = (m+\sqrt{-2})(m-\sqrt{-2}).
We want to infer that (1+\sqrt{-2})^n = m \pm \sqrt{-2}, one of the factors on the right. As we shall see, this is a very powerful conclusion.
So we are faced with the following challenges:
1. Show that 1+\sqrt{-2} and 1-\sqrt{-2} are irreducible (or "primes", which in our ring is the same thing). This means they cannot be broken further, so the right hand side must be a certain grouping of n copies of each.
2. Show that m+\sqrt{-2} and m-\sqrt{-2} are relatively prime, meaning they have no common factors, and that they are not units. If we show this, then each of them must be the product of n copies of one of the irreducible elements on the left.
3. Finally, we must show that the numbers in R have unique factorization into primes.
To do all these things, there's a very useful trick called the norm.
If you're familiar with complex numbers, you know that each complex number z has a size or absolute value |z|, and one nice thing about it is that the size of a product is the product of the sizes. This is helpful because it lets us show that certain products can't work because the sizes don't work. This is often easier.
Even if you're not familiar with complex numbers, you can directly show that defining the norm N(a+b\sqrt{-2}) = (a+b\sqrt{-2})(a-b\sqrt{-2}) = a^2+2b^2 achieves the following things:
- For any number x in R, the norm N(x) is an ordinary non-negative integer.
- For any two numbers x,y in R, the norm satisfies N(xy)=N(x)N(y). The norm of a product is the product of the norms.
- Therefore, if x divides y then N(x) divides N(y).
- Contrariwise, if N(x) doesn't divide N(y) then x does not divide y.
Armed with this device, we can quickly dispose of our challenges.
For starters, what are the units in R? Luckily, the only ones are the good old 1 and -1. Why? Well, if xy=1 then N(x)N(y)=1. But the norm is a non-negative integer, which means that N(x)=N(y)=1. When does a^2+2b^2=1? Obviously, b=0 and a = \pm 1 are the only solutions.
(This is really fortunate. In other rings, there are many non-obvious units, like for example (17+12\sqrt{2})(17-12\sqrt{2})=1. This is one of the main reasons why imaginary quadratic number fields are so much easier than real quadratic number fields. Units are a major nuisance).
Now, what about primes? Determining the primes completely takes some work, but there's a simple condition that helps: if a number has a prime norm, it must be irreducible. For if it were reducible, its norm would be the product of the norms of its factors.
Since N(1+\sqrt{-2})=3 and N(1-\sqrt{-2})=3, both of these numbers are irreducible. This is great: the left hand side of our equation is a genuine prime decomposition. There are no further hidden factors.
Next: why are m+\sqrt{-2} and m-\sqrt{-2} relatively prime? Imagine that some prime number p in R divided both of them. Then it would also divide their difference, which is 2\sqrt{-2} = (\sqrt{-2})^3. The only prime which divides (\sqrt{-2})^3 is \sqrt{-2}, a number of norm 2. But the norm of m+\sqrt{-2} is m^2+2, and if you scroll up to the distant beginning of this answer you'll remember that m is odd, so m^2+2 is odd, so it cannot be divisible by 2. Success! The prime \sqrt{-2} cannot divide m+\sqrt{-2}, and it is the only candidate for dividing both it and m-\sqrt{-2}. So, the factors on the right hand side of our equation are relatively prime, and none of them is a unit (look at their norms), so we can finally conclude that one of them must be none other than (1+\sqrt{-2})^n itself.
But wait — we still haven't proved that R has unique factorization into primes. If it doesn't, nothing we said makes sense. I'll need to leave this part out for now since this answer is horribly long as it is; suffice to say that this follows quickly from the fact that we have in R an analog of the idea of "division with remainder", and the norm of the remainder is always smaller than the norm of the divisor. From this property we can infer that it has unique factorization much like we do this for ordinary integers.
Step 5: Powers of 1+\sqrt{-2}
We've made an important discovery: One of m+\sqrt{-2} or m-\sqrt{-2} must be (1+\sqrt{-2})^n. How does this help? Instead of our original equation, which was
3^n=m^2+2,
we now have
\displaystyle \left(1+\sqrt{-2}\right)^n = m \pm \sqrt{-2}.
Why is that progress? Here's the thing: first of all, on the right we no longer have m^2, just m. That's a much easier thing to work with; we don't need to worry about it being a square or not. Secondly, we can start looking at powers of 1+\sqrt{-2}, and see whether they do or don't look like something plus or minus \sqrt{-2}. When they don't, the equation has no solution.
Those powers are very concrete numbers. We can calculate them successively quite simply, by multiplying each one by 1+\sqrt{-2} to get the next one:
(1+\sqrt{-2})^1 = 1+\sqrt{-2}
(1+\sqrt{-2})^2 = -1+2 \sqrt{-2}
(1+\sqrt{-2})^3= -5+\sqrt{-2}
(1+\sqrt{-2})^4 = -7 -4 \sqrt{-2}
(1+\sqrt{-2})^5 = 1 - 11 \sqrt{-2}
(1+\sqrt{-2})^6 = 23 - 10 \sqrt{-2}
We observe two powers here which indeed have a mere \sqrt{-2} as the b part: n=1 and n=3. This is excellent news - those are exactly the powers that yield solutions to our original equation. The other powers all have much larger coefficients in front of the \sqrt{-2}. Therefore, our goal is now to prove than when n>3, the number
\displaystyle \left(1+\sqrt{-2}\right)^n = a_n + b_n \sqrt{-2}
has b_n \neq \pm 1. For example, b_4 = -4, b_5 = -11, and so on; all of these numbers, we must show, are never 1 or -1 (except for b_1 and b_3).
Showing that b_n can't be -1 is relatively easy. If you write down the sequence b_n and consider the residues modulo 11, you get 0, 1, 2, 1, 7, 0, 1, 2, 1, 7, \ldots. It's not hard to show using induction that this is periodic behavior continues forever. Since the residue -1 (or 10) modulo 11 never shows up, b_n can never be -1. From here on we will focus on showing that b_n can't be 1 as soon as n > 3.
Since reduction mod 11 was so useful, we may wonder about reducing the sequence modulo other things. Playing around with various options you may find that the reductions modulo 2, 4, 8, 16 etc. seem promising: the sequence b_n modulo 2^r seems to always be periodic with period 2^r, and the residue 1 only shows up in positions 1 and 3 in the period. As you increase r, the positions of the 1's move farther and farther out, and if we can prove that this is the case, we're done.
(Note: I am indebted to math.stackexchange user Achille Hui for helping me complete this part of the solution).
Let's apply the binomial theorem to the expression (1+\sqrt{-2})^n. We get
\displaystyle \left(1+\sqrt{-2}\right)^n = \sum_{k=0}^n \binom{n}{k}\sqrt{-2}^k.
In this sum, when k is even we get an ordinary integer, and when k is odd we get an integer times \sqrt{-2}. We only care about those, because we only care about the b_ns. So we can write k=2t+1 and obtain the following formula for our b_ns:
\displaystyle b_n = \sum_{t=0}^{\lfloor \frac{n-1}{2} \rfloor} \binom{n}{2t+1}(-1)^t2^t.
The strange upper bound of this sum is simply meant to ensure that 2t+1 doesn't exceed n. Don't worry too much about it. We can write this in a more friendly way like this:
b_n = \binom{n}{1} - 2\binom{n}{3} + 4\binom{n}{5} - 8\binom{n}{7} - \ldots.
This is just an alternating sum of binomial coefficients multiplied by some powers of 2. The scary part about this formula is that it gets longer and longer as n grows. But there's hope: remember we thought it would be useful to consider the residues of b_n mod powers of 2. If we're looking at things mod 32, everything in this formula except the first five elements vanishes. In fact, if we're lucky and the binomial coefficients contribute more powers of 2, then even more elements disappear. This will be our proof strategy.
First of all, if n is even, everything on the right is even, so b_n is even and cannot be equal to 1. So we may assume that n is odd.
Since n is odd, it is something even plus 1. The "something even" is divisible by 2 a certain number of times, and since powers of 2 are important here we need to know exactly how many times. So we write n=2^r u+1 with u odd. Now, when t>0,
\binom{n}{2t+1} = \frac{n(n-1)}{2t(2t+1)}\binom{n-2}{2t-1}.
In the numerator we have an odd number n and then an even number n-1 which is divisible by 2 r times. In the denominator we have 2t+1, which is odd, and 2t which is even and we have no idea just how even, meaning how many powers of 2 it contains. But remember that in the formula for b_n there's another ingredient, those powers of 2 which are represented by 2^t. As soon as t is more than 2, 2^t has more 2's than 2t. In other words, the
expression
2^t\binom{n}{2t+1}
is divisible by 2 at least r+1 times: r times come from n-1 and at least one more from \frac{2^t}{2t}.
So, if we work modulo 2^{r+1}, we can ignore everything with t>2, that is everything except the very first few terms:
b_n \equiv \binom{n}{1}-2\binom{n}{3}+4\binom{n}{5} \pmod{2^{r+1}}.
The good news here are that our long formula has been reduced to just three terms. Three terms we can handle! In fact at this point, a routine check shows that if r>1, that is if n-1 is divisible by at least 4, then b_n cannot equal 1 modulo 2^{r+1}, which means that it cannot be equal to 1, period.
If however r=1, this argument isn't enough. But if n-1 isn't divisible by 4, then n-3 is, so we write n=2^r u+3 (those are now different u and r) and we repeat the argument. I'll leave the details to you, gentle reader who made it all the way down here.
Putting all these pieces together, we've shown that the sequence b_n never returns to 1 (or -1) once n > 3. This means that (1+\sqrt{-2})^n is never of the form m \pm \sqrt{-2} for n>3, which using the discoveries we made in the ring R means that 3^n cannot equal m^2+2 once n>3. And this, finally, proves the theorem.
QED