I found a question whether there are general methods to solve second degree Diophantine equations. I was unable to find an answer so is this known? In particular, the original writer wants to know whether one can find all integers satisfying $x^2 + x = y^2 + y + z^2 + z$.

  • 1
    $\begingroup$ For your equation, as was explained by Will Jagy, this is equivalent to looking for all the odd solutions of $X^2+1=Y^2+Z^2$. There are various parametric families of solutions. I have seen a nicer collection somewhere (Piezas?) but here is a start. $\endgroup$ – André Nicolas Aug 11 '12 at 20:20

About algorithm: There is an algorithm that will determine, given any quadratic $Q(x_1,\dots,x_n)$ as input, whether or not the Diophantine equation $Q(x_1,\dots,x_n)=0$ has a solution. This is something that I (and others) observed quite a long time ago. I have no knowledge about a nice algorithm.

Set one machine $M_1$ to search systematically for solutions. Another machine $M_2$ simultaneously checks whether there is a real solution (easy) and then checks systematically for every modulus $m$ whether there is a solution modulo $m$.

By the Hasse Principle (which in this case is a theorem), if our equation has "local" solutions (real and modulo $m$ for every $m$) then it has an integer solution. So either $M_1$ will bump into a solution or $M_2$ will find a local obstruction to a solution. Thus the algorithm terminates.

The corresponding question for cubics is unsolved. The same question for quartics (in arbitrarily many variables) is equivalent to the general problem of testing a Diophantine equation for solvability, so is recursively unsolvable.

Added: I think that the details are written out in the book Logical Number Theory I by Craig Smorynski. Very nice book, by the way.

  • $\begingroup$ do you mean $Q=0?$ $\endgroup$ – Will Jagy Aug 11 '12 at 20:17
  • $\begingroup$ @WillJagy: Yes. Thank you for pointing out the typo. $\endgroup$ – André Nicolas Aug 11 '12 at 20:23
  • $\begingroup$ So there are only finitely many $m$'s to be checked? If I remember correctly, Turing machine should halt after finitely many steps for every input. $\endgroup$ – Jaakko Seppälä Aug 11 '12 at 20:29
  • $\begingroup$ The machines $M_1$ and $M_2$ operate in parallel (or equivalently make a single $M$ that alternates between an $M_1$ computation and an $M_2$ computation.) As soon as we find an integer solution we halt. As soon as we find an obstruction $m$ (no solution mod $m$) we halt. So for any input $Q$, the algorithm halts in finite time. The time will depend on $Q$. $\endgroup$ – André Nicolas Aug 11 '12 at 20:36
  • $\begingroup$ Alpern's homepage has a method to solve two variable equations, but you will find it erratic. Try x^2 + (x+1)^2 = 125*y and you get a strange mess. The solutions are x=28 + 125*k and x=96 + 125*k for k=1,2,.... $\endgroup$ – J. M. Bergot Nov 12 '17 at 22:15

Rewrite this equation a little differently. $$X (X +a)+Y (Y +a)=Z (Z +a)$$

Formulas for the solution can then be written, $p,k$ - where are integers and sets us.

$$X =pk$$ $$Y =\frac{(p^2 −1)k}{2} +\frac{(p−1)a}{2}$$ $$Z =\frac{( p^2 +1)k}{2} +\frac{(p−1)a}{2}$$

If we use the solutions of Pell's equation $p^2 −2 s^2 =1$

Then the solution can be written: $$X =2(s+p)sL+as(2s+p)$$ $$Y =(2s+p)pL+as(2s+p)$$ $$Z =(2 s^2 +2ps+ p^2 )L+2as(s+p)$$

And more. $$X =2s(s−p)L+ap(s−p)$$ $$Y =(p−2s)pL+ap(s−p)$$ $$Z =(2 s^2 −2ps+ p^2 )L+ap(2s−p)$$

$L$ - given by us and can be any integer.


There is an algorithm for deciding whether a single degree 2 multivariable polynomial equation has a solution in integers, due to Siegel, Zur Theorie der quadratischen Formen, Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 1972, 21-46. See also Grunewald and Sigel, On the integer solutions of quadratic equations, J. Reine Angew. Math. 569 (2004), 13-45.

But the Hasse principle by itself does not give an algorithm: it holds only for rational solutions, not for integer solutions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.