Back to the on-screen lesson ·
Which residues are invertible and which multiply something non-zero to zero, why nothing is both, and how Euclid's algorithm produces an inverse in a handful of steps.
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 is a unit or a zero divisor from a single highest common factor, find an inverse by Euclid's algorithm, count the units and the zero divisors of the integers modulo $n$, explain why the units form a group, prove that no element is both a unit and a zero divisor, and say why the clean split is special to finite commutative rings.
The last lesson placed rings on a ladder by asking whether they have zero divisors and whether every non-zero element is invertible. In the integers modulo $n$ both questions have the same one-line answer, and it is about highest common factors. So the ring can be taken apart element by element.
In a ring with $1$, a unit is an element with a multiplicative inverse. A zero divisor is a non-zero element $a$ for which some non-zero $b$ has $ab = 0$. The group of units $U(R)$ is the set of units under multiplication; for the integers modulo $n$ it is written $U(n)$ and has $\phi(n)$ elements.
Work in $\mathbb{Z}_n$. For a non-zero residue $a$, everything depends on $d = \gcd(a, n)$.
If $d = 1$, then $a$ is a unit. Bézout gives integers $x, y$ with $ax + ny = 1$, which modulo $n$ says $ax \equiv 1$. So $x$ is an inverse, and it is found in practice by running Euclid's algorithm backwards.
If $d > 1$, then $a$ is a zero divisor. Take $b = n/d$, which is non-zero because $d > 1$ and smaller than $n$. Then $ab = a(n/d) = (a/d)n \equiv 0$, and $a$ kills a non-zero element.
So in $\mathbb{Z}_n$ the non-zero elements split exactly in two, and the counts are $\phi(n)$ units and $n - \phi(n) - 1$ zero divisors.
Nothing is both. If $a$ is a unit and $ab = 0$, then $b = (a^{-1}a)b = a^{-1}(ab) = 0$. This holds in every ring with unity, not just this one, and it is why a field has no zero divisors.
The units form a group. Closed, since $(ab)^{-1} = b^{-1}a^{-1}$; associative; containing $1$; and inverses by definition. That group is $U(n)$, met in unit 1 — the same set, now seen as the invertible part of a ring rather than as a group that happened to be lying about.
The splitting is special to finite commutative rings. In the integers the only units are $\pm 1$, there are no zero divisors, and every other element is neither.
Another way: picture
Set $n$ pegs in a circle and step round by $a$ each time. If $a$ is coprime to $n$ you visit every peg, so some number of steps lands on $1$: that number is the inverse. If $a$ shares a factor $d$ with $n$ you only ever visit multiples of $d$, so you never reach $1$ — and you return to $0$ after $n/d$ steps, which exhibits $a$ as a zero divisor. One picture, both conclusions.
Another way: steps
For a residue $a$ modulo $n$: 1. Compute $d = \gcd(a, n)$. 2. If $d = 1$: a unit. Find the inverse by Euclid's algorithm, or by looking for a product one more than a multiple of $n$. 3. If $d > 1$: a zero divisor, and $n/d$ is a partner that it multiplies to zero. 4. Count: $\phi(n)$ units, and $n - \phi(n) - 1$ zero divisors.
Euclid's algorithm does not only find a highest common factor; run backwards, it writes that factor as a combination. For $a$ and $n$ coprime this produces $x$ with $ax + ny = 1$, and $x$ is the inverse of $a$ modulo $n$.
Take $a = 7$, $n = 24$. Euclid: $24 = 3 \times 7 + 3$, then $7 = 2 \times 3 + 1$. Back-substituting, $1 = 7 - 2 \times 3 = 7 - 2(24 - 3 \times 7) = 7 \times 7 - 2 \times 24$. So $7 \times 7 \equiv 1 \pmod{24}$, and $7$ is its own inverse.
The cost matters. Euclid's algorithm takes a number of steps proportional to the number of digits, so inverting modulo a three-hundred-digit number is quick. Factorising that number is not, as far as anyone knows, and the whole of RSA sits in the gap between those two facts: finding $d$ from $e$ and $\phi(n)$ is one run of Euclid, while finding $\phi(n)$ from $n$ appears to require the factorisation.
Two smaller observations are worth carrying. First, a unit's inverse is unique, by the group argument of unit 1 — so the inverse is legitimate language. Second, the product of two units is a unit and the product of two zero divisors need not be a zero divisor: modulo $12$, $4$ and $3$ are both zero divisors and $4 \times 3 = 0$, while $4$ and $4$ give $4$. The units are closed; the zero divisors are not a structure at all, merely what is left over.
Calling $0$ a zero divisor. By the definition used here a zero divisor is non-zero. Conventions differ, and the arithmetic does not, but the counts do.
Expecting every ring to split in two. In the integers almost every element is neither a unit nor a zero divisor. The clean split is a fact about finite commutative rings with unity.
Thinking a large residue cannot be a unit. $11$ is a unit modulo $12$; $2$ is not. Size is irrelevant, only the highest common factor matters.
Looking for an inverse by trial when the modulus is large. Euclid's algorithm finds it in a handful of steps; searching does not scale at all.
Assuming the zero divisors are closed under multiplication. They are not, and they do not form a subgroup, a subring or an ideal in general.
$\phi(15) = \phi(3)\phi(5) = 2 \times 4 = 8$, so there are eight units: $1, 2, 4, 7, 8, 11, 13, 14$.
Count the coprime residues.
Non-zero zero divisors: $15 - 8 - 1 = 6$, namely $3, 5, 6, 9, 10, 12$ — the multiples of $3$ or of $5$.
Everything else non-zero.
Check one: $\gcd(6, 15) = 3$, and $6 \times 5 = 30 \equiv 0$, with $5$ non-zero.
The partner is the modulus over the common factor.
Invert $5$ modulo $16$. Euclid: $16 = 3 \times 5 + 1$.
One step is enough here.
So $1 = 16 - 3 \times 5$, giving $-3 \times 5 \equiv 1 \pmod{16}$.
Back-substitute.
And $-3 \equiv 13$, so the inverse is $13$. Check: $5 \times 13 = 65 = 4 \times 16 + 1$.
Reduce into range and verify.
$\gcd(8, 20) = 4$, which is bigger than $1$, so $8$ is not a unit.
The one computation.
So it is a zero divisor, with partner $20/4 = 5$.
The modulus over the common factor.
Check: $8 \times 5 = 40 \equiv 0 \pmod{20}$, and neither factor is zero. Note $8 \times 15$ is also zero — the partner is not unique.
Take the integers modulo $8$. Count the units, the non-zero zero divisors, and the elements altogether.
| How many | |
|---|---|
| Units | |
| Non-zero zero divisors | |
| Elements altogether |
How many units does the ring of integers modulo $9$ have?
Answer:
In the integers modulo $9$, match each unit to its multiplicative inverse.
| $4$ | $5$ | $7$ | $8$ | $2$ | |
|---|---|---|---|---|---|
| $2$ | |||||
| $4$ | |||||
| $7$ | |||||
| $8$ |
Select every statement that is true.
This task has no paper form; do it on a device.
In the integers modulo $10$, is $6$ a unit or a zero divisor?
Build the proof that a unit is never a zero divisor.
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.
Take the integers modulo $9$. Count the units, the non-zero zero divisors, and the elements altogether.
| How many | |
|---|---|
| Units | |
| Non-zero zero divisors | |
| Elements altogether |
You can classify a residue as a unit or a zero divisor and find an inverse when there is one. Say in your own words why a unit can never be a zero divisor. Next: ideals, which are the subrings you are allowed to quotient by.
9. Your turn: modulo $20$, is $8$ a unit or a zero divisor, and what is its partner?, step 3