6
$\begingroup$

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
    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](https://sites.google.com/site/tpiezas/003) is a start.2012-08-11

3 Answers 3

3

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.

  • 0
    do you mean $Q=0?$2012-08-11
  • 0
    @WillJagy: Yes. Thank you for pointing out the typo.2012-08-11
  • 0
    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.2012-08-11
  • 0
    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$.2012-08-11
  • 0
    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,....2017-11-12
  • 0
    As explained in my own answer, this answer is incorrect because the Hasse principle for *integral* zeros of quadratic forms can fail.2018-01-30
1

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.

1

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.