Same remainder, same place
Divide any integer by 4 and the remainder is 0, 1, 2 or 3. Colour every integer by its remainder and a repeating pattern appears:
Numbers of the same colour are "the same" as far as division by 4 is concerned. Two numbers have the same colour exactly when their difference is a multiple of 4: \(13 - 5 = 8\), and \(9 - (-3) = 12\).
Definition
Fix a whole number \(n \ge 2\), the modulus. Integers \(a\) and \(b\) are congruent modulo \(n\), written
\[ a \equiv b \pmod n, \]if \(n\) divides \(a - b\). Equivalently, \(a\) and \(b\) leave the same remainder on division by \(n\).
You use this every day. Times of day are congruence modulo 12 (or 24). Days of the week are modulo 7: 100 days after a Friday is a Sunday, because \(100 = 14 \times 7 + 2\), so \(100 \equiv 2 \pmod 7\), and two days after Friday is Sunday. Angles are modulo 360 degrees.
The ring \(\mathbb{Z}/n\)
Now treat each colour as a single new number. Modulo \(n\) there are exactly \(n\) colours, named by the remainders \(0, 1, \dots, n-1\). The set of them is written \(\mathbb{Z}/n\) (also \(\mathbb{Z}/n\mathbb{Z}\) or \(\mathbb{Z}_n\)). To add or multiply two colours, pick any number of each colour, calculate as usual, and take the colour of the answer.
Example: calculating in \(\mathbb{Z}/7\)
\(5 + 4 = 9 \equiv 2\). \(5 \times 4 = 20 \equiv 6\). \(3 - 5 = -2 \equiv 5\). And \(6 \times 6 = 36 \equiv 1\), so in \(\mathbb{Z}/7\), \(6 \cdot 6 = 1\). That makes sense once you notice \(6 \equiv -1\), and \((-1)(-1) = 1\).
There's a subtle question here. If the answer depended on which number of each colour you picked, the whole idea would collapse. Luckily it doesn't:
Theorem: congruence respects arithmetic
If \(a \equiv a'\) and \(b \equiv b' \pmod n\), then \(a + b \equiv a' + b'\) and \(ab \equiv a'b' \pmod n\).
Show proof
Write \(a' = a + sn\) and \(b' = b + tn\) for integers \(s, t\). Then \(a' + b' = (a + b) + (s + t)n\), which differs from \(a + b\) by a multiple of \(n\). And
\[ a'b' = (a + sn)(b + tn) = ab + (at + bs + stn)\,n, \]which differs from \(ab\) by a multiple of \(n\). ∎
So addition and multiplication of colours are well defined, and every ring rule holds because it holds in \(\mathbb{Z}\). Therefore \(\mathbb{Z}/n\) is a commutative ring with \(n\) elements. In Unit 6 you'll see this as the first example of a far-reaching construction, the quotient ring: "the integers, with \(n\) declared equal to zero".
Calculating with huge numbers
Because you can replace any number by anything of the same colour at any stage, you can keep numbers small throughout a calculation. This makes impossible-looking questions easy.
Example: what is the remainder when \(2^{100}\) is divided by 7?
Notice \(2^3 = 8 \equiv 1 \pmod 7\). So \(2^{99} = (2^3)^{33} \equiv 1^{33} = 1\), and \(2^{100} = 2^{99} \cdot 2 \equiv 2\). The remainder is 2, and we never computed a 31-digit number.
Example: the last digit of \(3^{100}\)
The last digit is the remainder modulo 10. Since \(3^4 = 81 \equiv 1 \pmod{10}\), \(3^{100} = (3^4)^{25} \equiv 1\). The last digit is 1.
Example: why "casting out nines" works
Since \(10 \equiv 1 \pmod 9\), every power of 10 is also \(\equiv 1\). So \(4721 = 4 \cdot 10^3 + 7 \cdot 10^2 + 2 \cdot 10 + 1 \equiv 4 + 7 + 2 + 1 = 14 \equiv 5 \pmod 9\). A number has the same remainder modulo 9 as the sum of its digits. That's why a number is divisible by 9 (or 3) exactly when its digit sum is.
Try it. Since \(10 \equiv -1 \pmod{11}\), find a digit rule for divisibility by 11, and use it to test 918,082.
Show answer
Powers of 10 alternate \(1, -1, 1, -1, \dots\) modulo 11, so a number is congruent to the alternating sum of its digits, starting from the units digit. For 918,082: \(2 - 8 + 0 - 8 + 1 - 9 = -22 \equiv 0\). So 918,082 is divisible by 11 (it equals \(11 \times 83{,}462\)).
Two multiplication tables
Here are the multiplication tables of \(\mathbb{Z}/5\) and \(\mathbb{Z}/6\). Purple cells show where a product equals 1; pink cells show where two non-zero elements multiply to give 0.
\(\mathbb{Z}/5\)
| × | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
\(\mathbb{Z}/6\)
| × | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| 2 | 0 | 2 | 4 | 0 | 2 | 4 |
| 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 4 | 0 | 4 | 2 | 0 | 4 | 2 |
| 5 | 0 | 5 | 4 | 3 | 2 | 1 |
The two tables have completely different personalities:
- In \(\mathbb{Z}/5\), every non-zero row contains each of \(0, 1, 2, 3, 4\) exactly once, like a Sudoku row. So every non-zero element has an inverse: \(2 \cdot 3 = 1\), \(4 \cdot 4 = 1\). You can divide by anything except 0. \(\mathbb{Z}/5\) is a field.
- In \(\mathbb{Z}/6\), the rows for 2, 3 and 4 repeat values and contain 0s. These elements are zero divisors: \(2 \cdot 3 = 0\), \(3 \cdot 4 = 0\). Only 1 and 5 are units.
The difference: 5 is prime and 6 isn't. If \(n = ab\) with \(1 < a, b < n\), then \(a \cdot b = n \equiv 0\), so \(a\) and \(b\) are zero divisors. Unit 3 shows that \(\mathbb{Z}/n\) is a field exactly when \(n\) is prime.
Multiplication as jumping
Here's a way to see whether an element is a unit. The multiples of \(a\), namely \(0, a, 2a, 3a, \dots\), are the places you land if you start at 0 and keep jumping \(a\) steps around the clock.
Jumps of 5visits all 12: a unit
Jumps of 8only 0, 8, 4: \(8 \cdot 3 = 0\)
Jumps of 9only 0, 9, 6, 3: \(9 \cdot 4 = 0\)
If the jumps visit every position, they visit 1 at some point: some multiple \(ka \equiv 1\), so \(k\) is an inverse of \(a\). For \(a = 5\), the 5th jump lands on 1 (\(5 \times 5 = 25 \equiv 1\)).
If the jumps get trapped, they return to 0 early: \(8 \times 3 = 24 \equiv 0\). So 8 is a zero divisor. What decides it? 8 and 12 share the factor 4, and the jumps only ever visit multiples of 4. In general, jumping by \(a\) visits exactly the multiples of \(d = \gcd(a, n)\), the greatest common divisor.
Which elements are units?
Theorem
Let \(0 < a < n\). Then in \(\mathbb{Z}/n\):
- if \(\gcd(a, n) = 1\), then \(a\) is a unit;
- if \(\gcd(a, n) = d > 1\), then \(a\) is a zero divisor, since \(a \cdot \tfrac{n}{d} \equiv 0\).
So every non-zero element of \(\mathbb{Z}/n\) is either a unit or a zero divisor, never both and never neither.
Show proof
Zero divisors. If \(d = \gcd(a, n) > 1\), then \(n/d\) is an integer between 1 and \(n - 1\), so it's non-zero in \(\mathbb{Z}/n\). And \(a \cdot \frac{n}{d} = \frac{a}{d} \cdot n\), a multiple of \(n\), so it's \(0\) in \(\mathbb{Z}/n\).
Units. We use Bézout's identity: for any integers \(a, n\) there are integers \(x, y\) with \(ax + ny = \gcd(a, n)\). (The next section shows how to find them.) If \(\gcd(a, n) = 1\), then \(ax + ny = 1\), and reading this modulo \(n\) gives \(ax \equiv 1\). So \(x\) is an inverse of \(a\). ∎
The units of \(\mathbb{Z}/n\) form a group under multiplication, written \((\mathbb{Z}/n)^\times\). Its size is Euler's totient \(\varphi(n)\), the number of integers from 1 to \(n\) that share no factor with \(n\).
| \(n\) | Units of \(\mathbb{Z}/n\) | \(\varphi(n)\) |
|---|---|---|
| 5 | 1, 2, 3, 4 | 4 |
| 6 | 1, 5 | 2 |
| 8 | 1, 3, 5, 7 | 4 |
| 12 | 1, 5, 7, 11 | 4 |
| \(p\) prime | everything except 0 | \(p - 1\) |
Finding inverses with Euclid
Knowing an inverse exists isn't the same as finding it. For small \(n\) you can search, but for numbers with hundreds of digits (as in cryptography) you need a method. The answer is 2,300 years old.
Euclid's algorithm finds \(\gcd(a, n)\) by repeated division: replace the pair \((n, a)\) by \((a, r)\), where \(r\) is the remainder of \(n\) divided by \(a\), until the remainder is 0. Run it backwards and you get Bézout's \(x\) and \(y\). Let's find the inverse of 11 modulo 26:
| Forwards: divide | Backwards: rewrite 1 |
|---|---|
| \(26 = 2 \cdot 11 + 4\) | \(1 = 4 - 3\) |
| \(11 = 2 \cdot 4 + 3\) | \(\;\;= 4 - (11 - 2 \cdot 4) = 3 \cdot 4 - 11\) |
| \(4 = 1 \cdot 3 + 1\) | \(\;\;= 3\,(26 - 2 \cdot 11) - 11 = 3 \cdot 26 - 7 \cdot 11\) |
| \(3 = 3 \cdot 1 + 0\): gcd is 1 | So \(-7 \cdot 11 \equiv 1 \pmod{26}\) |
The inverse of 11 is \(-7 \equiv 19\). Check: \(11 \times 19 = 209 = 8 \times 26 + 1\). ✓ Euclid's algorithm is extremely fast: the number of steps grows only with the number of digits, so computers find inverses modulo 600-digit numbers in a blink.
Try it. Find the inverse of 7 modulo 40.
Show answer
\(40 = 5 \cdot 7 + 5\), \(7 = 1 \cdot 5 + 2\), \(5 = 2 \cdot 2 + 1\). Backwards: \(1 = 5 - 2 \cdot 2 = 5 - 2(7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3(40 - 5 \cdot 7) - 2 \cdot 7 = 3 \cdot 40 - 17 \cdot 7\). So the inverse is \(-17 \equiv \mathbf{23}\). Check: \(7 \times 23 = 161 = 4 \times 40 + 1\). ✓
Fermat's little theorem
Here are the powers of each non-zero element of \(\mathbb{Z}/7\). Purple marks every power equal to 1.
| a | a1 | a2 | a3 | a4 | a5 | a6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 4 | 1 | 2 | 4 | 1 |
| 3 | 3 | 2 | 6 | 4 | 5 | 1 |
| 4 | 4 | 2 | 1 | 4 | 2 | 1 |
| 5 | 5 | 4 | 6 | 2 | 3 | 1 |
| 6 | 6 | 1 | 6 | 1 | 6 | 1 |
The whole last column is 1: every non-zero element raised to the 6th power gives 1. Some elements reach 1 sooner (2 and 4 cycle with length 3, and 6 with length 2), but the cycle lengths always divide 6. Notice also that 3 and 5 run through all six non-zero values before repeating. Such elements are called generators or primitive roots, and they reappear in Unit 10.
Fermat's little theorem (1640)
If \(p\) is prime and \(a \not\equiv 0 \pmod p\), then \(a^{p-1} \equiv 1 \pmod p\).
Show proof
Multiplying by \(a\) sends the non-zero elements \(1, 2, \dots, p-1\) to \(a, 2a, \dots, (p-1)a\). These are all different (if \(ia \equiv ja\) then multiplying by \(a^{-1}\) gives \(i \equiv j\)) and none is 0. So they're the same \(p - 1\) numbers, just shuffled: it's the "every row is a Sudoku row" property of the \(\mathbb{Z}/5\) table. Multiply all of them together both ways:
\[ a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1), \quad\text{so}\quad a^{p-1}\,(p-1)! \equiv (p-1)!. \]Each factor of \((p-1)!\) is a unit, so we can cancel it, leaving \(a^{p-1} \equiv 1\). ∎
The same argument with the units of \(\mathbb{Z}/n\) in place of \(1, \dots, p-1\) proves the general version:
Going deeper: RSA, the arithmetic behind secure websites
RSA encryption (1977) runs entirely in \(\mathbb{Z}/n\). Here it is with tiny numbers:
- Pick two primes, \(p = 5\) and \(q = 11\). Publish \(n = pq = 55\), but keep \(p\) and \(q\) secret.
- The units of \(\mathbb{Z}/55\) number \(\varphi(55) = 4 \times 10 = 40\). Pick a public exponent \(e = 3\), which shares no factor with 40, and compute its inverse modulo 40 with Euclid: \(d = 27\), since \(3 \times 27 = 81 = 2 \times 40 + 1\).
- To send the message \(m = 2\), anyone can compute \(c = m^e = 2^3 = 8 \pmod{55}\).
- To decrypt, the owner computes \(c^d = 8^{27} \pmod{55}\), which comes out as \(2\). It works because \(m^{ed} = m^{1 + 2 \cdot 40} = m \cdot (m^{40})^2 \equiv m\) by Euler's theorem.
Finding \(d\) requires \(\varphi(n)\), which requires factoring \(n\). With primes hundreds of digits long, nobody knows how to factor \(n\) in any reasonable time, so the secret stays secret.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. In \(\mathbb{Z}/9\), compute \(7 + 5\), \(7 \times 5\) and \(-4\).
Show answer
\(12 \equiv 3\); \(35 = 27 + 8 \equiv 8\); \(-4 \equiv 5\).
2. List the units and the zero divisors of \(\mathbb{Z}/10\).
Show answer
Units (sharing no factor with 10): 1, 3, 7, 9. Zero divisors: 2, 4, 5, 6, 8 (for example \(2 \times 5 = 0\), \(4 \times 5 = 0\), \(6 \times 5 = 0\), \(8 \times 5 = 0\)). So \(\varphi(10) = 4\).
3. Solve \(3x \equiv 4 \pmod 7\).
Show answer
The inverse of 3 mod 7 is 5 (\(3 \times 5 = 15 \equiv 1\)). Multiply both sides by 5: \(x \equiv 20 \equiv \mathbf{6}\). Check: \(3 \times 6 = 18 \equiv 4\). ✓
4. Does \(4x \equiv 2 \pmod 6\) have a solution? Does \(4x \equiv 1 \pmod 6\)?
Show answer
Multiples of 4 mod 6 are \(0, 4, 2, 0, 4, 2\): only the multiples of \(\gcd(4, 6) = 2\). So \(4x \equiv 2\) has solutions (\(x = 2\) and \(x = 5\)), but \(4x \equiv 1\) has none. With a zero divisor, equations can have several solutions or none.
5. Find the remainder of \(5^{2026}\) when divided by 13.
Show answer
By Fermat, \(5^{12} \equiv 1 \pmod{13}\). \(2026 = 12 \times 168 + 10\), so \(5^{2026} \equiv 5^{10}\). Now \(5^2 = 25 \equiv -1\), so \(5^{10} = (5^2)^5 \equiv (-1)^5 = -1 \equiv \mathbf{12}\).
6. Show that a square number always leaves remainder 0 or 1 when divided by 4. Deduce that 4,000,003 is not a sum of two squares.
Show answer
Squares modulo 4: \(0^2 = 0\), \(1^2 = 1\), \(2^2 = 4 \equiv 0\), \(3^2 = 9 \equiv 1\). So a sum of two squares is \(\equiv 0, 1\) or \(2 \pmod 4\), never 3. And \(4{,}000{,}003 \equiv 3 \pmod 4\). Which primes are sums of two squares is the story of Unit 9.
Summary and glossary
- \(a \equiv b \pmod n\) means \(n\) divides \(a - b\): the same remainder, the same place on the clock.
- Congruence respects \(+\) and \(\times\), so the \(n\) remainder classes form a commutative ring \(\mathbb{Z}/n\).
- Reducing at every step makes calculations with enormous powers easy.
- A non-zero \(a\) is a unit in \(\mathbb{Z}/n\) if \(\gcd(a, n) = 1\), and a zero divisor otherwise. \(\mathbb{Z}/p\) is a field for prime \(p\).
- Euclid's algorithm run backwards finds inverses quickly.
- Fermat: \(a^{p-1} \equiv 1 \pmod p\). Euler: \(a^{\varphi(n)} \equiv 1 \pmod n\). These power RSA.
- Modulus
- The number \(n\) you work "modulo".
- Congruent
- \(a \equiv b \pmod n\): their difference is a multiple of \(n\).
- \(\mathbb{Z}/n\)
- The ring of remainders modulo \(n\).
- Well defined
- The answer doesn't depend on which representative you pick.
- \(\gcd(a, n)\)
- The greatest common divisor of \(a\) and \(n\).
- Bézout's identity
- \(ax + ny = \gcd(a, n)\) has integer solutions.
- \(\varphi(n)\)
- Euler's totient: the number of units in \(\mathbb{Z}/n\).
- Generator
- A unit whose powers run through all the units.