Back to the on-screen lesson ·
Arithmetic that remembers only the remainder: why reducing at any point is allowed, why division is not, and what an inverse is instead.
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 add, subtract, multiply and take powers modulo a number, reducing at every step so the numbers never grow, and test a congruence by asking whether the modulus divides the difference. You will also be able to say why cancelling is not allowed, find an inverse when one exists, decide from the greatest common divisor whether one exists at all, and recognise an ordinary question about last digits or days of the week as a modular one.
Lesson 14 showed that congruence modulo $m$ is an equivalence relation with $m$ classes, and owed a check: that arithmetic on classes is well defined. Lesson 25 gave Bezout's identity. This lesson pays the first debt and spends the second.
$a \equiv b \pmod m$ means $m \mid a - b$. A residue is a representative of a class, usually taken between $0$ and $m-1$. An inverse of $a$ modulo $m$ is an $x$ with $ax \equiv 1$. $\mathbb{Z}_m$ is the set of the $m$ classes with this arithmetic on it.
The definition. $a \equiv b \pmod m$ when $m$ divides $a - b$. Two integers are congruent exactly when they leave the same remainder, which is lesson 14's relation, and the classes are the $m$ remainders.
Addition and multiplication survive. If $a \equiv a'$ and $b \equiv b'$ then $a + b \equiv a' + b'$ and $ab \equiv a'b'$. The proof is two lines: $m \mid a - a'$ and $m \mid b - b'$, so $m$ divides the sum, and for the product write $ab - a'b' = a(b - b') + b'(a - a')$. That is the well-definedness check lesson 14 said a quotient always owes, and it is what lets you reduce at any point — before the arithmetic, after it, or in the middle.
Reducing as you go is not a convenience; it is what makes the arithmetic possible. $7^{100}$ has eighty-five digits and $7^{100} \bmod 11$ takes seven multiplications of numbers below $121$.
Division does not survive, and this is where modular arithmetic stops looking like ordinary arithmetic. $2 \times 3 \equiv 2 \times 6 \pmod 6$, and $3 \not\equiv 6$: you may not cancel the $2$. What replaces division is multiplying by an inverse, and $a$ has one modulo $m$ exactly when $\gcd(a, m) = 1$.
That condition is Bezout's identity read sideways. If $\gcd(a, m) = 1$ then $ax + my = 1$ for some integers, and reducing modulo $m$ gives $ax \equiv 1$ — so the Bezout coefficient of $a$ is the inverse. And if the gcd is $d > 1$ then every multiple of $a$ is a multiple of $d$ modulo $m$, so $1$ is out of reach and no inverse exists.
When $m$ is prime every non-zero residue is coprime to it, so every non-zero residue has an inverse and the arithmetic behaves like a number system. When $m$ is composite it does not, and that difference is the beginning of abstract algebra.
Another way: steps
To compute modulo $m$:
Another way: example
$3^{20} \bmod 7$: $3^2 = 9 \equiv 2$, so $3^4 \equiv 4$, $3^8 \equiv 16 \equiv 2$, $3^{16} \equiv 4$. Then $3^{20} = 3^{16} \cdot 3^4 \equiv 4 \cdot 4 = 16 \equiv 2$. Five multiplications, never a number above $16$.
| The question | The modulus |
|---|---|
| what is the last digit | $10$ |
| what day of the week | $7$ |
| what time, on a twelve-hour clock | $12$ |
| is this number even | $2$ |
| does $3$ divide the digit sum | $9$ |
Each of these is a question nobody phrases with a modulus, and each becomes routine once it is phrased with one. What is the last digit of $7^{100}$? is $7^{100} \bmod 10$; the last digits of the powers of $7$ cycle $7, 9, 3, 1$ with period four, and $100$ is a multiple of four, so the answer is $1$.
The divisibility test for $9$ is the same idea: $10 \equiv 1 \pmod 9$, so $10^k \equiv 1$ for every $k$, so a number is congruent to the sum of its digits. The rule everybody learns at school is one congruence, applied.
Recognising the modulus is the transferable skill. The arithmetic afterwards is mechanical.
Cancelling. $ab \equiv ac$ does not give $b \equiv c$ unless $a$ is coprime to the modulus. $2 \cdot 3 \equiv 2 \cdot 6 \pmod 6$ and $3 \not\equiv 6$.
Writing a fraction. There is no $1/2$ modulo $7$; there is the inverse of $2$, which is $4$.
Reducing an exponent by the modulus. $a^{m} \not\equiv a^{m \bmod m}$. Exponents are reduced by the order of $a$, which is a different number, and that is what the cycle length in a last-digit problem is.
Expecting a negative residue to be wrong. $-3 \equiv 4 \pmod 7$; both name the same class, and the range $0$ to $m-1$ is a convention for writing an answer down.
$17 \equiv 2 \pmod 5$ does not say the two numbers are nearly equal or that one is a rounded version of the other. It says they are in the same class — that $5$ divides their difference — and nothing about their sizes. $10^{6} \equiv 1 \pmod 3$ is exactly as true as $4 \equiv 1 \pmod 3$, and the enormous gap between the numbers is irrelevant, because the relation was never about how far apart they are.
$2^{10} \bmod 11$. Squaring: $2^2 = 4$, $2^4 = 16 \equiv 5$.
Reduce after every step.
$2^8 \equiv 5^2 = 25 \equiv 3$, and $2^{10} = 2^8 \cdot 2^2 \equiv 3 \cdot 4 = 12 \equiv 1$.
Square, square, square, then combine.
Four multiplications, never a number above $25$. Computing $2^{10} = 1024$ and dividing would also work here and does not scale, which is the reason to build the habit now.
The method that survives large numbers.
Modulo $7$, what is the inverse of $3$? Look for $x$ with $3x \equiv 1$: $3 \cdot 5 = 15 = 2 \cdot 7 + 1$, so $x = 5$.
Small modulus: search is enough.
Modulo $6$, what is the inverse of $3$? $\gcd(3, 6) = 3$, not $1$, so there is none — every multiple of $3$ is $0$ or $3$ modulo $6$, and $1$ is unreachable.
Check the gcd before searching.
So dividing by $3$ is available modulo $7$ and not modulo $6$. Whether a number system supports division depends on the modulus, and for a prime modulus every non-zero residue has an inverse.
Prime moduli behave; composite ones do not.
Work modulo $5$ and look for a cycle: $3^1 \equiv 3$, $3^2 \equiv 4$, $3^3 \equiv 2$, $3^4 \equiv 1$.
Find where the powers return to one.
Once a power is $1$ the cycle restarts, so the powers of $3$ repeat with period four.
The cycle length is what reduces the exponent.
$100$ is a multiple of $4$, so $3^{100} \equiv (3^4)^{25} \equiv 1^{25} = 1$. The remainder is $1$, and the exponent was reduced by the cycle length rather than by the modulus — those are different numbers, and confusing them is the standard error here.
Work modulo $6$, with $a = 5$ and $b = 2$. Give each answer as a residue between $0$ and $5$.
| Residue modulo $6$ | |
|---|---|
| $a + b$ | |
| $a - b$ | |
| $a \times b$ |
What is $7^{2}$ modulo $12$?
Answer:
Work modulo $13$. Find the residue $x$ with $5x \equiv 1$, and give the residue $5x$ reduces to when $x$ is that value.
$x = $x, and then $5x$ reduces to one.
Mark every congruence below that is true.
This task has no paper form; do it on a device.
What is the last digit of $2^{10}$?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Work modulo $11$, with $a = 8$ and $b = 6$. Give each answer as a residue between $0$ and $10$.
| Residue modulo $11$ | |
|---|---|
| $a + b$ | |
| $a - b$ | |
| $a \times b$ |
You can compute modulo a number, find an inverse and say when there is none. Say in your own words why reducing before or after an operation gives the same answer, and why a cancellation that looks obvious can be wrong. Next: sequences defined by a rule referring back to themselves.
10. Your turn: what is the remainder when $3^{100}$ is divided by $5$?, step 3