# Thread: [SOLVED] Solving Diophantine Equations:

1. Originally Posted by Samson
So would it be correct to say that

(x,y,z)=(2,1,3) is one solution, but

$x=m^2-5n^2$, $y=2mn$, $z=m^2+5n^2$

is a parameterization of all solutions that meet the aforementioned conditions?
We thought it was so, but actually it is only a parametrisation of some solutions. roninpro brought up that (2,1,3) can't be generated by the proposed system, which I agree with. So we have some sorting out to do in order to know we've gotten all solutions, but in the meantime, you do have an infinite number of solutions at your disposal.

2. Originally Posted by undefined
We thought it was so, but actually it is only a parametrisation of some solutions. roninpro brought up that (2,1,3) can't be generated by the proposed system, which I agree with. So we have some sorting out to do in order to know we've gotten all solutions, but in the meantime, you do have an infinite number of solutions at your disposal.
Okay! Please do let me know when you have sorted it out so that all solutions have been found. I really appreciate all of your help guys!

3. Originally Posted by roninpro
Taking the idea from the Wikipedia article, I used the following:

$a=m^2-5n^2$, $b=2mn$, $c=m^2+5n^2$

You can put this into the equation to see that it does indeed work. Then I suppose that you can throw in an extra parameter $k$ to get all solutions (with some possible overlap).
Don't ask how but I believe I've found all solutions. It generalizes roninpro's solution too and it has twice as many parameters.

Choose $a,b,c,d$ such that $ad=bc$ and we get $\begin{cases} x=ab-5cd\\y=ad+bc\\z=ab+5cd \end{cases}$

I've convinced myself that these cover all solutions but can't/don't feel like saying why (to much typing )...

Assuming this is right, this can be generalized to the equation $x^2+ty^2=z^2$.

4. Originally Posted by chiph588@
Don't ask how but I believe I've found all solutions. It generalizes roninpro's solution too and it has twice as many parameters.

Choose $a,b,c,d$ such that $ad=bc$ and we get $\begin{cases} x=ab-5cd\\y=ad+bc\\z=ab+5cd \end{cases}$

I've convinced myself that these cover all solutions but can't/don't feel like saying why (to much typing )...

Assuming this is right, this can be generalized to the equation $x^2+ty^2=z^2$.
So are those "parameterized solutions then?" Does that meet all of the conditions in the first post?

5. I can't speak for chiph588@'s parametrisation although it looks interesting.

I have a proof that roninpro's parametrisation can be modified to obtain all solutions. I will post it for review when I have time, but here is the resolution to the sticking point brought up earlier. Consider that when m = 5 and n = 1 we have (x,y,z) = (20,10,30); dividing by gcd(x,y,z) = 10, we obtain (x,y,z) = (2,1,3). Following this procedure, I claim all solutions are obtainable.

I wrote out a lengthy proof on paper involving rational points on an ellipse and got exactly roninpro's parametrisation as the end result; it will take a while to type out, won't get to it for some hours.

6. Originally Posted by undefined
I can't speak for chiph588@'s parametrisation although it looks interesting.

I have a proof that roninpro's parametrisation can be modified to obtain all solutions. I will post it for review when I have time, but here is the resolution to the sticking point brought up earlier. Consider that when m = 5 and n = 1 we have (x,y,z) = (20,10,30); dividing by gcd(x,y,z) = 10, we obtain (x,y,z) = (2,1,3). Following this procedure, I claim all solutions are obtainable.

I wrote out a lengthy proof on paper involving rational points on an ellipse and got exactly roninpro's parametrisation as the end result; it will take a while to type out, won't get to it for some hours.
I know that the only solutions I can consider are when the GCD[x,y,z]=1, and you have an example of where it equals 10.... Doesn't that violate the conditions or is there a typo or something I'm missing?

7. Originally Posted by Samson
I know that the only solutions I can consider are when the GCD[x,y,z]=1, and you have an example of where it equals 10.... Doesn't that violate the conditions or is there a typo or something I'm missing?
Yes, I should have been more careful about that point.

So we have

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

and suppose we are interested in all integer solutions. First note that there are trivial solutions $(x,0,x)$ for all integers $x$. Without loss of generality we can consider just solutions in positive integers for the non-trivial solutions. It can be seen that if $(x,y,z)$ satisfies, then $(kx,ky,kz)$ satisfies for any positive integer $k$, thus we can obtain all non-trivial solutions from the primitive solutions having $\gcd(x,y,z) = 1$. (This is standard use of the term primitive.) As for the problem statement restricting $x$ to odd; I don't know what the motivation is for that, but we can just discard any solutions for which $x$ is even at the very end.

Now for the actual proof/derivation I mentioned earlier. Disclaimer is that my solution method is not original.

Let $a=\frac{y}{z}$ and $b=\frac{x}{z}$, from which we obtain

$(bz)^2 + 5(az)^2 = z^2$

$5a^2 + b^2 = 1$

This is an equation of an ellipse; solutions to the problem correspond with points on the ellipse. Consider the point $A\ (0,-1)$ on the ellipse. A parametrisation for all non-vertical lines through $A$ is $(a, ta - 1)$, where $t$ is the slope of the line. The intersection of the line with the ellipse is given by

$5a^2 + (ta-1)^2 = 1$

$5a^2 + t^2a^2 - 2ta + 1 = 1$

$a(5+t^2) = 2t$

$a = \frac{2t}{t^2 + 5}$

and

$b = t\left( \frac{2t}{t^2 + 5} \right) - 1$

$b = \frac{2t^2-5-t^2}{t^2+5}$

$b = \frac{t^2 - 5}{t^2 + 5}$

It can be seen that if $t$ is rational then $a$ and $b$ are rational. Replace $t$ with $\frac{m}{n}$ and we have

$a = \frac{2\left( \frac{m}{n}\right)}{\left( \frac{m}{n} \right)^2 + 5}$

$b = \frac{\left( \frac{m}{n} \right)^2 - 5}{\left( \frac{m}{n} \right)^2 + 5}$

which simplifies to

$a = \frac{2mn}{m^2 + 5n^2}$

$b = \frac{m^2-5n^2}{m^2+5n^2}$

Now we can take the parametrisation $(x',y',z') = (m^2-5n^2, 2mn, m^2+5n^2)$. Let $g = \gcd(x',y',z')$. Then we have a parametrisation for primitive solutions $(x,y,z) = \left(\frac{x'}{g},\frac{y'}{g},\frac{z'}{g} \right)$. We must choose positive integers $m$ and $n$ such that

$m^2-5n^2 > 0$

$m > \sqrt{5}n$

Restricting $\gcd(m,n)=1$, we obtain all primitive triples uniquely.

8. Originally Posted by undefined
Yes, I should have been more careful about that point.

So we have

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

and suppose we are interested in all integer solutions. First note that there are trivial solutions $(x,0,x)$ for all integers $x$. Without loss of generality we can consider just solutions in positive integers for the non-trivial solutions. It can be seen that if $(x,y,z)$ satisfies, then $(kx,ky,kz)$ satisfies for any positive integer $k$, thus we can obtain all non-trivial solutions from the primitive solutions having $\gcd(x,y,z) = 1$. (This is standard use of the term primitive.) As for the problem statement restricting $x$ to odd; I don't know what the motivation is for that, but we can just discard any solutions for which $x$ is even at the very end.

Now for the actual proof/derivation I mentioned earlier. Disclaimer is that my solution method is not original.

Let $a=\frac{y}{z}$ and $b=\frac{x}{z}$, from which we obtain

$(bz)^2 + 5(az)^2 = z^2$

$5a^2 + b^2 = 1$

This is an equation of an ellipse; solutions to the problem correspond with points on the ellipse. Consider the point $A\ (0,-1)$ on the ellipse. A parametrisation for all lines through $A$ with slope $t$ is $(a, ta - 1)$. The intersection of the line with the ellipse is given by

$5a^2 + (ta-1)^2 = 1$

$5a^2 + t^2a^2 - 2ta + 1 = 1$

$a(5+t^2) = 2t$

$a = \frac{2t}{t^2 + 5}$

and

$b = 2\left( \frac{2t}{t^2 + 5} \right) - 1$

$b = \frac{2t^2-5-t^2}{t^2+5}$

$b = \frac{t^2 - 5}{t^2 + 5}$

It can be seen that if $t$ is rational then $a$ and $b$ are rational. Replace $t$ with $\frac{m}{n}$ and we have

$a = \frac{2\left( \frac{m}{n}\right)}{\left( \frac{m}{n} \right)^2 + 5}$

$b = \frac{\left( \frac{m}{n} \right)^2 - 5}{\left( \frac{m}{n} \right)^2 + 5}$

which simplifies to

$a = \frac{2mn}{m^2 + 5n^2}$

$b = \frac{m^2-5n^2}{m^2+5n^2}$

Now we can take the parametrisation $(x',y',z') = (m^2-5n^2, 2mn, m^2+5n^2)$. Let $g = \gcd(x',y',z')$. Then we have a parametrisation for primitive solutions $(x,y,z) = \left(\frac{x'}{g},\frac{y'}{g},\frac{z'}{g} \right)$. We must choose positive integers $m$ and $n$ such that

$m^2-5n^2 > 0$

$m > \sqrt{5}n$

Restricting $\gcd(m,n)=1$, we obtain all primitive triples uniquely.
Okay, that is a lot of text, and I followed it, except I'm missing what is the actual answer to the problem (the parameterized solutions in integers of the Diophantine Equation where GCD[x,y,z]=1 (x,y,z)>0 and x is odd.

9. Originally Posted by Samson
Okay, that is a lot of text, and I followed it, except I'm missing what is the actual answer to the problem (the parameterized solutions in integers of the Diophantine Equation where GCD[x,y,z]=1 (x,y,z)>0 and x is odd.
I don't mean to be rude, but if you don't see what the answer to the problem is, then you didn't follow what I wrote!

Well I guess that response isn't very helpful to you. To answer your question, the parametrisation is given here:

Originally Posted by undefined
Now we can take the parametrisation $(x',y',z') = (m^2-5n^2, 2mn, m^2+5n^2)$. Let $g = \gcd(x',y',z')$. Then we have a parametrisation for primitive solutions $(x,y,z) = \left(\frac{x'}{g},\frac{y'}{g},\frac{z'}{g} \right)$. We must choose positive integers $m$ and $n$ such that

$m^2-5n^2 > 0$

$m > \sqrt{5}n$

Restricting $\gcd(m,n)=1$, we obtain all primitive triples uniquely.
Whenever we come across a solution with $x$ even, we discard it. (I would look at what restrictions to place on $m$ and $n$ to ensure this, but I don't understand the motivation for restricting $x$ to odd integers anyway, so I don't see the worth of it. Maybe it refers to another solution method for which $x$ even poses complications.)

10. Originally Posted by undefined
Restricting $\gcd(m,n)=1$, we obtain all primitive triples uniquely.
This is a very neat way of looking at this problem!

My only question is if we're dividing by $\gcd(x',y',z')$, why do we want $\gcd(m,n)=1$?

11. Originally Posted by chiph588@
This is a very neat way of looking at this problem!

My only question is if we're dividing by $\gcd(x',y',z')$, why do we want $\gcd(m,n)=1$?
I don't understand either because I thought only GCD[x,y,z]=1, and undefined has $\gcd(x',y',z') = g$ and GCD[m,n]=1 ...

12. Originally Posted by Samson
I don't understand either because I thought only GCD[x,y,z]=1, and undefined has $\gcd(x',y',z') = g$ and GCD[m,n]=1 ...
He divides by g to obtain GCD[x,y,z]=1.

13. Originally Posted by chiph588@
He divides by g to obtain GCD[x,y,z]=1.
Ah, I see. But have we figured out why the GCD[m,n]=1 ?

14. Originally Posted by chiph588@
This is a very neat way of looking at this problem!

My only question is if we're dividing by $\gcd(x',y',z')$, why do we want $\gcd(m,n)=1$?
To prevent duplicate counting. (The problem statement doesn't require this, but it is a nice thing to have.) A rational point $(a,b)$ on the ellipse represents a class of solutions $(kx,ky,kz), k \in \mathbb{Z}, k > 0$ for some primitive $(x,y,z)$. Since we defined $t=\frac{m}{n}$, restricting $\gcd(m,n)=1$ ensures that we will count each (positive) rational $t$ exactly once.

15. Originally Posted by undefined
To prevent duplicate counting. (The problem statement doesn't require this, but it is a nice thing to have.) A rational point $(a,b)$ on the ellipse represents a class of solutions $(kx,ky,kz), k \in \mathbb{Z}, k > 0$ for some primitive $(x,y,z)$. Since we defined $t=\frac{m}{n}$, restricting $\gcd(m,n)=1$ ensures that we will count each (positive) rational $t$ exactly once.
Brilliant reasoning, really, quite brilliant! Props and many thanks!

Page 2 of 2 First 12