# The modular arithmetic contradiction trick for Diophantine equations

It is a slick, and seemingly ad-hoc, technique often used to prove that a Diophantine equation has no solutions.

The equation $f(x_1,\ldots, x_k)=0$, with variables $x_i\in\mathbb{Z}$ and some elementary function $f$, is taken modulo some ingeniously chosen $n\in\mathbb{Z}^+$. Then by evaluating $f$ on the $k^n$ possible $k$-tuples $(x_1,\ldots,x_k)$ of residues modulo $n$, it is shown that $0$ is achieved in no case. Thus no solution exists in $\mathbb{Z}$ either.

A traditional classroom example is $x^2+y^2-3z^2=0$. Assume $\gcd(x,y)=1$ without loss of generality, and use modulo $3$.

The trouble is in coming up with the brilliant $n$. An example of a good heuristic principle is choosing modulo $20$ if there are powers of $4$ as, out of to $20$ possible residues, the only quartic residues are $0,1,5,16$. Are there similar mods for other powers?

In general, has there been any work done on an objective way of finding $n$? Perhaps good heuristics, if nothing else? Restrict $f$ to some non-trivial case, say certain polynomials of given degree, if needed. Paper references would be nice.

-
I don't quite know why this has been down-voted. I asked a question that has bothered me since my old olympiad days, looking for a serious answer. And potentially interesting answers exist. –  Seraj Jun 21 '13 at 6:01
For Diophantine equations coming from curves, the Hasse-Weil bound shows that you can solve your Diophantine equation mod p for any sufficiently large prime p, and for higher dimensional varieties I suspect one can use the Weil conjectures to get a similar result. Furthermore, if the equation is solvable mod p, then usually Hensel's lemma allows you to lift the solution to a solution mod any power of p. So really there are only finitely many congruences one needs to check to see if a Diophantine equation can be ruled out by congruences. –  zeb Jun 21 '13 at 8:55
This is a lot more than a slick ad-hoc trick". The idea that the existence of an integer solution implies the existence of solutions modulo every $n$ is really at the cornerstone of the modern study of diophantine equations. Equations for which the converse also holds are said to satisfy the Hasse principle; as already noted this principle does not hold in general. In practice one often chooses an $n$ such that the equation has singular reduction mod $n$ (e.g. $n$ divides an exponent or a coefficient), since often one gets solutions for free for $n$ with non-singular reduction. –  Daniel Loughran Jun 21 '13 at 11:58
I forgot to add that with regards to the Hasse principle, one also asks for solubility at the "infinite prime", which corresponds to asking for solutions in $\mathbb{R}$. –  Daniel Loughran Jun 21 '13 at 16:41

[More a comment than an answer, but a bit long for that]

D. J. Lewis, in Diophantine equations: p-adic methods, pp. 25–75 of Studies in Number Theory, Math. Assoc. Amer. 1969, MR0241359 (39 #2699), writes (p. 28), "As you might expect, there is some artistry in choosing the appropriate modulus."

This was confirmed by Valeriu Şt. Udrescu in the paper, On D. J. Lewis's equation $x^3-117y^3=5$, Rev. Roumaine Math. Pures Appl. 18 (1973) 473, MR0316380 (47 #4927). Lewis stated, on p. 26 of the paper cited earlier, that this equation "is known to have at most 18 integral solutions but the exact number is unknown." Finkelstein and London used algebraic number theory to prove it has no solutions, and then Udrescu pointed out that it reduces to $x^3\equiv5\pmod9$.

-
(+1) Very nice story! –  Gottfried Helms Jun 21 '13 at 6:29
@Gerry: You could have just posted a link to the following answer of yours from 2010 which has essentially the same contents: mathoverflow.net/questions/42512/… –  Stefan Kohl Jun 21 '13 at 16:54
@Stefan, expecting me to remember something I posted here two-and-a-half years ago is giving me way too much credit. –  Gerry Myerson Jun 21 '13 at 23:15

Alex says in his answer that for a polynomial that is an integral or rational quadratic form, congruence conditions explain completely when it has no rational zeros (other than $(0,\dots,0)$). Congruence conditions need not be sufficient to explain a lack of integral solutions in some other situations.

1. Consider $2x^2 + 7y^2 = 1$. It has no integral solutions, but has the rational solutions $(1/3,1/3)$ and $(3/5,1/5)$. Because the denominators in the two solutions are relatively prime, they can be used to produce solutions to $2x^2 + 7y^2 \equiv 1 \bmod m$ for any $m \geq 2$. (See Diophantine equation with no integer solutions, but with solutions modulo every integer for more examples in this direction.)

2. Consider a Mordell equation $y^2=x^3+k$ with $k$ a nonzero integer. Depending on $k$ there may or may not be an integral solution (e.g., there is if $k = 1$ and there is not if $k = 6$), but you can't rule out the possibility of an integral solution using modular arithmetic alone since $y^2 \equiv x^3 + k \bmod m$ has a solution for every $m \geq 2$.
It suffices by the Chinese remainder theorem to show $y^2 \equiv x^3 + k \bmod p^r$ is solvable for every prime power $p^r$, or what amounts to the same thing, there is a $p$-adic integer solution for every prime $p$. There is a 2-adic integer solution $(x,k+1)$ for some $x$ and a 3-adic integer solution $(1−k,y)$ for some $y$. In the 5-adic integers there is a solution $(0,y)$ if $k \equiv 1, 4 \bmod 5$, $(1,y)$ if $k \equiv 0, 3 \bmod 5$, and $(-1,y)$ if $k \equiv 2 \bmod 5$. In the 7-adic integers there is a solution $(0,y)$ if $k≡1,2,4 \bmod 7$, $(1,y)$ if $k≡0,3 \bmod 7$, $(−1,y)$ if $k≡5 \bmod 7$, and $(x,0)$ if $k ≡ 6 \bmod 7$. For $p \geq 11$, let $N_p$ be the number of mod $p$ solutions to $y^2 \equiv x^3 + k \bmod p$, so $N_p=p+S_p$ where $S_p=0$ if $p|k$ and $|S_p| \leq 2\sqrt{p}$ by the Hasse bound if $(p,k)=1$. Then $N_p \geq 4$, so there is a solution to $y_0^2 \equiv x_0^3 + k \bmod p$ where $y_0 \not\equiv 0 \bmod p$, and this solution lifts $p$-adically to $(x_0,y)$ for some $p$-adic integer $y$.

-
Dear Keith, As you well know, the difference between these examples and those Alex considers is that Alex's are homogeneous (so that integral and rational solutions amount to the same thing), while those that you consider are not. I just wanted to add this in case the OP (or anyone else coming by) wonders about the difference. Cheers, Matt –  Emerton Jun 23 '13 at 1:19

For diagonal conics, such as your example of $x^2+y^2-3z^2=0$, a non-zero rational solution exists if and only if one exists modulo all powers of all prime divisors of the coefficients and modulo powers of 2. And the powers you need to consider can also be bounded a priori. This is the Hasse-Minkowski theorem. Moreover, for those odd $p$ that don't divide any of the coefficients, a solution modulo $p$ always exists. So in your example, 2 and 3 are the only primes worth trying. All this can be found in Cassels, Lectures on Elliptic Curves, chapters 3,4,5. This works more generally for quadratic forms over number fields.

On the other hand for cubic forms, this local-global principle fails, so there may be no modulus that will exclude the existence of rational solutions, even when there really are none. A famous example due to Selmer is $3x^3+4y^3+5z^3=0$. This has solutions modulo all prime powers and over $\mathbb{R}$, but not over $\mathbb{Q}$. You can read more about this in Silverman, Arithmetic of Elliptic Curves.

-