How to solve Diophantine equations in $F_{p}$? - MathOverflow

How to solve Diophantine equations in $F_{p}$?

2010-04-06T21:24:25Z

For example, how to solve the equation $\sum^{p-1}_{i}x_{i}^{2}=0$ in $F_{p}$? This is not a homework problem. I think it should have a definite answer, so not an open problem. I just don't know how to solve it.

Answer by Bjorn Poonen for How to solve Diophantine equations in $F_{p}$?

2010-04-06T21:45:47Z

There is a deterministic polynomial-time algorithm for finding solutions to diagonal equations of degree less than or equal to the number of variables over finite fields. See Christiaan van de Woestijne's thesis.

(A solution of your example equation can be found much more simply, however: try small integers, not necessarily distinct... . And for quadratic forms, the other solutions can be found by drawing lines through the point and intersecting with the quadric hypersurface: there will either be one more intersection point, or a whole line of points.)

Answer by Michael Lugo for How to solve Diophantine equations in $F_{p}$?

2010-04-06T21:46:36Z

You want to know if the sum of $p-1$ squares can be equal to 0 mod $p$. I'll assume that you don't want to allow the trivial (all-zeroes) solution.

If $k$ is a quadratic residue mod $p$, not equal to $1$, then this is simple; take $x_1$ such that $x_1^2 = k$, take $x_2 = \ldots = x_{p-k+1} = 1$, and take $x_{p-k+2} = \ldots = x_{p-1} = 0$.

So the equation $x_1^2 + \cdots + x_{p-1}^2 = 0$ has solutions mod $p$ as long as there exists a quadratic residue mod $p$ which is not equal to $1$. The number of quadratic residues mod $p$ is $\phi(p)/2$, where $\phi$ is Euler's totient function; if $\phi(p)/2 \ge 2$, or $\phi(p) \ge 4$, then there is at least one non-$1$ quadratic residue mod p. Now for a prime, $\phi(p) = p-1$, so that means your equation has solutions when $p-1 \ge 4$, i. e. when $p \ge 5$. We can check by brute force that $x_1^2 = 0 \mod 2$ and $x_1^2 + x_2^2 = 0 \mod 3$ have only the trivial solutions. So the equation $x_1^2 + \cdots + x_{p-1}^2 = 0 \mod p$ has nontrivial solutions for all primes $p \ge 5$.

(Basically, this is a more explicit version of the second paragraph of Bjorn Poonen's answer.)

Answer by Anweshi for How to solve Diophantine equations in $F_{p}$?

2010-07-20T20:00:59Z

This answer is tangential in the sense that it is speaking of the existence of solutions rather than counting them all. But I rather suspect that you would find this interesting.

Suppose you have a quadratic form in at least thee variables over $\mathbb F_p$. Then the Chevalley-Warning Theorem would tell you that it has a nontrivial solution.

If you want to check out more, I refer you to the first chapter of J.-P. Serre's "A Course in Arithmetic", rather than the wikipedia page linked above.