# Solving $x^2 \cdot y^2 + x^2 + y^2 = c^2$ with $x$, $y$, $c \in \mathbb{Z}^+$

I am working on Project Euler 390.

The question is about triangles, and finding the area of a triangle with sides $\sqrt{a^2+1}, \sqrt{b^2+1}$ and $\sqrt{a^2+b^2}$, with $a, b \in \mathbb{Z}$. I have narrowed the problem down to solving the equation

$$x^2 \cdot y^2 + x^2 + y^2 = (2\cdot c)^2 \text{ with } x, y, c \in \mathbb{Z}^+$$

This is not a problem for $c \le 10^6$ (brute force), but I have to calculate up to $10^{10}$. I would like to know how to solve these kind of equations, without any brute force attack. I have searched for a few days on Google, but the general solutions to the Diophantine equations I found were never appliable to my problem.

Any suggestions are welcome (even the name of this kind of equation), although I would appreciate not being told the answer to the problem.

-
Oops, you're right. I'll delete my comment. – celtschk Aug 15 '12 at 12:11
We do have $(2c)^2+1=(x^2+1)(y^2+1)$ which indicates that both factors on the RHS are odd, and x,y are therefore even. – Mark Bennet Aug 15 '12 at 12:12
@MarkBennet Thanks for the comment, I found that out already. I still require 25 minutes of computing power to calculate all the $(x, y)$ for $c \le 10^6$. $10^{10}$ is just not possible brute force. – Hidde Aug 15 '12 at 12:19
It seems to me that this curve (for a fixed $c$) is closely related to Edwards' curves. May be with a twist (Daniel Bernstein and Tanja Lange have studied the twisted curves)? Anyway, they are birationally equivalent to elliptic curves meaning that parametrizing the rational points may be a tall order. – Jyrki Lahtonen Aug 15 '12 at 18:08
I don't know how much use it is, but another form is $(x+y)^2 + (xy - 1)^2 = 4c^2 + 1$. – SiliconCelery Aug 15 '12 at 18:17

## 2 Answers

It seems like the problem is that you simply can't afford to compute all the solutions for all valid values of $c$. As Mark's comment notes, your equation is equivalent to saying that $(2c)^2+1 = (x^2+1)(y^2+1)$, and trying to factor each $4c^2+1$ for all $c$ in your range is just infeasible. So, why not go the other way? Rather than trying to solve your equation for each $c$, instead iterate over all even $x$ from $1\leq x\leq \approx 2\cdot 10^{10}$ (and it's not hard to find your specific upper bound), and compute your maximum value of $y$ as $\displaystyle{y_{\mathrm{max}} = \sqrt{\frac{4\cdot 10^{20}+1}{x^2+1}-1}}$; then for every even $y\leq y_{\mathrm{max}}$ you can compute $(x^2+1)(y^2+1)-1$ and test whether it's a perfect square (this test should be pretty quick); this will involve doing roughly $\displaystyle{\sum_{i=0}^{10^{10}}\left\lfloor\frac{10^{10}}{i}\right\rfloor}\approx 10^{10}\ln(10^{10})\approx 23\cdot 10^{10}$ tests, but that should be relatively feasible. What's more, with a careful application of symmetry you can shrink your upper bound for $x$ to something more on the order of $10^5$ (since every solution $(x,y,c)$ corresponds to a solution $(y,x,c)$, you can assume $x\geq y$) and shave your total number of tests approximately in half.

-
I have read your answer, and I agree a lot. I am letting my mind go over it while I am sleeping, that always helps. The reduction of the range of $x$ is good, it should help. I hope though that something in the range of $10^{11}$ is computable. – Hidde Aug 15 '12 at 21:12
Another thing to consider is sieving, based on the idea that there are only a certain number of values that a square can have mod most primes. For instance, if you consider mod 5, then $1^2=4^2=1, 2^2=3^2=4$, so the possible values for $x^2+1$ are $0,1,2$; in particular, $x$ and $y$ can't both be $\equiv \pm 1\pmod 5$, since then $x^2+1\equiv 2$, $y^2+1\equiv 2$, and $(2c)^2= (x^2+1)(y^2+1)-1$ would have to be $\equiv 3\pmod 5$; this lets you eliminate roughly 15% of all possibilities, and using other primes should let you shave off quite a bit more. – Steven Stadnicki Aug 15 '12 at 21:53

Let $y=x+a=>x^2\cdot y^2+x^2+y^2=x^2(x+a)^2+x^2+(x+a)^2=x^4+x^3(2a)+x^2(a^2+2)+x(2a)+a^2$

Let this be equal to $(x^2+px+q)^2$ where p,q are integers, so that $c=x^2+px+q$.

So, $x^4+x^3(2a)+x^2(a^2+2)+x(2a)+a^2=x^4+x^3(2p)+x^2(2q+p^2)+x(2pq)+q^2$

Expanding the RHS and comparing the coefficients of different powers of x,

coefficients of cubic power $=>p=a$

coefficients of square $=>a^2+2=2q+p^2=>q=1$ as $p=a$

coefficients of first degree $=>2pq=2a=>q=1$

constants $=>q^2=a^2=>a=±q=±1=>p=a=±1$

So, $y=x±1$.

The RHS($x^2+px+q$) reduces to $x^2±x+1$ but unfortunately this must be odd as x is even, so can not be equals to 2c.

So, there can be no solution following this approach.

Now, if we arrange $x^4+x^3(2a)+x^2(a^2+2)+x(2a)+a^2=(2c)^2$ as a quadratic equation of a, $a^2(x^2+1)+2a(x^3+x)+x^4+2x^2-4c^2=0$--->(1).

As a=x-y is integer, so the discriminant($D^2$) of (1) must be perfect square.

So,$D^2=(2x^3+2x)^2-4(x^2+1)(x^4+2x^2-4c^2)$

So, D is even=(2E, say)

$=>E^2=(x^3+x)^2-(x^2+1)(x^4+2x^2-4c^2)=4c^2+4c^2x^2-x^4-x^2$

$=>x^4-(4c^2-1)x^2+E^2-4c^2=0$--->(2)

As x is integer, the discriminant($D_1^2$) of (2) must be perfect square.

So, $D_1^2=(4c^2-1)^2-4.1.(E^2-4c^2)$

$=>D_1^2+(2E)^2=(4c^2+1)^2$, clearly $D_1$ is odd.

Now $4c^2+1$ can always be expressed as the sum of two squares(not necessarily in a unique way)=($r^2+s^2$, say), where r,s are integers.

If we take $E=rs =>D_1=r^2-s^2$

So,$x^2=\frac{4c^2-1 ± D_1}{2}=\frac{r^2+s^2-2±(r^2-s^2)}{2}=r^2-1\ or s^2-1$

Now, either I have made some mistake or I doubt the existence of a non-trivial solution.

-
You're looking for parameterized solutions - while the only way that the quartics can be the same as a polynomial in $x$ is for individual terms to be the same, they can coincidentally be the same at a particular x in any number of ways. (e.g., $3x^2-2x+5$ and $2x^2-x+11$ are not the same polynomial, but they both happen to evaluate to $26$ at $x=3$.) – Steven Stadnicki Aug 15 '12 at 17:22
I do agree with you for the 1st approach, but this method sometimes leads to solution. Acceptably, this method does not ensure the non-existence of the solution. What about the 2nd approach. – lab bhattacharjee Aug 15 '12 at 17:37
To be honest, I didn't look at the second approach closely enough, although I feel like it may suffer from the same problem. More to the point, there's a known non-trivial solution (the one that corresponds to the solution in the original problem statement), so I doubt any mathematics that doubts the existence of a solution that's already known to exist. :-) – Steven Stadnicki Aug 15 '12 at 18:00
I really don't understand what you are trying to do in your solutions. Maybe I am not mathematically educated enough. If it is really a solution to my problem, it would be nice if you could explain a little what you are doing. – Hidde Aug 15 '12 at 19:40