Chapter
Theory
Congruences replace infinitely many integers by a finite table of residues. To prove impossibility, it is often enough to find a modulus in which the two sides always belong to disjoint sets of residues.
The main skill in this module is not mechanical computation, but choosing the modulus: \(3,4,5,7,8,9,11,16\) often produce quick contradictions.
If the right side has the form \(4k+3\), \(8k+7\), or \(3k+2\), try square residue tables. If cubes appear, test modulo \(7\) or \(9\). If the problem asks about the last digit, look for a power cycle.
The right modulus is usually small and makes one side very restricted: for example, a square modulo \(8\) cannot be \(2,3,5,6,7\).
Examples
A congruence fixes the residue but lets us work without exact division.
Problem. Find the remainder of \(2026^2+2026\) upon division by \(5\).
\(2026\equiv1\pmod5\). Hence \(2026^2+2026\equiv1^2+1=2\pmod5\). The remainder is \(2\).
Comment. First replace the number by its residue, then compute.
Squares have very few possible residues.
Problem. Show that the square of an integer modulo \(8\) can only have residue \(0,1,4\).
Check residues \(0,1,2,\ldots,7\). Their squares modulo \(8\) are \(0,1,4,1,0,1,4,1\). Thus only \(0,1,4\) are possible.
Comment. This table will be used many times.
A sum of two squares cannot be \(3\) modulo \(4\).
Problem. Prove that \(x^2+y^2=4z+3\) has no integer solutions.
A square modulo \(4\) is \(0\) or \(1\). Therefore a sum of two squares modulo \(4\) can be \(0,1,2\), but not \(3\). The right side \(4z+3\equiv3\pmod4\). Contradiction.
Comment. The modulus \(4\) is suggested by the form of the right side.
Modulo \(8\) is stronger than ordinary parity.
Problem. Prove that \(x^2+y^2=8z+7\) has no integer solutions.
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 is \(7\) modulo \(8\). Contradiction.
Comment. Here modulo \(4\) would be weaker, while modulo \(8\) solves the problem.
Sometimes it is easiest to check all residues modulo a small number.
Problem. Find all residues \(n\pmod7\) for which \(7\mid n^2+n+1\).
Check \(n=0,1,2,3,4,5,6\). The values of \(n^2+n+1\) modulo \(7\) are \(1,3,0,6,0,3,1\). Thus \(n\equiv2\) and \(n\equiv4\pmod7\) work.
Comment. A seven-row table is acceptable when it gives the full answer.
Cubes modulo \(9\) have only three possible residues.
Problem. Show that the cube of an integer modulo \(9\) is \(0,1\), or \(8\).
Check residues \(0,\ldots,8\): the cubes are \(0,1,8,0,1,8,0,1,8\). Hence only \(0,1,8\), i.e. \(0,\pm1\), are possible.
Comment. This table is useful for sums of cubes.
The last digit is work modulo \(10\).
Problem. Find the last digit of \(7^{2026}\).
The last digits of powers of \(7\) cycle as \(7,9,3,1\). The cycle length is \(4\). Since \(2026\equiv2\pmod4\), we take the second digit in the cycle: \(9\).
Comment. There is no need to compute the large power.
Sometimes the modulus is suggested by a coefficient.
Problem. Prove that the equation \(x^2=3y^2+2\) has no integer solutions.
Consider the equation modulo \(3\). The right side satisfies \(3y^2+2\equiv2\pmod3\). But a square modulo \(3\) can only be \(0\) or \(1\). Contradiction.
Comment. Modulo \(3\) is chosen because the right side is almost a multiple of \(3\).
Problems
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.
Ladders