The modular arithmetic contradiction trick for Diophantine equations

Question

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.

Answer 1

[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$.

Answer 2

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.

Answer 3

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$.

Answer 4

Yes, there are similar modulos to other powers. For example, $n^6\mod504$ can take only the values $0, 1, 64, 217, 225, 280, 288, 441$ over integers $n$.

The $p$-adic methods are used to prove the insolubility for some Diophantine equations. For example:

There are no integer solutions to $$x^5+y^5+z^5+t^5=5$$, as this can be proved modulo $11$.

Also, there only integer solution to $$x^2+3y^2=2z^2$$ is the trivial $(x,y,z)=(0,0,0)$, as this can be proved by applying the $p$-adic method for $p=2$.

However, the insolubility to the negative Pell equation $x^2-34y^2=1$ canno be deduced from the $p$-adic method.