Diophantine Equations - Modular Arithmetic Considerations
A useful technique for problems involving Diophantine equations is reducing mod \( n \) for some well-chosen modulus \( n \). This is often a method for proving the nonexistence of solutions: if there are no solutions mod \( n \) for some \( n \), then there are no solutions over the integers. Occasionally it is also useful to narrow down the possible solutions based on solutions mod \( n \), 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
\[x^2+4x+1=4y^2.\]
Taking both sides modulo 4, we get
\[x^2+1\equiv 0 \pmod 4.\]
However, \(x^2\equiv 0,1 \pmod 4\), so
\[x^2+1\equiv 1,2 \pmod 4.\]
Therefore, since the left hand side is never divisible by 4, the equation has no solutions in positive integers. \( _\square\)
Choice of Modulus
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 \( x^3-3xy^2+y^3 =2891 \) has no integer solutions \( (x,y) \).
Look mod \( 7 \). The equation becomes \( x^3-3xy^2+y^3 \equiv 0 \pmod{7} \).
If \( x \equiv 0 \pmod{7}\), then \( y \equiv 0 \pmod{7} \), but this is impossible since \( 7^3 \nmid 2891 \). Now suppose \( x \not\equiv 0 \pmod{7}\). Let \( u \equiv \frac yx \pmod{7}\). Dividing through by \( x^3 \) gives
\[1-3u^2+u^3 \equiv 0 \pmod{7}\]
and it is easy to check that this has no solutions. \(_\square\)
For Diophantine equations which are polynomials in the unknowns, a good choice tends to be an odd prime \( p \) for which the key exponent divides \( p-1 \). This is due to the fact that
\[\frac1{\text{gcd}(k,p-1)}\]
of the nonzero elements mod \(p\) are \( k^\text{th}\) powers mod \( p \) (see the wiki on primitive roots for details), and the most helpful and restrictive conditions come from taking a \( p \) for which that fraction is minimized, which happens when the denominator is \(k\).
Show that \( x^5+113y^5 = 137 \) has no integer solutions.
Look mod \( 11 \): \( x^5 \) and \( y^5 \) are in \( \{-1,0,1\} \), so \( x^5+113y^5 \equiv x^5+3y^5\) is in \( \{ -4,-3,-2,-1,0,1,2,3,4 \} \) mod \( 11 \). But \( 137 \equiv 5 \). So there are no solutions mod \( 11\), hence no solutions. \(_\square\)
Note that looking mod \( 113 \) or mod \( 137 \) 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 \( p \) is a power of \( p \). As above, only \( \frac 1p\) of the integers relatively prime to \( p \) are \( p^\text{th}\) powers mod \( p^k\).
For instance, if the exponent is \(2\) or \( 4\), it is effective to use moduli of \( 8\) and \( 16\), respectively, since \( x^2 \equiv 1\) mod \( 8 \) for odd \( x \), and \( x^4 \equiv 0,1 \) mod \( 16 \) for any \( x \). (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
\[n_1^4 + n_2^4 + \cdots +n_{14}^4 = 1599.\]
Look mod \( 16 \). Then \( n_i^4 \equiv 0 \) or \( 1 \), so the left side is in \( \{ 0,1,2,\ldots,14\} \) mod \( 16 \), but the right side is \( 15 \) mod \( 16 \). So there are no solutions. \(_\square\)
The three cubes problem is the subject of considerable contemporary research: for which values of \(n\) do integer solutions to
\[x^3+y^3+z^3=n\]
exist? Show that for \( n = 32 \) there are no solutions. \((\)The question of whether there is a solution for \( n = 33 \) has recently been solved by Andrew Booker.\()\)
Look mod \( 9 \). Cubes are \( -1,0,1 \), so their sum is in \( \{ -3,-2,-1,0,1,2,3 \} \). Thus any number congruent to \( \pm 4\) mod \( 9 \) cannot be written as a sum of three integer cubes. And \( 32 \equiv -4 \) mod \(9\). \(_\square\)
The conjecture is that any \( n \not\equiv \pm 4 \) mod \( 9 \) admits solutions, but there are many \( n \) where solutions have not been found. As of the time of this writing, \( 42 \) is the only natural number below 100 for which no solutions have been found.
Descent
Sometimes there are solutions mod \( n\), but only the "trivial" ones where the variables are \( 0 \). So \( n \) divides all the variables. Sometimes factoring \( n \) out leads to a contradiction, and sometimes it leads to a simpler equation.
For more examples, see the wiki on infinite descent.
Diophantine Equations with Powers
This section deals with equations with terms of the form \(a^n\), where \(a\) is a given positive integer. The standard technique for solving this type of equation is manipulating the equation until the form, \(a^n=\text {product of several expressions},\) is obtained. In particular, if \(a\) 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 \(a\) 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 \((p,n,x)\) in the following Diophantine equation with prime \(p\) and positive integers \(x,n:\)
\[p^n+1=x^2.\]
Notice that we get a difference of squares by substrating \(1\) on both sides:
\[p^n=x^2-1=(x-1)(x+1).\]
From the opening discussion, we know each factor is a power of \(p\):
\[\begin{align} x-1&=p^a \\ x+1&=p^b, \end{align}\]
where \(a,b\) are non-negative integers that satisfy \(a+b=n\). Note that \(x+1>x-1\implies b>a\).
Subtracting the two equations gives \(p^b-p^a=2.\)
If \(a\ge 1\), then \(p\) is a divisor on the lefthand side, so \(p|2\implies p=2\). Also, \(a\le 1\) or else \(4|2\). Thus \(a=1\) and we have \(2^b-2^1=2\implies 2^b=4\implies b=2\), which gives the solution \((2,3,3)\).
If \(a=0\), then \(p^b=3\implies p=3, b=1\), which gives the solution \((3,1,2)\).
In conclusion, \((2,3,3)\) and \((3,1,2)\) are the only solutions to the equation. \(_\square\)
A fairly easy category of power equations to solve has the form
\[a^x-b^y=1,\]
where \(a,b\) are given positive integers. We will assume that \(a,b\) are relatively prime and \(x,y\) 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 \(a^x-1=b^y\), then we know there exists \(N\) such that for all \(x\ge N\), \(a^x-1\) has prime divisors that do not divide \(b\).
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 \(b\) always divides \(a^x-1\), then a fixed number must also always divide \(x\). This is just a property of order of an element: if \(a^x\equiv 1\pmod m\) and \(a,m=1\), then \(\text {ord}_m(a)\Big|x\). On one hand, we get that \(\text {ord}_m(a)\) is even, which implies \(x\) is even and gives way to difference of squares. On the other hand, we get that \(a^{\text {ord}_m(a)}-1\) has prime divisors that do not divide \(b\). Since \(a^{\text {ord}_m(a)}-1\Big|a^x-1=b^y\), we know there is no solution when this occurs. If neither of these cases happens, then choose a "larger" \(b\). We illustrate this in the examples below.
Solve \(11^x=2^y-1\) in positive integers.
From \(2^y\equiv 1 \pmod {11}\), we have \(\text {ord}_{11}(a)=10\implies 10\big|y\). It follows that \(2^{10}-1\big|2^y-1=11^x\), which is impossible because \(2^{10}-1=11\cdot 3\cdot 31\). Therefore this equation has no solution. \(_\square\)
Find all integers \(n,m\) such that
\[|2^n-3^m|=1.\]
We first get the zero cases out of the way: \((n,m)=(1,0)\). Now assume that \(n,m\) are positive integers.
The absolute value means we have two cases:
Case 1: \(2^n-3^m=1\implies 2^n-1=3^m\)
Considering modulo \(3\) gives us \(2|n\). This result, however, is not strong enough as \(2^2-1=3\) does not contain prime divisors other than \(3\). What do we do now? Well, \(m=1\) produces the solution \((2,1)\). Now we assume \(m\ge 2\) and consider modulo \(3^2\). This gives us \(6|n\) and we can stop here because \(7|2^6-1\). Thus there is not a solution when \(m\ge 2\).Note that from \(2|n\) we could have proceeded differently using difference of squares, so try this yourself to check with the answers above.
Case 2: \(3^m-2^n=1\)
This case can be solved similarly as case 1. Here, however, we cannot conclude one of \(m,n\) being even, which means difference of squares is out of the window. I will leave this case as an exercise for interested readers. \(_\square\)
What happens if our equation is
\[a^x-b^y=n ~\text { with }~ n>1? \]
Then, in general, we cannot apply the method above because using order requires \(n\) to be \(1\). In these situations, choosing the right modulus often helps by giving us information about \(x,y\). Trying different modulus on the equation should be a priority when solving these equations.
Find all positive integers \(m,n\) that satisfy
\[|12^m-5^n|=7.\]
Case 1: \(5^n-12^m=7\). In modulo \(4\), this becomes \(1\equiv 3\pmod 4\), so there are no solutions for this case.
Case 2: \(12^m-5^n=7\). In modulo \(6\), this becomes \((-1)^n\equiv -1\pmod 6\), so \(n\) is odd. Note that \(m=n=1\) is a solution, so taking modulo \(5\) and \(4\) would not help. Instead, we can assume that \(m\ge 2\) and now we can analyze with modulo \(8\):
\[5^n\equiv 1\pmod 8 \implies 2|n.\]
This contradicts with \(n\) being odd, what we found earlier. So \(m=n=1\) is our only solution. \(_\square\)
Find all positive integers \((m,n)\) that satisfy
\[3^m-7^n=2.\]
By observation, we can see that \((2,1)\) satisfies this, but not \((1,1)\). We will now show there are no solutions for \(m>2\) and \(n>1\). Assume the contrary:
\[\begin{align} 3^m - 7^n &= 2\\ 3^m - 9 &= 7^n - 7\\ 9 \big(3^{m-2}-1\big) &= 7 \big(7^{n-1}-1\big). \end{align}\]
Since \(\text{gcd}(7,9)=1\), it must follow that \(9 \mid 7^{n-1}-1\). The multiplicative order of \(7 \pmod{9}\) is \(3\), so \(3 \mid n-1\). This statement implies \(19 \mid 7^3-1 \mid 7^{n-1}-1\).
From this, using the fact that \(\text{gcd}(9,19)=1\), it must follow that \(19 \mid 3^{m-2}-1\). The multiplicative order of \(3 \pmod{19}\) is \(18\), so \(18 \mid n-1\). This statement gives us \(37 \mid 3^{18}-1 \mid 3^{m-2}-1\).
Following from before, using \(\text{gcd}(7,37)=1\), it must follow that \(37 \mid 7^{n-1}-1\). The multiplicative order of \(7 \pmod{37}\) is \(9\), so \(9 \mid n-1\). From this, we gather \(27 \mid 7^9-1 \mid 7^{n-1}-1\).
However, this implies that \(27 \mid 3^2 (3^{m-2}-1) \implies 3 \mid 3^{m-2}-1\), which is impossible for \(m>2\). Thus, there exist no further solutions for this Diophantine equation.
Therefore, the only satisfying solution is \((2,1).\ _\square\)
Try proving the following problems yourself:
Find all positive integer solutions to the Diophantine equation
\[5^x-3^y=2.\]
Find all positive integer solutions of the equation
\[3^x+4^y=5^z.\]
Hint: Show that \(x=y=2\) are the only solutions.