We’ve all seen the solutions that say “trivial by modulo ” by maxal and a few other prominent AoPS users. How do they come up with these crazy numbers? Well, the trick is not to focus on using only one modulus, in fact it is to use many! Its simply easier to check if the solution works through a computer if you are using only one modulus, which is why these solutions appear so often on AoPS. However, we will explore this process to learn how you can construct these solutions by hand, albeit being a little tedious.
The key intuition to this strategy is to just take modulo a lot of numbers and attempt to derive a contradiction. Its really simple, but there are a few techniques introduced in the following problems which will heavily speed up your approach.
Let’s start first with a simple innocent looking problem.
Problem 1: Find the natural numbers for which is a power of .
Solution: We solve the exponential Diophantine Equation . The solution of is rather daunting but it motivates the solution. First, remark that if the only solutions are . Note take . By modulo one quickly deduces (do you see why this is immediate from being a solution? The fact that for is used here). Now, recall that and that is prime. This means . One can painfully check that as well. This means the LHS is fixed for all values of . Looking modulo we get . Now check the cases to see there are no solutions modulo so we are done.
Remark: Maxal probably would have posted a solution simply stating use modulo , however this is heavily obfuscated in that one gains no intuition from reading such a solution. The motivation of looking modulo is clear since we need to bypass the large solutions. As this tells us , we then find a number for which . There really isn’t a feasible way to do this other than checking primes or remembering Euler’s proof that .
The above solution demonstrates that using various moduli is extremely helpful in solving exponential Diophantine equations. The most important step for picking your moduli is first to pick , where is divisible by at least one of the components of the largest solution but is strictly greater than it (i.e. like if a is part of a solution then picking might work, note that the fact that for we have is essential). Without this step, your solution cannot possibly be correct. Fore the next step, suppose is one of the numbers raised to an exponent in the problem and we have in the problem , and by step one we achieved . Now, choose numbers such that . The intuition behind this is we are trying to draw a contradiction, and this is the only way to draw one. Simply repeat this process many times and you will almost surely get a contradiction. There are lots of shortcuts that can make your mod bashing work a lot faster, but those are mostly picked up with experience and it is very hard to teach them.
Let’s do another example, except the solution does not involve as much bashing. To my knowledge there does not exist a “nice” solution, i.e. does not take modulo “random” numbers.
Problem 2: Solve for positive integers .
Solution:
Suppose . Then I claim only has the solution of . Suppose there is a solution with . Check modulo to deduce . Now check modulo to deduce there are no solutions as the LHS is fixed as , which is not a power of modulo due to being a quadratic residue while not being one. A similar tactic holds to show has no solutions.
Now, suppose . Then remark that by checking modulo we need to be even so let . So let’s solve . Checking modulo we get is even so let . Then:
We get for some .
But then , forcing . Thus we need . But we already showed this only has the solution . Thus it follows the only solution where is with .
Putting every together, we have proven the only solutions are .
We present another problem now.
Problem 3: Find all positive integers such that .
Solution: First, note that is a solution. Now look at the equation modulo and we get that (do you see why we can derive this so quickly?). Now, as we are motivated to look modulo . First checking modulo we get . Then as , it follows we need only check cases. One deduces there are no solutions for those cases, so it follows is the only solution.
As the technique is rather simple, we shall now close this entry with a few problems the readers can try as this technique is learned much more easily through experience than reading solutions.
Problem 4: (India) Solve the equation over the positive integers.
Problem 5: Solve the equation
over the non-negative integers.
Problem 6: (Warning : very computationally heavy) Solve
over the positive integers.
Problem 7: Find all positive integer solutions to .
excellent
exSAllent
great!! Thank you very much!!
exSAlent the SAcond