Back to the on-screen lesson ·
Which residues can be cancelled, why the greatest common divisor decides it, and the algorithm that produces the inverse.
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 decide whether a residue has an inverse modulo a given number, compute that inverse with the extended Euclidean algorithm and check it, prove that an inverse is unique when it exists, and state the correct cancellation rule for a factor that is not coprime to the modulus.
Congruences add, multiply and raise to powers. They do not cancel: $2 \cdot 4 \equiv 2 \cdot 1 \pmod 6$ while $4 \not\equiv 1$.
In ordinary arithmetic, cancelling $a$ from $ab = ac$ is multiplying both sides by $1/a$. So the question when can I cancel modulo $n$ is really which residues have a reciprocal modulo $n$. And a reciprocal for $a$ is a solution of $ax \equiv 1$, which is a solution of $ax + ny = 1$ — which is a Bézout identity. Lesson 3 already answered this; the answer just has not been recognised yet.
A residue $b$ is an inverse of $a$ modulo $n$ when $ab \equiv 1 \pmod n$. It is written $a^{-1}$, which is legitimate only because it is unique when it exists.
A residue with an inverse is a unit modulo $n$. The units form a group under multiplication, written $(\mathbb{Z}_n)^\times$ or $U(n)$.
A non-zero residue $a$ with $ab \equiv 0$ for some non-zero $b$ is a zero divisor. Modulo $6$, $2$ and $3$ are zero divisors, since $2 \cdot 3 \equiv 0$. Every non-zero residue modulo $n$ is one or the other: a unit or a zero divisor, never both and never neither.
When $n = p$ is prime every non-zero residue is a unit, and $\mathbb{Z}_p$ is then a field — a system in which every non-zero element can be divided by.
Theorem. $a$ has an inverse modulo $n$ if and only if $\gcd(a, n) = 1$, and the inverse is then unique modulo $n$.
If. When $\gcd(a, n) = 1$, Bézout gives $ax + ny = 1$, so $ax \equiv 1 \pmod n$ and $x$ is an inverse.
Only if. If $ab \equiv 1$ then $ab - 1 = kn$, so $ab - kn = 1$, and any common divisor of $a$ and $n$ divides $1$.
Uniqueness. If $ab \equiv 1$ and $ac \equiv 1$ then $b \equiv (ac)b = (ab)c \equiv c$.
Computing one. Run the extended Euclidean algorithm on $a$ and $n$; the coefficient of $a$, reduced into range, is the inverse. This is fast — a few thousand divisions for thousand-digit numbers — and there is no elementary alternative.
What it fixes. Cancellation becomes legitimate exactly for units: if $\gcd(c, n) = 1$ and $ac \equiv bc \pmod n$, multiply by $c^{-1}$ to get $a \equiv b$. The general statement without that hypothesis is $$ac \equiv bc \pmod n \;\Longrightarrow\; a \equiv b \pmod{n/\gcd(c, n)},$$ so a non-unit does not forbid cancellation, it shrinks the modulus.
The structure this gives $\mathbb{Z}_n$. The units are the residues coprime to $n$; there are $\varphi(n)$ of them, and they are closed under multiplication, so they form a group. The rest, apart from $0$, are zero divisors. When $n$ is prime there are no zero divisors at all, every non-zero residue is a unit, and $\mathbb{Z}_p$ is a field — which is why so much of the rest of this course is stated for prime moduli.
Another way: steps
Another way: example
$7^{-1}$ modulo $26$. Euclid: $26 = 3 \cdot 7 + 5$, $7 = 1 \cdot 5 + 2$, $5 = 2 \cdot 2 + 1$. Back: $1 = 5 - 2 \cdot 2 = 5 - 2(7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3(26 - 3 \cdot 7) - 2 \cdot 7 = 3 \cdot 26 - 11 \cdot 7$. So $7^{-1} \equiv -11 \equiv 15$, and $7 \cdot 15 = 105 = 4 \cdot 26 + 1$.
Writing out the units of a small modulus is worth doing once, because several later theorems are visible in the table before they are proved.
Modulo $8$ the units are $\{1, 3, 5, 7\}$, and each is its own inverse: $3^2 = 9 \equiv 1$, $5^2 = 25 \equiv 1$, $7^2 = 49 \equiv 1$. Four units, all of order at most $2$.
Modulo $7$ the units are $\{1, 2, 3, 4, 5, 6\}$ — every non-zero residue, because $7$ is prime — and the inverses pair up as $2 \leftrightarrow 4$, $3 \leftrightarrow 5$, with $1$ and $6$ their own. Six units, and the powers of $3$ run $3, 2, 6, 4, 5, 1$, reaching every one of them.
Three things to take from that comparison. First, the number of units is $\varphi(n)$, which is the subject of lesson 12. Second, most units are not their own inverse, so the units pair off with a small number of exceptions — and the exceptions are the solutions of $x^2 \equiv 1$, which for a prime modulus are exactly $\pm 1$. That pairing, with those exceptions, is the proof of Wilson's theorem in lesson 14. Third, sometimes a single unit generates all of them by taking powers, as $3$ does modulo $7$ and nothing does modulo $8$. Which moduli have such a generator is the subject of lesson 16.
The practical use is more immediate. Solving $ax \equiv b \pmod n$ when $a$ is a unit is a single multiplication: $x \equiv a^{-1}b$. That is the next lesson's easy case, and the whole of the next lesson is what to do when $a$ is not a unit.
It is not a fraction. $3^{-1} \pmod 7$ is $5$, a residue, not $1/3$. Writing fractions inside congruences invites steps that have no meaning, and the first one that does damage is usually a denominator sharing a factor with the modulus.
It does not always exist. $2$ has no inverse modulo $6$. Checking the gcd first is not a formality; it is the theorem.
A residue can be its own inverse. $1$ and $n-1$ always are, and for composite $n$ there are often others: modulo $8$, every unit is. Nothing is wrong when this happens.
The coefficient of the modulus is not part of the answer. The extended algorithm produces two numbers; only the one attached to the residue is the inverse. The other exists to make the identity true and is then discarded.
A negative coefficient is not an error. The algorithm usually produces one. Add the modulus until the answer is in range, and check by multiplying — a sign slip is the commonest mistake in the back-substitution, and the check catches it immediately.
$6x \equiv 6 \cdot 4 \pmod{10}$. Can $6$ be cancelled? $\gcd(6, 10) = 2$, so no — not as it stands.
Check the gcd before touching the congruence.
The correct rule shrinks the modulus: $x \equiv 4 \pmod{10/2}$, that is $x \equiv 4 \pmod 5$. So $x$ is $4$ or $9$ modulo $10$, and both check out.
The factor was not cancelled for free; it cost half the modulus.
By contrast $7x \equiv 7 \cdot 4 \pmod{10}$ cancels outright, since $\gcd(7, 10) = 1$: multiply by $7^{-1} \equiv 3$ to get $x \equiv 4 \pmod{10}$, one solution.
A unit cancels with no cost at all.
Solve $5x \equiv 3 \pmod{11}$. First, $\gcd(5, 11) = 1$, so $5$ is a unit and there will be exactly one solution.
Existence and count, before any computing.
$5 \cdot 9 = 45 = 4 \cdot 11 + 1$, so $5^{-1} \equiv 9$. (Found by inspection here; by the extended algorithm when the numbers are larger.)
A small modulus rewards a moment's looking.
Multiply both sides: $x \equiv 9 \cdot 3 = 27 \equiv 5 \pmod{11}$. Check: $5 \cdot 5 = 25 = 2 \cdot 11 + 3$.
Multiplying by the inverse is the whole method.
Let $a$ be a residue with $1 \le a \le p - 1$, and consider $\gcd(a, p)$.
The theorem reduces the question to a gcd.
The only positive divisors of $p$ are $1$ and $p$, and $p \nmid a$ because $0 < a < p$. So the gcd is $1$.
Primality is used exactly once, and here.
By the theorem $a$ has an inverse. So $\mathbb{Z}_p$ has no zero divisors and is a field.
Put the steps of finding the inverse of $2$ modulo $7$ into the order you carry them out.
Number the steps in order (write the number in the box):
What is the inverse of $7$ modulo $25$? Give the least residue.
Answer:
Does $19$ have an inverse modulo $23$?
Give the inverse of $11$ modulo $21$, and the product of $11$ with that inverse.
inverse a, product c
Working modulo $21$, give the inverse of each residue as a least residue.
| Inverse | |
|---|---|
| $2$ | |
| $4$ | |
| $5$ |
Build the proof that a residue has at most one inverse modulo $14$.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Put the steps of finding the inverse of $12$ modulo $19$ into the order you carry them out.
Number the steps in order (write the number in the box):
You can decide whether a residue is invertible, produce the inverse, and use it to cancel legitimately. Say in your own words what happens to the modulus when you cancel a factor that is not coprime to it. Next: the equations this makes solvable, and the ones it does not.
9. Your turn: show that every non-zero residue modulo a prime $p$ has an inverse, step 3