Olympiad Diophantine Equation

This was one of my practice olympiad problems I had to do. It was pretty tough. I struggled with it for most of the time until I got a mediocre solution with a lot of holes in it. However, it was a rewarding experience. You don't learn how to tackle the tough problems unless you actually get engaged with one. I'll be explaining the complete solution.



I forgot to include that m and n are positive btw.

It's pretty intimidating. What's so intimidating about it? For one, the variables in the exponents make the equation funky looking. Second, at first glance, there's absolutely nothing we can do with it. There's nothing to factor. We do notice the square on the right hand side of the equation for it, which I don't show here. Does that suggest a difference of squares? Only if one of m or n are even. Can we show that it is? If we can, it's certainly not intuitive how.

By the way, before I forget, for any Diophantine equation, try playing around with small numbers to see if you can find any solutions. Here, a fairly obvious solution is (4,2), as this yields one side of a Pythagorean triple. Whether or not you can find any solutions will help you understand where you might need to steer your proof. The fact that both m and n are even in this solution suggests even more so that our previous idea is on the right track.

So back to the problem. We have an idea of where to go. Seeing as I don't have any better ideas, it's worth exploring. How do we show that m or n is even? We can start by breaking down the equation using mods. What does this mean? It means we look at the equation under as many mods as we see fit. What sort of mods should jump out right away? 2 and 3 might come in handy later. Because the quadratic residues are so limited mod 4 and 8, it will probably be helpful examining the equation under these. And if you don't know what quadratic residues are, I'll side track to explain them:

How many solutions are there to n = 3 mod 4? Obviously an infinite amount, whenever n is in the form 4m + 3. This is basic modular notation.

How many solutions are there to n^2 = 3 mod 4? Turns out that there are none. How can we show this?

Every number will be congruent to either 0, 1, 2, or 3 mod 4. Therefore, every number in the form n^2 will be congruent to o^2, 1^2, 2^2, or 3^2 mod 4. This table explains it pretty well:





We can take this idea and apply it to a number of different things. The powers of an integer modulo n, cubes modulo n, etc. Lets look at the powers of 2 and 3 modulo 4:




We can show by induction that all odd powers of 3 =3 mod 4, and all even powers =1 mod 4. It's pretty simple to do so I won't bother explaining it. We can make a similar argument for powers of 2 where the exponent is greater than 1, it will be congruent to 0 mod 4.

Since all squares are congruent to 0,1 mod 4, then we only have two cases for our powers of 2 and 3: 2 reduces to 2 mod 4 (or in other words, our power of 2 is 1), and 3 reduces to 3. Or, 2 reduces to 0 mod 4, and 3 reduces to 1. Playing around with smaller numbers for the first case suggests that it won't work out, and we can easily prove it:




We can reduces all squares modulo 3 to find that they're congruent to 0,1 mod 3. However, its easy to see that the expression is always congruent to 2 mod 3.

So we can conclude that n must be even. Let n = 2x. Then we can subtract and factor:




Clearly both factors must be nonegative powers of two. Writing some equations and subtracting them yields:




Taking both sides mod 2 and remembering that x is a positive integer, we see that our power of two must be 1, giving us the equation:




Trying small values of x, we quickly see x = 1 works, meaning n = 2. Putting this back into our original equations, we can determine that m = 4. We now have one solution, (4,2).

If we try values of x larger than 1, it seems as if the RHS of that equation will never be a power of two. Lets try to prove it. We try looking at it modulo 8, because for x > 1, the RHS will always be greater than 8, and since its supposed to be a power of two, must be divisible by 8:



Again we can induct to show that it's always congruent to 3 or 1 modulo 8. And since we're adding 1, the LHS is congruent to 4 or 2 modulo 8. So it'll never be a power of 2 for x > 1. Thus, our only solution is (4,2).

That problem was pretty mind numbing, mainly because of all the modular residues we had to examine. However, it is a great example of how to break down number theory problems using modular arithmetic. To sum everything up, here's my main approach for diophantine equations that don't like immediately solvable by some method:

1) Quickly look for some solutions
2) Look for ways to factor it
3) Examine it under different modulos to narrow down the possibilities of the variables.

Also, here are the general tactics that ACoPS proposes:

- Is the problem in "simple" form? Always make sure that you have divided out all common factors, or assume the variables share no common factors.

-Do there exist solutions? Sometimes you cannot actually solve the equation, but you can show that at least one solution exists.

-Are there no solutions? Quite frequently, this is the first question to ask. As with argument by contradiction, it is sometimes rather easy to prove that an equation has no solutions. It is always worth spending some time on this question when you begin your investigation.
(I'll add here that this is why you should look for some quick solutions first, so you don't get caught up trying to prove that there are no solutions whatsoever)

-Can we find all solutions? Once one solution is found, we try to understand how we can generate more solutions. It is sometimes quite tricky to prove that the solutions found are the complete set.

Oomph. So how are you? I'm visiting WPI tomorrow and monday, I'm planning on visiting RPI in november, and I'm also going to plan a trip to MIT sometime before winter. I'm not as stressed out about it anymore, as I took a step back and realized that once I switch from my retarded french guidance counselor I'll be better off. And now I'm very tired and while I would love to do more math, I have a bunch of tests to study for next week.