Practice
Find the remainder of \(2026\) upon division by \(7\).
Subtract a nearby multiple of \(7\).
\(7\cdot289=2023\), so \(2026=7\cdot289+3\). The remainder is \(3\).
Prove that the square of an integer modulo \(4\) can only have residue \(0\) or \(1\).
Check even and odd integers.
If \(n=2k\), then \(n^2=4k^2\equiv0\pmod4\). If \(n=2k+1\), then \(n^2=4k^2+4k+1\equiv1\pmod4\).
Make the table of square residues modulo \(8\).
It is enough to check residues \(0,1,\ldots,7\).
The squares of residues \(0,1,2,3,4,5,6,7\) modulo \(8\) are \(0,1,4,1,0,1,4,1\). Hence only \(0,1,4\) are possible.
Find the last digit of \(3^{2025}\).
Look at the cycle of last digits of powers of \(3\).
The last digits of powers of \(3\) are \(3,9,7,1\), with cycle length \(4\). Since \(2025\equiv1\pmod4\), the last digit is \(3\).
Find all residues \(n\pmod5\) for which \(n^2\equiv1\pmod5\).
Check residues \(0,1,2,3,4\).
Squares modulo \(5\): \(0^2\equiv0\), \(1^2\equiv1\), \(2^2\equiv4\), \(3^2\equiv4\), \(4^2\equiv1\). Thus \(n\equiv1\) and \(n\equiv4\pmod5\) work.
Prove that \(x^2+y^2=4z+3\) has no integer solutions.
Consider the equation modulo \(4\).
A square modulo \(4\) is \(0\) or \(1\). Hence \(x^2+y^2\) can have residue \(0,1,2\), but not \(3\). The right side has residue \(3\). Contradiction.
Prove that \(x^2+y^2=8z+7\) has no integer solutions.
Use squares modulo \(8\).
Squares modulo \(8\) are \(0,1,4\). A sum of two such residues can be \(0,1,2,4,5\), but not \(7\). The right side has residue \(7\). Contradiction.
Find all integers \(n\) for which \(7\mid n^2+n+1\).
Check \(n=0,1,\ldots,6\) modulo \(7\).
The values of \(n^2+n+1\) modulo \(7\) for \(n=0,1,2,3,4,5,6\) are \(1,3,0,6,0,3,1\). Therefore \(n\equiv2\) or \(n\equiv4\pmod7\).
Prove that no square of an integer has remainder \(2\) or \(3\) upon division by \(4\).
Use the table of squares modulo \(4\).
Every square modulo \(4\) is \(0\) or \(1\). Residues \(2\) and \(3\) do not occur, so a square cannot have these remainders.
Find the last digit of \(7^{2026}\).
The last-digit cycle of powers of \(7\) has length \(4\).
The cycle is \(7,9,3,1\). Since \(2026\equiv2\pmod4\), take the second digit of the cycle. The answer is \(9\).
Use congruences to prove that \(n^2+n\) is even for every integer \(n\).
Check residues of \(n\) modulo \(2\).
If \(n\equiv0\pmod2\), then \(n^2+n\equiv0\). If \(n\equiv1\pmod2\), then \(n^2+n\equiv1+1\equiv0\pmod2\). Thus the expression is always even.
Prove that a sum of three integer cubes cannot have residue \(4\) or \(5\) modulo \(9\).
A cube modulo \(9\) is \(0\), \(1\), or \(-1\).
Each cube modulo \(9\) is \(0,\pm1\). A sum of three such residues is among \(-3,-2,-1,0,1,2,3\), i.e. modulo \(9\) among \(6,7,8,0,1,2,3\). Residues \(4\) and \(5\) do not occur.
Prove that a number of the form \(8t+7\) cannot be represented as a sum of three integer squares.
Squares modulo \(8\) are \(0,1,4\). Check sums of three such residues.
A square modulo \(8\) is \(0,1\), or \(4\). A sum of three such residues can give \(0,1,2,3,4,5,6\), but not \(7\). Hence a sum of three squares cannot be congruent to \(7\) modulo \(8\). The number \(8t+7\) has residue \(7\). Contradiction.
Prove that \(x^2=3y^2+2\) has no integer solutions.
Consider the equation modulo \(3\).
The right side \(3y^2+2\equiv2\pmod3\). But a square modulo \(3\) is only \(0\) or \(1\). Thus the left side cannot have residue \(2\). Contradiction.
Prove: if \(3\mid x^2+y^2\), then \(3\mid x\) and \(3\mid y\).
Squares modulo \(3\) are \(0\) or \(1\).
If a number is not divisible by \(3\), its square has residue \(1\) modulo \(3\). If at least one of \(x,y\) is not divisible by \(3\), the sum of squares has residue \(1\) or \(2\), not \(0\), except when both squares are \(0\). Therefore both \(x\) and \(y\) are divisible by \(3\).
Find all integers \(n\) for which \(13\mid n^2+n+1\).
Check residues \(0,1,\ldots,12\), or use the symmetry between \(n\) and \(-1-n\).
Checking residues modulo \(13\) gives zeros only for \(n\equiv3\) and \(n\equiv9\). Indeed, \(3^2+3+1=13\), \(9^2+9+1=91=7\cdot13\). Other residues give nonzero values. The answer is \(n\equiv3\) or \(9\pmod{13}\).
Prove that \(n^2+n+1\) is not divisible by \(11\) for any integer \(n\).
Check all residues \(n\pmod{11}\).
For \(n=0,1,\ldots,10\), the values of \(n^2+n+1\) modulo \(11\) are \(1,3,7,2,10,9,10,2,7,3,1\). Zero does not occur, so divisibility by \(11\) is impossible.
Prove that \(x^4+y^4=16z+15\) has no integer solutions.
A fourth power modulo \(16\) is \(0\) or \(1\).
If \(x\) is even, then \(x^4\equiv0\pmod{16}\); if \(x\) is odd, then \(x^2\equiv1\) or \(9\pmod{16}\), and \(x^4\equiv1\pmod{16}\). Thus \(x^4+y^4\) can have residue \(0,1,2\), but not \(15\). The right side has residue \(15\). Contradiction.
Prove that the congruence \(x^3\equiv2\pmod7\) has no solutions.
Make the table of cubes modulo \(7\).
For residues \(0,1,2,3,4,5,6\), the cubes modulo \(7\) are \(0,1,1,6,1,6,6\). Only \(0,1,6\) are possible. Residue \(2\) does not occur, so there are no solutions.
Find the last two digits of \(3^{20}\).
Work modulo \(100\). Notice that \(3^4=81\).
\(3^{20}=(3^4)^5=81^5\). Modulo \(100\): \(81^2\equiv61\), \(81^4\equiv61^2\equiv21\), \(81^5\equiv21\cdot81\equiv1\). Therefore the last two digits are \(01\).
Prove that the only integer solution of \(x^2+y^2=3z^2\) is \(x=y=z=0\).
First prove that if \(x^2+y^2\) is divisible by \(3\), then \(3\mid x\) and \(3\mid y\).
The equation implies \(3\mid x^2+y^2\). By the table of squares modulo \(3\), we get \(3\mid x\) and \(3\mid y\). Let \(x=3x_1\), \(y=3y_1\). Then \(9x_1^2+9y_1^2=3z^2\), so \(z^2=3(x_1^2+y_1^2)\), and \(3\mid z\). Thus all of \(x,y,z\) are divisible by \(3\). If a nonzero solution existed, we could divide all three numbers by \(3\) indefinitely, impossible for nonzero integers. Hence no nonzero solutions exist.
Prove that \(x^2-5y^2=2\) has no integer solutions.
Consider the equation modulo \(5\).
Modulo \(5\), we get \(x^2\equiv2\pmod5\). But squares modulo \(5\) are only \(0,1,4\). Residue \(2\) is impossible. Therefore there are no solutions.
Prove: if \(7\mid x^2+y^2\), then \(7\mid x\) and \(7\mid y\).
Squares modulo \(7\) are \(0,1,2,4\).
The quadratic residues modulo \(7\) are \(0,1,2,4\). For the sum of two such residues to be \(0\), the only possibility is \(0+0\): the negatives of \(1,2,4\) are \(6,5,3\), which are not square residues. Thus \(x^2\equiv0\) and \(y^2\equiv0\pmod7\), so \(7\mid x\) and \(7\mid y\).
Prove that infinitely many positive integers cannot be represented as a sum of three integer squares.
Consider numbers of the form \(8t+7\).
From the problem on three squares modulo \(8\), a sum of three squares cannot have residue \(7\) modulo \(8\). Therefore no number of the form \(8t+7\) can be represented as \(x^2+y^2+z^2\). There are infinitely many such positive integers: \(7,15,23,31,\ldots\). Hence infinitely many required numbers exist.