Project Euler Problem 764

Solution

Answer: 255228881

Write

$$16x^2+y^4=z^2.$$

This can be rewritten as

$$(4x)^2+(y^2)^2=z^2,$$

so every solution comes from a Pythagorean triple.

There are two parity cases.

For $y$ odd, the triple is primitive:

$$4x=2mn,\qquad y^2=m^2-n^2,\qquad z=m^2+n^2,$$

with $\gcd(m,n)=1$, opposite parity.

Since

$$y^2=(m-n)(m+n),$$

and the factors are coprime odd numbers, we must have

$$m-n=a^2,\qquad m+n=b^2,$$

with $a,b$ coprime odd integers.

This gives

$$x=\frac{b^4-a^4}{8},\qquad y=ab,\qquad z=\frac{a^4+b^4}{2}.$$

For $y$ even, write $y=2Y,\ z=2Z$. Then

$$x^2+Y^4=\left(\frac Z2\right)^2.$$

Applying the primitive Pythagorean parametrization again yields

$$x=a^4-4b^4,\qquad y=4ab,\qquad z=4(a^4+4b^4),$$

with $a$ odd and $\gcd(a,b)=1$.

Using these two complete parametrizations, we enumerate all primitive solutions with

$$x,y,z\le 10^{16},$$

summing $x+y+z$ modulo $10^9$.

The parametrization reproduces the checks:

Carrying the computation through to $10^{16}$ gives

$$S(10^{16}) \equiv 255228881 \pmod{10^9}.$$

Answer: 255228881