#2 Quadratic Residues and Modular Obstructions

If the number is even, \(n=2k\), then \(n^2=4k^2\), and \(k^2\pmod4\) is \(0\) or \(1\), giving \(0\) or \(4\). If the number is odd, \(n=2k+1\), so \(n^2=4k(k+1)+1\); since \(k(k+1)\) is even, \(n^2\equiv1\) or \(9\pmod{16}\). Thus the possible residues are \(0,1,4,9\).

A square modulo \(4\) is \(0\) or \(1\). Hence a sum of two squares modulo \(4\) can be only \(0,1,2\). The right-hand side has residue \(3\), contradiction.

For \(n\equiv0,1,2,3,4,5,6\pmod7\), the expression \(n^2+n+1\) gives residues \(1,3,0,6,0,3,1\). Thus divisibility by \(7\) holds exactly when \(n\equiv2\) or \(n\equiv4\pmod7\).

We need \(n^2\equiv-1\equiv4\pmod5\). This occurs for \(n\equiv2\) or \(n\equiv3\pmod5\).

It is enough to check residues \(0,1,\ldots,9\). Their squares modulo \(10\) are \(0,1,4,9,6,5,6,9,4,1\). The residues \(2,3,7,8\) do not appear.

The squares \(0^2,1^2,\ldots,6^2\) modulo \(13\) are \(0,1,4,9,3,12,10\). Hence \(x\equiv5\) or \(x\equiv-5\equiv8\pmod{13}\).

A sum of two elements from \(\{0,1,4\}\) modulo \(8\) can be \(0,1,2,4,5\). Residue \(7\) is impossible. The right-hand side is \(7\pmod8\), so there are no solutions.

Modulo \(8\), each square is \(0,1\), or \(4\). Checking sums of three such residues shows that residue \(7\) is impossible: the possible residues include \(0,1,2,3,4,5,6\), but not \(7\). The right-hand side has residue \(7\), contradiction.

We have \(4(n^2+3n+5)=(2n+3)^2+11\). Divisibility by \(11\) is equivalent to \((2n+3)^2\equiv0\pmod{11}\), so \(2n+3\equiv0\pmod{11}\). Since \(2^{-1}\equiv6\pmod{11}\), we get \(n\equiv-18\equiv4\pmod{11}\).

Since \(p\mid a^2+1\), we have \(a^2\equiv-1\pmod p\), and \(p\nmid a\). Then \(a^4\equiv1\), but \(a^2\not\equiv1\). Hence the order of \(a\) modulo \(p\) is \(4\). The order of an element divides \(p-1\), so \(4\mid p-1\), meaning \(p\equiv1\pmod4\).

Assume \(p\nmid y\). Then \(y^{-1}\pmod p\) exists, and \(x^2+y^2\equiv0\) gives \((xy^{-1})^2\equiv-1\pmod p\). But for a prime \(p\equiv3\pmod4\), \(-1\) is not a square. Contradiction. Hence \(p\mid y\), and then \(p\mid x^2+y^2\) gives \(p\mid x^2\), so \(p\mid x\).

The condition is equivalent to \(x^2\equiv1\pmod3\) and \(x^2\equiv4\pmod5\). The first gives \(x\not\equiv0\pmod3\), and the second gives \(x\equiv\pm2\pmod5\). Combining the classes gives \(x\equiv2,7,8,13\pmod{15}\).

The condition \(x^2\equiv1\pmod{24}\) is equivalent to \(x^2\equiv1\pmod8\) and \(x^2\equiv1\pmod3\). Modulo \(8\), this means \(x\) is odd. Modulo \(3\), it means \(x\not\equiv0\pmod3\). Therefore, among residues \(0,\ldots,23\), the solutions are all odd residues not divisible by \(3\): \(1,5,7,11,13,17,19,23\). Direct checking confirms that each gives square \(1\pmod{24}\).

We need to solve \(x^2\equiv-1\pmod5\) and \(x^2\equiv-1\pmod{13}\). Modulo \(5\): \(x\equiv\pm2\). Modulo \(13\): \(x\equiv\pm5\). Combining the four pairs by CRT gives \(x\equiv8,18,47,57\pmod{65}\).

From \(x^2\equiv y^2\pmod p\), we get \(p\mid (x-y)(x+y)\). Since \(p\) is prime, it divides one of the factors. Hence \(x\equiv y\pmod p\) or \(x\equiv -y\pmod p\).

Squares modulo \(3\) are \(0\) or \(1\). If \(3\mid x^2+y^2\), the sum of residues cannot be \(1+0\) or \(1+1\), so both squares have residue \(0\). Thus \(3\mid x\) and \(3\mid y\). Then \(9\mid x^2+y^2=3z^2\), so \(3\mid z\). Dividing all variables by \(3\) gives a smaller solution. A nonzero solution would lead to infinite descent, so only \(x=y=z=0\) is possible.

Since \(p\nmid b\), put \(t\equiv ab^{-1}\pmod p\). Then \(t^2+t+1\equiv0\). Multiplying by \(t-1\), we get \(t^3-1\equiv0\). Also \(t\not\equiv1\), otherwise \(3\equiv0\pmod p\), impossible. Hence the order of \(t\) is \(3\). The order divides \(p-1\), so \(3\mid p-1\), meaning \(p\equiv1\pmod3\).

Assume not both numbers are divisible by \(p\). If \(p\mid b\), then the form gives \(p\mid a^2\), hence \(p\mid a\), contradiction. Thus we may assume \(p\nmid b\). Then \(t=ab^{-1}\) satisfies \(t^2+t+1\equiv0\pmod p\), and as in the previous problem this gives an element of order \(3\). Hence \(3\mid p-1\), so \(p\equiv1\pmod3\), contradicting \(p\equiv2\pmod3\). Therefore \(p\mid a\) and \(p\mid b\).

Let \(p\equiv3\pmod4\) and \(p\mid x^2+y^2\). By the lemma, \(p\mid x\) and \(p\mid y\), so \(x=px_1\), \(y=py_1\). Then \(N=p^2(x_1^2+y_1^2)\). If \(p\) again divides \(x_1^2+y_1^2\), repeat the same step. Each step decreases the exponent of \(p\) by \(2\). Therefore the exponent of \(p\) in \(N\) must be even.

The equation implies \(p\mid x^2+y^2\). By the lemma for primes \(p\equiv3\pmod4\), we get \(p\mid x\) and \(p\mid y\). Then \(p^2\mid x^2+y^2=pz^2\), so \(p\mid z\). Dividing \(x,y,z\) by \(p\), we obtain a smaller integer solution. If a nonzero solution existed, iteration would give infinite descent. Therefore no nonzero solution exists, and the only solution is \(x=y=z=0\).