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

Question

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.

Answer 1

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.

Answer 2

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.