# Is there an algorithm to solve quadratic Diophantine equations?

I was asked two questions related to Diophantine equations.

1. Can one find all integer triplets $(x,y,z)$ satisfying $x^2 + x = y^2 + y + z^2 + z$? I mean some kind of parametrization which gives all solutions but no points which do not satisfy the equation.

2. Is there an algorithm that will determine, given any quadratic $Q(x_1,\ldots,x_n)$ as input, all integer points of this quadratic? In the case of existence of solution, there is an algorithm, https://math.stackexchange.com/questions/181380/second-degree-diophantine-equations/181384#comment418090_181384

• Are you looking for all triples $(x,y,z)$? Then one has $X^2+1=Y^2+Z^2$ for $X=2x+1$ etc. So $Z^2-1=X^2-Y^2$ i.e. $(Z-1)(Z+1)=(X-Y)(X+Y)$ – Aaron Meyerowitz Sep 23 '13 at 14:10
• @AaronMeyerowitz Yes. I'm looking for all triplets. The idea you gave was already given in stackexchange. But it seems to be hard to find all solutions. – amateur Sep 23 '13 at 14:29

Sierpsinski proved that whenever this diophantine equation does not have a solution for $x$ then $x^2+(x+1)^2$ is prime. It is conjectured also by Sierpinski that there are infinitely many primes of the above form but this still remains open.

So, your question cannot be answered yet. For more details see http://arxiv.org/pdf/0810.0222.pdf

• I think this only answers a much stronger question. In particular, one can give a parametrization of solutions without necessarily having a characterization of which $x$ coordinates are hit. – S. Carnahan Sep 24 '13 at 15:30
• @S.Carnahan yes ,but the ''parametrization'' may not actually give all integer triplets in a away similar to Euclidean triplets – Konstantinos Gaitanas Sep 24 '13 at 16:09

If one is interested in efficient algorithms, as opposed to the simple existence of algorithms, it may be worth noting that, given positive integers $a$, $b$, and $c$, the question, are there positive integers $x$ and $y$ such that $ax^2+by=c$, is NP-complete. This is item AN8 in Garey and Johnson, page 250; the citation is Manders and Adleman, NP-complete decision problems for binary quadratics, J Comput System Sci 16 (1978) 168-184.

• @Turbo, have you had a look at the Manders & Adleman paper? – Gerry Myerson Mar 31 '15 at 11:59
• Actually no I have not. – 1.. Mar 31 '15 at 12:13
• @Turbo, on the cited page of Garey & Johnson, they say "Transformation from 3SAT." – Gerry Myerson Mar 31 '15 at 22:48
• Actually thinking back, could $c$ be a prime with $gcd(a,b) = gcd(b,c) = gcd(c,a) = 1$? Sorry I do not have reference to Adleman paper or Garey Johnson. – 1.. Apr 2 '15 at 10:03
• Read the papers, Turbo. Read the papers. – Gerry Myerson Jan 22 '16 at 21:39

Let me just add that for solving quadratic diophantine equations in 2 variables, i.e. equations of the form $$ax^2 + bxy + cy^2 + dx + ey + f = 0, \ \ a, b, c, d, e, f \in \mathbb{Z},$$ there is a nice algorithm. Dario Alpern has created a website running a Java program which completely solves such equations for given coefficients $a, b, c, d, e$ and $f$ -- see http://www.alpertron.com.ar/JQUAD.HTM. Optionally, the program shows all steps of the solution, similar as a human might do when solving the equation by hand. The website also describes the algorithm used.

• @pts, are you sure about that? I just tried it, and it gave me $(0,-1),(0,1),(-1,-2),(-1,2),(2,-5)$ and $x_{n+1}=-9x_n-4y_n-2$, $y_{n+1}=-20x_n-9y_n-4$. Is it possible you accidentally asked for $5x^2+2x+1+y^2=0$? – Gerry Myerson Jun 7 '16 at 22:54
• @Gerry Myerson: I've tried it again (not the Java program, but the JavaScript on alpertron.com.ar/JQUAD.HTM), an it gives me the same recursive formula as you got, but not the starting value (e.g. $(0,-1)$ and the others don't show up). So it's still buggy – pts Jun 8 '16 at 6:38
• @pts That example works fine for me: i.stack.imgur.com/Dev3k.gif (Of course it's possible the program changed since then, but I also remember seeing this comment a couple of years ago and finding it to work...) – shreevatsa Nov 3 '19 at 20:54
• @pts I suspect you are entering your equations incorrectly, as it seems to work fine for other people entering the same equations as you, and also works fine for me. Are you sure you put negative signs in the right places? – EntangledLoops Apr 9 '20 at 17:56
• In an earlier comment I wrote that the web (JavaScript) version of program is buggy. I'm not able to reproduce that particular bug anymore (i.e. it works correctly for that input), so I deleted the comment. – pts Apr 9 '20 at 20:55

There are infinitely many integer solutions, so you need to specify what you mean by "can one find all". If you mean "Are all solutions given by a finite set of easily computed parametrized families?" then the answer is yes, essentially following John R Ramsden's answer (with some minor corrections).

If we set $X = 2x+1$, $Y = 2y+1$ and $Z = 2z+1$, we get the equation $X^2 + 1 = Y^2 + Z^2$. Euler showed that all solutions have the form $(ac+bd)^2 + 1 = (ac-bd)^2 + (ad+bc)^2$ where $a,b,c,d$ range over integers satisfying $ad-bc = 1$. This set is easy to parametrize, because $a,b,c,d$ describe entries of elements $\binom{ab}{cd}$ in $SL_2(\mathbb{Z})$. We are seeking odd solutions, and this condition is equivalent to $ac+bd$ odd, which can be determined by reducing matrices mod 2.

We find that any element of $SL_2(\mathbb{Z})$ congruent to $\binom{11}{01}$, $\binom{01}{11}$, $\binom{10}{11}$, or $\binom{11}{10}$ modulo 2 yields a solution to your equation. These can be easily generated, either by using the Euclidean algorithm to generate suitable elements of $SL_2(\mathbb{Z})$ from an initial choice of coprime integers, or by multiplying an initial solution by powers of the matrices $\binom{12}{01}$ and $\binom{10}{21}$. The kernel $\Gamma(2)$ of reduction mod 2 in $SL_2(\mathbb{Z})$ becomes a free group generated by those two matrices, once we quotient by $\pm \binom{10}{01}$. This sign ambiguity nicely cancels the invariance under sign change in Euler's parametrization.

The equation is equivalent to $(2 x + 1)^2 + 1 = (2 y + 1)^2 + (2 z + 1)^2$. So given that an integer solution to this is implies integers $a, b, c, d$ with exactly one odd and $(a, d) = (b, c) = 1$ with $2 x + 1, 2 y + 1, 2 z + 1 = a c + b d, a b + c d, a c - b d$ subject to $a b - c d = 1$, it would appear the original is equivalent to the latter.

S. Carnahan (Sep 24 '13 at 18:33) showed parametrization by cosets of congruence subgroups of SL(2,Z). What is missing is parametrization of SL(2,Z) and its congruence subgroups which can be found in L.N. Vaserstei. Polynomial parametrization for the solutions of Diophantine equations and arithmetic groups , Annals of Math. 171:2 (March of 2010), 979–1009. MR2630059. Zbl 05712747

• Actually, the answer is the same as for the equation x^2 + y^2 = z^2 : the integer solutions cannot be covered by a polynomial solution with integer coefficients but can be covered by 2 polynomial solutions. – Leon Vaserstein Mar 24 '15 at 3:07

We first run the algorithm to determine whether any solutions exist, by dovetailing an enumeration of integer $n$-tuples together with an exhaustive search of solutions modulo prime powers, halting if it finds either an integer solution, a disproof in modular arithmetic or a disproof in the reals (e.g. by showing that the quadratic form is positive- or negative-definite). This algorithm works by the Hasse principle.

If it finds a disproof, output the empty set $\emptyset$. Otherwise, we analyse the signature of the quadratic form. If it is $+++ ... +$ or $--- ... -$, then the surface would be bounded and, as such, there is a finite solution set that can be produced by exhaustive search. Otherwise, there are infinitely many solutions (as intersecting one solution with an appropriately-chosen plane yields a generalised Pell equation). In that case, we can just exhaustively run through an enumeration of integer $n$-tuples, printing out each solution that it finds.

• But if there are infinitely many solutions, can we parametrize them somehow? – amateur Sep 23 '13 at 10:18
• The Hasse principle works rationally: your quadratic form has rational zeroes if and only if it has real zeroes and zeroes in $\mathbb{Q}_p$ for all $p$ (and the latter is fairly close to having solutions mod every prime power). However, in general there's a big gap between rational solutions and integer solutions, particularly as the OP's example of interest isn't homogenous. – James Cranch Sep 23 '13 at 14:28
• James is correct; I missed the word 'homogeneous' when quickly reading an e-mail containing necessary and sufficient conditions for the Hasse principle to give an algorithmic criterion for whether integer solutions exist. – Adam P. Goucher Sep 23 '13 at 22:27

Everything can be done much easier! 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.