6
$\begingroup$

I'm use to finding the solutions of linear Diophantine equations, but what are you suppose to do when you have quadratic terms? For example consider the following problem:

Find all solutions in positive integers to the following Diophantine equation

$x^2 + 2y^2 = z^2$

I'd usually start by finding the gcd and use some other tricks, but I'm not sure how to approach this type of problem

$\endgroup$
  • $\begingroup$ AFAIK, there is no consistent "method" for solving Diophantine equations like this, beyond linear. You just try things. $\endgroup$ – ShreevatsaR Apr 20 '13 at 16:22
  • $\begingroup$ @ShreevatsaR: Actually, for $x^2+ny^2 = z^2$ there is a complete solution. I modified my answer below so it is clearer. $\endgroup$ – Tito Piezas III Apr 20 '13 at 16:28
4
$\begingroup$

Here's the identity that completely solves it,

$$((a^2-nb^2)t)^2+n(2abt)^2 = ((a^2+nb^2)t)^2\tag{1}$$

for arbitrary $a,b$ and scaling factor $t$. Yours is just the case $n = 2$.

EDIT:

To address ShreevatsaR's comment if this is the complete solution (when $x_1 x_2 x_3 \ne 0$), given rational $x_1, x_2, x_3$ such that,

$$x_1^2+nx_2^2 = x_3^2\tag{2}$$

one can always find particular rational $a,b,t$ that recovers those values using the formulas,

$$\begin{aligned}a &= x_1+x_3\\ b &= x_2\\ t &= \frac{1}{2(x_1+x_3)}\end{aligned}\tag{3}$$

Example: Given the smallest solution to ,

$$x_1^2+2x_2^2 = x_3^2$$

as {$x_1, x_2, x_3$} = {$1, 2, 3$}, then using (3), we find,

$$\begin{aligned}a &= 4\\ b &= 2\\ t &= 1/8\end{aligned}$$

which yields,

$$\begin{aligned}x_1 &= (a^2-2b^2)t = 1\\ x_2 &= 2abt = 2\\ x_3 &= (a^2+2b^2)t = 3\end{aligned}$$

which are precisely the values we started with. I hope everything is clear?

$\endgroup$
  • 2
    $\begingroup$ This is one set of solutions no doubt, but you have to prove that these are all the solutions (if indeed these are). $\endgroup$ – ShreevatsaR Apr 20 '13 at 15:56
  • $\begingroup$ Is there a general method to solving these problems or should I just memorize this identity? Also, what's the name of this identity? $\endgroup$ – Benzne_O Apr 20 '13 at 16:00
  • 2
    $\begingroup$ Just to confirm: How do you enumerate all solutions using this? Do you try all rational values for $(a, b, t)$, and throw out the ones that give non-integer solutions? Or is there something better? $\endgroup$ – ShreevatsaR Apr 20 '13 at 16:29
  • $\begingroup$ Where did this identity come from? $\endgroup$ – Benzne_O Apr 20 '13 at 16:32
  • 1
    $\begingroup$ @TitoPiezasIII: My question is, how to enumerate all integer solutions using this. $\endgroup$ – ShreevatsaR Apr 20 '13 at 16:41
6
$\begingroup$

Since the equation is homogeneous, we may WLOG assume $\gcd(x, y, z)=1$. (So that all solutions will be given by multiplying all the primitive solutions by any positive integer $k$)

Now if $x$ is even, then $z$ is even, so $y$ is also even, a contradiction. Thus $x$ is odd, so $z$ is odd, and so $x^2 \equiv z^2 \equiv 1 \pmod{4}$. Thus $4 \mid 2y^2$, so $y$ is even. Note that if $p \mid x, z$ for some prime $p$, then $p$ is odd and $p \mid 2y^2$, so $p \mid y$, a contradiction, so $\gcd(x, z)=1$.

Let $y=2y'$, so that $2y'^2=\frac{z^2-x^2}{4}=(\frac{z-x}{2})(\frac{z+x}{2})$. Now $\gcd((\frac{z-x}{2}),(\frac{z+x}{2}))=\gcd(x, z)=1$, so we have 2 cases:

Case 1: $4 \mid z-x$. Then we have $\frac{z-x}{2}=2a^2, \frac{z+x}{2}=b^2, y'=ab$ for some $a, b \in \mathbb{Z}^+$, so $z=b^2+2a^2, x=b^2-2a^2, y=2ab, \, b>a\sqrt{2}>0$. Checking, these are indeed solutions.

Case 2: $4 \mid z+x$. Then we have $\frac{z-x}{2}=b^2, \frac{z+x}{2}=2a^2, y'=ab$ for some $a, b \in \mathbb{Z}^+$, so $z=b^2+2a^2, x=2a^2-b^2, y=2ab, \, a\sqrt{2}>b>0$. Checking, these are indeed solutions.

Therefore all primitive solutions are given by $(x, y, z)=(|b^2-2a^2|, 2ab, b^2+2a^2), a, b \in \mathbb{Z}^+$.

Therefore all positive integer solutions are given by $$(x, y, z)=(k|b^2-2a^2|, k(2ab), k(b^2+2a^2)), a, b, k \in \mathbb{Z}^+$$

$\endgroup$
  • 1
    $\begingroup$ Good. Same result by finding rational points on $x^2 + 2 y^2 = 1$ and drawing lines of rational slope through $(1,0).$ $\endgroup$ – Will Jagy Apr 20 '13 at 17:06
2
$\begingroup$

Solve the Pell's equation $$Z^2 - 2Y^2 = 1$$ Now set $x=x, y=xY$ and $z=xZ$.


Finding all positive integer solutions for $Z^2 - 2Y^2 =1$.

First note that $(3,2)$ satisfies this problem since $3^2 -2 \times 2^2 = 1$. This will be the generator now. (*A slightly non-trivial fact is that all solutions to the Pell equation can be generated from this fundamental solution.) So now lets see how we generate solutions. We have \begin{align*} 3^2 - 2 \times 2^2 & = 1\\ (3+ 2 \sqrt{2}) (3 - 2 \sqrt{2}) & = 1\\ \end{align*} Now lets square both sides and proceed. \begin{align*} (3+ 2 \sqrt{2})^2 (3 - 2 \sqrt{2})^2 & = 1\\ (9 + 8 + 12 \sqrt{2}) (9 + 8 - 12 \sqrt{2}) & = 1\\ (17 + 12\sqrt{2}) (17 - 12\sqrt{2}) & = 1\\ 17^2 - 2 \times 12^2 & = 1 \end{align*} Hence, now we find that $(17,12)$ satisfies the equation $Z^2 -2Y^2 = 1$. Now lets find one more solution based on the same method and the general idea should be clear. As before, we have $(3+ 2 \sqrt{2}) (3 - 2 \sqrt{2}) =1$. Now lets cube both sides and proceed. $$(3+ 2 \sqrt{2})^3 (3 - 2 \sqrt{2})^3 = 1^3$$ $$(3^3 + 3 \times 3^2 \times 2 \sqrt{2} + 3 \times 3 \times (2 \sqrt{2})^2 + (2 \sqrt{2})^3) (3^3 - 3 \times 3^2 \times 2 \sqrt{2} + 3 \times 3 \times (2 \sqrt{2})^2 - (2 \sqrt{2})^3) = 1$$ $$(27 + 54 \sqrt{2} + 72 + 16 \sqrt{2}) (27 - 54 \sqrt{2} + 72 - 16 \sqrt{2}) = 1$$ $$(99 + 70 \sqrt{2}) (99 - 70 \sqrt{2}) = 1$$ $$99^2 - 2 \times 70^2 = 1$$ Hence, in general, we raise the equation $(3+ 2 \sqrt{2}) (3 - 2 \sqrt{2}) =1$ to the $n^{th}$ power on both sides to get the general solution. The general solution can be compactly written as $$(Z,Y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^n+\left( 3 - 2\sqrt{2} \right)^n}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^n-\left( 3 - 2\sqrt{2} \right)^n}{2\sqrt{2}} \right)$$ where $n$ is any positive integer.

$n=1$ gives us $(Z,Y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^1+\left( 3 - 2\sqrt{2} \right)^1}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^1-\left( 3 - 2\sqrt{2} \right)^1}{2\sqrt{2}} \right) = \left( 3,2\right)$.

$n=2$ gives us $(Z,Y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^2+\left( 3 - 2\sqrt{2} \right)^2}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^2-\left( 3 - 2\sqrt{2} \right)^2}{2\sqrt{2}} \right) = \left( 17,12\right)$.

$n=3$ gives us $(Z,Y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^3+\left( 3 - 2\sqrt{2} \right)^3}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^3-\left( 3 - 2\sqrt{2} \right)^3}{2\sqrt{2}} \right) = \left( 99,70\right)$.

$n=4$ gives us $(Z,Y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^4+\left( 3 - 2\sqrt{2} \right)^4}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^4-\left( 3 - 2\sqrt{2} \right)^4}{2\sqrt{2}} \right) = \left( 577, 408\right)$.

$n=5$ gives us $(Z,Y) = \left( \dfrac{\left(3 + 2\sqrt{2} \right)^5+\left( 3 - 2\sqrt{2} \right)^5}{2} , \dfrac{\left(3 + 2\sqrt{2} \right)^5-\left( 3 - 2\sqrt{2} \right)^5}{2\sqrt{2}} \right) = \left( 3363, 2378\right)$. and so on...

$\endgroup$
  • 2
    $\begingroup$ How do you show that these are all the solutions to $x^2 + 2y^2 = z^2$? $\endgroup$ – ShreevatsaR Apr 20 '13 at 16:09
  • $\begingroup$ @ShreevatsaR Thinking... $\endgroup$ – user17762 Apr 20 '13 at 16:12
  • $\begingroup$ So if you have solutions for $(Z,Y)$, what's $(x,y,z)$ exactly? $\endgroup$ – Inceptio Apr 20 '13 at 16:14
  • $\begingroup$ @Inceptio $x=x, y=xY$ and $z=xZ$. $\endgroup$ – user17762 Apr 20 '13 at 16:15
  • $\begingroup$ @user17762: What's $x$ when $n=2$? Is it $3$? $\endgroup$ – Inceptio Apr 20 '13 at 16:19
2
$\begingroup$

The following method can be used to find all points on conics if one solution is obvious.

  1. Divide by $z^2$ to obtain $(x/z)^2 + n(y/z)^2 = 1$. This implies the question is equivalent to finding the rational points on the curve $x^2+ny^2 = 1$. (Equivalent in the sense that every integer solution for $x^2+ny^2=z^2$ gives a rational solution for $x^2+ny^2=1$ and vice versa.)
  2. Note that $(1,0)$ is a solution. If $(x_0,y_0)$ is an other solution, then we can draw the line between these two points. This line will have rational slope (since both points are rational).
  3. Thus we can recover all rational points on the curve by drawing lines through $(1,0)$ with rational slope and determining the intersection with the curve.
  4. Such a line can be parametrized by $$ \begin{aligned} x-1 &= rt \\ y &= t\end{aligned}, $$ where $t$ is the parameter and $r$ the (arbitrary) slope. (Actually you have to check the case where "$r=\infty$", i.e. $x-1=t$ and $y=0$ as well. This results in the solution $x=-1$ and $y=0$.)
  5. Subsituting in the equation $x^2 + ny^2 = 1$, cancelling $1$'s and dividing by $t$ (which expresses that $(1,0)$ is a solution), we find $$ \begin{aligned} x &= \frac{n-r^2}{n+r^2} \\ y &= \frac{-2r}{r^2+n} \end{aligned}.$$
  6. Any integer solution for the original equation comes from the rational $x,y$'s above. It's a bit a pain, but first write $r = a/b$ and then find out by what common factors you can multiply $x$ and $y$ to make sure that they both are integers.
$\endgroup$
1
$\begingroup$

Um. For any prime $p \equiv 1,3 \pmod 8,$ there is a representation $p = u^2 + 2 v^2,$ as a result of which there is also a primitive representation $p^2 = u_2^2 + 2 v_2^2$ by Tito's formula. There is a representation of $4$ but not primitive. Finally, there is the trivial representation $q^2 = x^2$ when $q \equiv 5,7 \pmod 8.$ So, in fact, if you allow non-primitive answers, $z$ can be anything at all, and if $z$ has any factor $p \equiv 1,3 \pmod 8,$ there is a solution $z^2 = x^2 + 2 y^2$ with nonzero $y.$

Oh, products are not a problem, $$ (u^2 + 2 v^2)(x^2 + 2 y^2) = (ux + 2 vy)^2 + 2 (uy-vx)^2. $$ Notice that negating one of these, as $v,$ gives a genuinely different formula on the right hand side.

This procedure does give all solutions; if you can factor $z,$ you can build all $(x,y).$

EEDDIITT: As an alternative, we can take the ellipse $x^2 + 2 y^2 = 1$ and parametrize all rational points, a procedure which gives everything and was called to my attention by Gerry Myerson. Done here Generating Pythagorean triples for $a^2+b^2=5c^2$? for the problem $a^2 + b^2 = 5 c^2. $ Went through it for rational points on the ellipse $x^2 + 2 y^2 = 1$ by lines through $(1,0).$ The result is exactly what Ivan Loh got, but without any thinking. I'm getting quicker at this.

$\endgroup$
0
$\begingroup$

Basically, I will also transform the problem into that of finding rational points on the ellipse $x^{2}+2y^{2}=1$ as other answers did but I will use the Hilbert's Satz 90.

I will prove the following:

Solutions $(u,v)\in\mathbb{Q}^{2}$ of the Diophantine equation $u^{2}+2v^{2}=1$ is of the form $u=\frac{m^{2}-2n^{2}}{m^{2}+2n^{2}},v=\frac{-2mn}{m^{2}+2n^{2}}$.

Consider the Galois extension $\mathbb{Q}(\sqrt{-2})/\mathbb{Q}$. Write $u=\frac{x}{z},v=\frac{y}{z}~(x,y,z\in\mathbb{Z})$. Let $a=\frac{x+y\sqrt{-2}}{z}$. Then $N_{\mathbb{Q}(\sqrt{-2})/\mathbb{Q}}(a)=\frac{x+y\sqrt{-2}}{z}\cdot\frac{x-y\sqrt{-2}}{z}=\frac{x^{2}+2y^{2}}{z^{2}}=1$.

Thus, $a=\bar{b}/b$ for some $b\in\mathbb{Q}(\sqrt{-2})^{*}$ since $H^{1}(\text{Gal}(\mathbb{Q}(\sqrt{-2})/\mathbb{Q}),\mathbb{Q}(\sqrt{-2})^{*})$ is trivial. Choose $s\in\mathbb{Z}$ so that $bs\in\mathbb{Z}[\sqrt{-2}]$.

Then $\frac{\bar{b}s}{bs}=a$. Write $bs=m+n\sqrt{-2}$. Then $a=\frac{m-n\sqrt{-2}}{m+n\sqrt{-2}}=\frac{(m-n\sqrt{-2})^{2}}{m^{2}+2n^{2}}=\frac{(m^{2}-2n^{2})+(-2mn)\sqrt{-2}}{m^{2}+2n^{2}}$. Hence, $u=\frac{m^{2}-2n^{2}}{m^{2}+2n^{2}},v=\frac{-2mn}{m^{2}+2n^{2}}$.

$\endgroup$

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.