How to solve Diophantine equations in $F_{p}$? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T12:00:01Z http://mathoverflow.net/feeds/question/20548 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/20548/how-to-solve-diophantine-equations-in-f-p How to solve Diophantine equations in $F_{p}$? Changwei Zhou 2010-04-06T21:24:25Z 2010-07-20T20:00:59Z <p>For example, how to solve the equation <code>$\sum^{p-1}_{i}x_{i}^{2}=0$</code> 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. </p> http://mathoverflow.net/questions/20548/how-to-solve-diophantine-equations-in-f-p/20553#20553 Answer by Bjorn Poonen for How to solve Diophantine equations in $F_{p}$? Bjorn Poonen 2010-04-06T21:45:47Z 2010-04-06T23:57:56Z <p>There is a <em>deterministic</em> polynomial-time algorithm for finding solutions to diagonal equations of degree less than or equal to the number of variables over finite fields. See <a href="http://www.opt.math.tugraz.at/~cvdwoest/" rel="nofollow">Christiaan van de Woestijne's thesis</a>.</p> <p>(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.)</p> http://mathoverflow.net/questions/20548/how-to-solve-diophantine-equations-in-f-p/20554#20554 Answer by Michael Lugo for How to solve Diophantine equations in $F_{p}$? Michael Lugo 2010-04-06T21:46:36Z 2010-04-06T21:46:36Z <p>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.</p> <p>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$. </p> <p>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$. </p> <p>(Basically, this is a more explicit version of the second paragraph of Bjorn Poonen's answer.)</p> http://mathoverflow.net/questions/20548/how-to-solve-diophantine-equations-in-f-p/32685#32685 Answer by Anweshi for How to solve Diophantine equations in $F_{p}$? Anweshi 2010-07-20T20:00:59Z 2010-07-20T20:00:59Z <p>This answer is tangential in the sense that it is speaking of the <em>existence</em> of solutions rather than counting them all. But I rather suspect that you would find this interesting.</p> <p>Suppose you have a quadratic form in at least thee variables over $\mathbb F_p$. Then the <a href="http://en.wikipedia.org/wiki/Chevalley%2DWarning_theorem" rel="nofollow">Chevalley-Warning Theorem</a> would tell you that it has a nontrivial solution.</p> <p>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.</p>