A useful technique for problems involving Diophantine equations is reducing mod for some well-chosen modulus . This is often a method for proving the nonexistence of solutions: if there are no solutions mod for some , then there are no solutions over the integers. Occasionally it is also useful to narrow down the possible solutions based on solutions mod , but finding a complete set of solutions, when the set is nonempty, will almost always require more advanced techniques.
Solve in positive integers the equation
Taking both sides modulo 4, we get
However, , so
Therefore, since the left hand side is never divisible by 4, the equation has no solutions in positive integers.
Once the appropriate modulus is chosen, the verification that there are no solutions is often a straightforward computation. So the main difficulty in solving these types of problems is deciding which modulus to use.
One guideline that is often helpful (and is used in the introductory example) is to choose moduli that make coefficients of the polynomials vanish. This often simplifies the equation and can help to eliminate variables.
Source: IMO 1982, Problem 4
Show that has no integer solutions .
Look mod . The equation becomes .
If , then , but this is impossible since . Now suppose . Let . Dividing through by gives
and it is easy to check that this has no solutions.
For Diophantine equations which are polynomials in the unknowns, a good choice tends to be an odd prime for which the key exponent divides . This is due to the fact that
of the nonzero elements mod are powers mod (see the wiki on primitive roots for details), and the most helpful and restrictive conditions come from taking a for which that fraction is minimized, which happens when the denominator is .
Show that has no integer solutions.
Look mod : and are in , so is in mod . But . So there are no solutions mod , hence no solutions.
Note that looking mod or mod doesn't help here, because every number is a fifth power modulo either of those two primes.
Another common choice when the exponent is a prime is a power of . As above, only of the integers relatively prime to are powers mod .
For instance, if the exponent is or , it is effective to use moduli of and , respectively, since mod for odd , and mod for any . (These choices can be extended for exponents which are higher powers of 2 as well.)
Source: USAMO 1979, Problem 1
Find all nonnegative solutions in integers to
Look mod . Then or , so the left side is in mod , but the right side is mod . So there are no solutions.
The three cubes problem is the subject of considerable contemporary research: for which values of do integer solutions to
exist? Show that for there are no solutions. The question of whether there is a solution for has recently been solved by Andrew Booker.
Look mod . Cubes are , so their sum is in . Thus any number congruent to mod cannot be written as a sum of three integer cubes. And mod .
The conjecture is that any mod admits solutions, but there are many where solutions have not been found. As of the time of this writing, is the only natural number below 100 for which no solutions have been found.
Sometimes there are solutions mod , but only the "trivial" ones where the variables are . So divides all the variables. Sometimes factoring out leads to a contradiction, and sometimes it leads to a simpler equation.
For more examples, see the wiki on infinite descent.
This section deals with equations with terms of the form , where is a given positive integer. The standard technique for solving this type of equation is manipulating the equation until the form, is obtained. In particular, if is prime, then we can conclude by the fundamental theorem of arithmetic that each factor in the product is a power of that prime. Even if is a composite, it often boils down to casework after considerations of greatest common divisor. We give the following example to illustrate this technique:
Solve for in the following Diophantine equation with prime and positive integers
Notice that we get a difference of squares by substrating on both sides:
From the opening discussion, we know each factor is a power of :
where are non-negative integers that satisfy . Note that .
Subtracting the two equations gives
If , then is a divisor on the lefthand side, so . Also, or else . Thus and we have , which gives the solution .
If , then , which gives the solution .
In conclusion, and are the only solutions to the equation.
A fairly easy category of power equations to solve has the form
where are given positive integers. We will assume that are relatively prime and are positive. For those who are familiar with Zsigmondy theorem, it is easy to see that the equation has a finite number of solutions. Indeed, if we write the equation as , then we know there exists such that for all , has prime divisors that do not divide .
Although this heavy theorem gives us an upper bound of our solution, a more elementary and practical approach uses modular arithmetic. The general method is based on the fact that if a divisor of always divides , then a fixed number must also always divide . This is just a property of order of an element: if and , then . On one hand, we get that is even, which implies is even and gives way to difference of squares. On the other hand, we get that has prime divisors that do not divide . Since , we know there is no solution when this occurs. If neither of these cases happens, then choose a "larger" . We illustrate this in the examples below.
Solve in positive integers.
From , we have . It follows that , which is impossible because . Therefore this equation has no solution.
Find all integers such that
We first get the zero cases out of the way: . Now assume that are positive integers.
The absolute value means we have two cases:
Considering modulo gives us . This result, however, is not strong enough as does not contain prime divisors other than . What do we do now? Well, produces the solution . Now we assume and consider modulo . This gives us and we can stop here because . Thus there is not a solution when .
Note that from we could have proceeded differently using difference of squares, so try this yourself to check with the answers above.
This case can be solved similarly as case 1. Here, however, we cannot conclude one of being even, which means difference of squares is out of the window. I will leave this case as an exercise for interested readers.
What happens if our equation is
Then, in general, we cannot apply the method above because using order requires to be . In these situations, choosing the right modulus often helps by giving us information about . Trying different modulus on the equation should be a priority when solving these equations.
Find all positive integers that satisfy
Case 1: . In modulo , this becomes , so there are no solutions for this case.
Case 2: . In modulo , this becomes , so is odd. Note that is a solution, so taking modulo and would not help. Instead, we can assume that and now we can analyze with modulo :
This contradicts with being odd, what we found earlier. So is our only solution.
Find all positive integers that satisfy
By observation, we can see that satisfies this, but not . We will now show there are no solutions for and . Assume the contrary:
Since , it must follow that . The multiplicative order of is , so . This statement implies .
From this, using the fact that , it must follow that . The multiplicative order of is , so . This statement gives us .
Following from before, using , it must follow that . The multiplicative order of is , so . From this, we gather .
However, this implies that , which is impossible for . Thus, there exist no further solutions for this Diophantine equation.
Therefore, the only satisfying solution is
Try proving the following problems yourself:
Find all positive integer solutions to the Diophantine equation
Find all positive integer solutions of the equation
Hint: Show that are the only solutions.