Back to the on-screen lesson ·
Sameness modulo a number, the classes it sorts the integers into, and the arithmetic that survives the sorting.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state what $a \equiv b \pmod n$ asserts and prove it is an equivalence relation compatible with addition and multiplication, reduce a sum, a product or a power modulo $n$ by reducing at every step, choose a negative representative when it shortens the work, and say exactly why cancellation fails and what replaces it.
The division algorithm sorts the integers by the remainder they leave on division by $n$: exactly $n$ heaps, because the remainder takes exactly the values $0, 1, \ldots, n-1$. Lesson 1's last item asked you to sort numbers into those heaps.
This lesson gives the heaps a name and — the part that matters — shows that you can add and multiply them. Pick any number from one heap and any from another, add, and the heap you land in does not depend on which two you picked. That is not obvious, and without it the heaps would be a classification rather than an arithmetic.
$a \equiv b \pmod n$ — read $a$ is congruent to $b$ modulo $n$ — means $n \mid (a - b)$. The number $n$ is the modulus.
The residue class of $a$ is $\bar{a} = \{a + kn : k \in \mathbb{Z}\}$, the whole heap. Any member of it is a residue; the one in $\{0, \ldots, n-1\}$ is the least residue, sometimes called the canonical representative.
$\mathbb{Z}_n$ (also written $\mathbb{Z}/n\mathbb{Z}$) is the set of the $n$ classes, with the addition and multiplication below. A complete residue system is any set of $n$ integers, one from each class — the least residues are the usual choice, but $\{-1, 0, 1\}$ is a perfectly good one modulo $3$.
Definition. $a \equiv b \pmod n$ when $n \mid (a - b)$; equivalently, when $a$ and $b$ leave the same remainder on division by $n$.
It is an equivalence relation. Reflexive, since $n \mid 0$. Symmetric, since $n \mid (a-b)$ gives $n \mid (b-a)$. Transitive, since $n \mid (a-b)$ and $n \mid (b-c)$ give $n \mid (a-c)$ by adding. So it partitions $\mathbb{Z}$ into the $n$ classes.
It is compatible with $+$ and $\times$. If $a \equiv b$ and $c \equiv d$ modulo $n$, then $$a + c \equiv b + d \quad\text{and}\quad ac \equiv bd \pmod n.$$ The first is immediate. For the second, write $ac - bd = c(a - b) + b(c - d)$, and $n$ divides both terms.
That compatibility is the whole content. It means the classes themselves can be added and multiplied, so $\mathbb{Z}_n$ is a commutative ring with identity, and reduction may be done at any point in a calculation without changing the answer. Every practical use of modular arithmetic — digital signatures, hash tables, check digits, calendars — is that permission being exercised.
Consequences that get used constantly. $a \equiv b$ implies $a^k \equiv b^k$ for every $k \ge 1$, by repeated multiplication. A polynomial with integer coefficients respects congruence: $a \equiv b$ implies $f(a) \equiv f(b)$.
What does not carry over: cancellation. $ac \equiv bc \pmod n$ does not give $a \equiv b$. Modulo $6$, $2 \cdot 4 \equiv 2 \cdot 1$ while $4 \not\equiv 1$. The correct statement is $$ac \equiv bc \pmod n \;\Longrightarrow\; a \equiv b \pmod{n/\gcd(c, n)},$$ so cancellation is free exactly when $\gcd(c, n) = 1$. That gap is what the next lesson exists to close.
Another way: steps
Another way: example
$37 \cdot 44 \bmod 9$: reduce first, $37 \equiv 1$ and $44 \equiv 8$, so the product is $\equiv 8$. Checking the long way, $37 \cdot 44 = 1628 = 9 \cdot 180 + 8$. Now $7^{100} \bmod 10$: $7^2 = 49 \equiv 9 \equiv -1$, so $7^{100} = (7^2)^{50} \equiv (-1)^{50} = 1$. A hundred multiplications became two.
The least residue is the conventional representative, and it is often the wrong one to compute with. Any member of the class will do, and choosing a small negative one can shorten a calculation enormously.
Modulo $11$, the class of $10$ is also the class of $-1$. So $10^{50} \equiv (-1)^{50} = 1$, which is a one-line argument, while working with $10$ directly is not. Modulo $7$, $6 \equiv -1$ and $5 \equiv -2$, and squaring $-2$ is easier than squaring $5$ — even though they land in the same place.
The general principle: when a residue is more than half the modulus, replace it by itself minus the modulus. The result is a representative of absolute value at most $n/2$, and the arithmetic that follows is smaller. This is called the least absolute residue, and every hand computation in the rest of this course uses it.
It matters for a second reason. A statement like $(p-1)! \equiv -1 \pmod p$ — Wilson's theorem, in unit 3 — is far easier to recognise as a pattern in the form $-1$ than in the form $p - 1$, which changes with $p$. Several of the theorems ahead are stated with $-1$ on the right for exactly that reason, and reading $p-1$ and $-1$ as the same thing is a habit worth forming now.
A caution in the other direction: a final answer asked for as a residue is normally wanted as the least residue, between $0$ and $n-1$. Negative representatives are a working convenience, not a form to report in.
Cancelling a common factor. $2x \equiv 2y \pmod 6$ does not give $x \equiv y$. Check $\gcd$ of the factor with the modulus first; if it is not $1$, the modulus shrinks.
Dividing. There is no division in $\mathbb{Z}_n$. $a/b$ means $a \cdot b^{-1}$, and $b^{-1}$ exists only when $\gcd(b, n) = 1$. Writing a fraction in a congruence is almost always a mistake in disguise.
Reducing an exponent modulo $n$. $2^{13} \bmod 5$ is not $2^{3} \bmod 5$. Exponents live in a different place, and reducing them correctly needs Fermat's or Euler's theorem — and a modulus of $p-1$ or $\varphi(n)$, not $n$.
Assuming $a^2 \equiv 1$ forces $a \equiv \pm 1$. True for prime moduli, false in general: modulo $8$, all of $1, 3, 5, 7$ square to $1$.
Treating a congruence as an equation between numbers. $a \equiv b \pmod n$ is a statement about classes. Squaring both sides is fine; taking square roots of both sides is not, and neither is taking logarithms or anything else that is not a polynomial with integer coefficients.
What is the last digit of $3^{2024}$? The last digit is the residue modulo $10$.
Name the modulus before starting.
The powers of $3$ modulo $10$ run $3, 9, 7, 1, 3, 9, 7, 1, \ldots$ — a cycle of length $4$, because $3^4 = 81 \equiv 1$.
Once a power hits $1$, everything repeats.
$2024 = 4 \cdot 506$, so $3^{2024} = (3^4)^{506} \equiv 1^{506} = 1$, and the last digit is $1$.
The exponent was reduced modulo $4$, not modulo $10$.
Can $x^2 \equiv 3 \pmod 4$ hold? Rather than search, look at what squares can be modulo $4$.
Finitely many classes means the question can be settled exhaustively.
Every integer is $0, 1, 2$ or $3$ modulo $4$, and squaring gives $0, 1, 0, 1$. So a square is always $0$ or $1$ modulo $4$.
Four cases, and congruence lets four cases cover every integer.
$3$ is neither, so there is no solution — and no integer of the form $4k + 3$ is a perfect square. That argument, applied to sums of two squares, is the whole of a theorem in unit 5.
An impossibility proof, from a table with four rows.
Work modulo $2$ and modulo $3$ separately; $6$ divides a number exactly when both do.
Split the modulus into coprime parts.
Modulo $2$: $n$ is $0$ or $1$, and $n^3 - n$ is $0$ in both cases. Modulo $3$: $n$ is $0$, $1$ or $2$, and $n^3 - n$ is $0$, $0$ and $6 \equiv 0$.
Five cases in total, and they cover every integer.
So $2 \mid (n^3 - n)$ and $3 \mid (n^3 - n)$, and since $2$ and $3$ are coprime, $6$ does too.
Working modulo $12$, give the least residue of each sum.
| Least residue | |
|---|---|
| $6 + 10$ | |
| $6 + 5$ | |
| $10 + 5$ |
What is the remainder when $39 + 77$ is divided by $12$?
Answer:
Mark the least residue of $91$ modulo $11$. The line runs from $0$ to $11$.
0 |——————————| 11
Mark the position with a cross, then write the value:
What is the remainder when $16 \times 31$ is divided by $7$?
Answer:
Working modulo $10$, match each number to the least residue of its class.
| $3$ | $4$ | $1$ | |
|---|---|---|---|
| $33$ | |||
| $34$ | |||
| $91$ |
The days of a week are numbered $0$ to $6$. Today is day $2$. What day number will it be in $36$ days?
day number a
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Working modulo $11$, give the least residue of each sum.
| Least residue | |
|---|---|
| $5 + 10$ | |
| $5 + 3$ | |
| $10 + 3$ |
You can compute with residues rather than with the numbers themselves, and you know which operations survive the reduction. Say in your own words why cancelling a common factor is not allowed, and what has to be true of that factor before it is. Next: the factors you are allowed to cancel.
9. Your turn: show that $n^3 - n$ is divisible by $6$ for every integer $n$, step 3