Diophantine Equations II: Descent and Vieta Jumping

If \(x^2=2y^2\), then \(x^2\) is even, so \(x=2u\). Then \(4u^2=2y^2\), hence \(y^2=2u^2\), and \(y\) is also even: \(y=2v\). We get \(u^2=2v^2\), a smaller positive solution. Infinite descent is impossible.

From \(x^2=5y^2\), \(5\mid x^2\), hence \(x=5u\). Then \(25u^2=5y^2\), so \(y^2=5u^2\), and \(5\mid y\). With \(y=5v\), we get \(u^2=5v^2\), a smaller solution. Impossible.

Modulo \(3\), \(x^2+y^2\equiv 0\). This is possible only when \(x\equiv y\equiv 0\pmod 3\). Then \(9\mid x^2+y^2\), so \(9\mid 3z^2\), and \(3\mid z\). Dividing \(x,y,z\) by \(3\), we get a smaller nonzero solution. Contradiction.

Squares modulo \(7\) are \(0,1,2,4\). A sum of two such residues can be \(0\) modulo \(7\) only if both residues are \(0\). Hence \(7\mid x\) and \(7\mid y\). Then \(49\mid x^2+y^2\), so \(7\mid z\). Dividing all variables by \(7\) gives a smaller solution, impossible.

The right side is divisible by \(4\). A square modulo \(4\) is \(0\) or \(1\). For \(x^2+y^2\equiv 0\pmod 4\), both squares must be \(0\), so \(x,y\) are even. Thus \(x,y\) have common divisor \(2\), so the solution cannot be primitive.

Let \(x\le y\) and take a minimal solution. As a quadratic in \(y\), the equation is \(Y^2-4xY+x^2+1=0\). The second root is \(y'=4x-y=\frac{x^2+1}{y}\), positive and integral. Since \(y\ge x\), \(y'\le x+\frac{1}{x}\), so \(y'\le x\). Equality \(y'=x\) would give \(y=3x\), hence \(x^2+9x^2+1=12x^2\), or \(2x^2=1\), impossible. We get a smaller solution. For \(x=1\), the discriminant is \(16-8=8\), not a square. Contradiction.

Let \(x\le y\) and take a minimal solution. For \(x=1\), \(y^2-3y+3=0\) has no integer roots; for \(x=2\), \(y^2-6y+6=0\) also has no integer roots. For \(x\ge 3\), the second root is \(y'=3x-y=\frac{x^2+2}{y}\), positive and integral. Since \(y\ge x\), \(y'\le x+\frac{2}{x}

Let \(x\le y\). For \(x=1\), \(y^2-3y+2=0\), so \(y=1\) or \(2\). For \(x>1\), the second root is \(y'=3x-y=\frac{x^2+1}{y}\). It is positive and integral. Since \(y\ge x\), \(y'\le x+\frac{1}{x}1\), \(0

Write \(Y^2-mxY+x^2+c=0\). One root is \(y\). By Vieta's formula, the sum of the roots is \(mx\), so the second root is \(y'=mx-y\). Since the coefficients are integers and \(y'\) is assumed to be a positive integer, substituting the second root again makes the quadratic zero. Hence \(x^2+(y')^2+c=mxy'\).

Let \(x\le y\) and take a solution with minimal sum. For \(x=1\), we get \(y^2-ky+2=0\). Its discriminant \(k^2-8\) is not a square: if \(k^2-8=t^2\), then \((k-t)(k+t)=8\), impossible for \(k\ge 4\). Now let \(x\ge 2\). The second root is \(y'=kx-y=\frac{x^2+1}{y}\), positive and integral. Since \(y\ge x\), \(y'\le x+\frac{1}{x}

Consider \(Z^2-3xyZ+x^2+y^2=0\). One root is \(z\), the other is \(z'=3xy-z\). The product of the roots is \(x^2+y^2>0\), so \(zz'>0\); since \(z>0\), \(z'>0\). By Vieta's formula, the second root satisfies the same quadratic equation, so \(x^2+y^2+(z')^2=3xyz'\).

Fourth powers modulo \(7\) are \(0,1,2,4\). A sum of two such residues can be \(0\pmod 7\) only as \(0+0\). Hence \(7\mid x\) and \(7\mid y\). Write \(x=7x_1\), \(y=7y_1\). Then the left side is divisible by \(7^4\), so \(7z^2\) is divisible by \(7^4\), meaning \(z^2\) is divisible by \(7^3\). Since valuations in a square are even, \(7^2\mid z\); write \(z=49z_1\). Substitution gives \(7^4(x_1^4+y_1^4)=7\cdot 7^4 z_1^2\), hence \(x_1^4+y_1^4=7z_1^2\). We have obtained a smaller positive solution. Infinite descent is impossible, so no original solution exists.

If \(p\nmid y\), then \((xy^{-1})^2\equiv -1\pmod p\). Raise both sides to \(\frac{p-1}{2}\). The left side is \(1\), while the right side is \((-1)^{(p-1)/2}=-1\), since \(p\equiv 3\pmod 4\). Contradiction. Hence \(p\mid y\), and then \(p\mid x\) follows from \(p\mid x^2+y^2\).

Since \(11\equiv 3\pmod 4\) and \(11\mid x^2+y^2\), we get \(11\mid x\) and \(11\mid y\). Then \(121\mid x^2+y^2=11z^2\), so \(11\mid z\). Dividing all variables by \(11\), we obtain a smaller nonzero solution. Infinite descent is impossible.

The equation gives \(p\mid x^2+y^2\). By the lemma for primes \(3\pmod 4\), \(p\mid x\) and \(p\mid y\). Then \(p^2\mid x^2+y^2=pz^2\), so \(p\mid z^2\), hence \(p\mid z\). Dividing \(x,y,z\) by \(p\), we get a smaller nonzero solution of the same equation. This gives infinite descent, impossible in positive integers.

From \(x^4+y^4\equiv 0\pmod 3\), both \(x\) and \(y\) are divisible by \(3\). Then the left side is divisible by \(81\), so \(3z^4\) is divisible by \(81\), and \(z\) is divisible by \(3\). Dividing \(x,y,z\) by \(3\) preserves the equation and gives a smaller nonzero solution. Contradiction.

A fourth power modulo \(5\) is \(0\) or \(1\). Therefore \(x^4+y^4\equiv 0\pmod 5\) implies \(5\mid x\) and \(5\mid y\). Then \(5^4\mid x^4+y^4=5z^4\), so \(5^3\mid z^4\), hence \(5\mid z\). Dividing all variables by \(5\), we get a smaller nonzero solution of the same equation. Contradiction.

Squares modulo \(5\) are \(0,1,4\). Thus \(2y^2\) has residues \(0,2,3\). The sum \(x^2+2y^2\) can be \(0\pmod 5\) only if both terms are \(0\). Hence \(5\mid x,y\). Then \(25\mid x^2+2y^2=5z^2\), so \(5\mid z\). Dividing all variables by \(5\), we get a smaller solution of the same equation. Contradiction.

By Problem 8, all solutions are neighbouring terms of the sequence \(1,1,2,5,13,34,89,233,\ldots\), where \(a_{n+1}=3a_n-a_{n-1}\). The bound \(x+y\le 150\) leaves the neighbouring pairs \((1,1),(1,2),(2,5),(5,13),(13,34),(34,89)\) and their swaps. The pair \((89,233)\) already has sum greater than \(150\).

Let \(x\le y\). For \(x=1\), \(y^2-4y+4=0\), so \(y=2\). For \(x=2\), \(y^2-8y+7=0\), so \(y=1\) or \(7\); this matches neighbouring terms of the future sequence. For \(x=3\), the discriminant \(144-48=96\) is not a square. For \(x\ge 4\), the second root is \(y'=4x-y=\frac{x^2+3}{y}\), positive and integral. Since \(y\ge x\), \(y'\le x+\frac{3}{x}

Reversing the jump: if \((a,b)\) is a solution, then \((b,4b-a)\) is also a solution. Starting from \((1,2)\), define \(a_0=1\), \(a_1=2\), \(a_{n+1}=4a_n-a_{n-1}\). All solutions are \((a_n,a_{n+1})\) and swaps, \(n\ge 0\).