Modular Rings and Units

The Ring of Integers Modulo n

Recall the number system

$${\mathbb{Z}}_n=\{0,1,2,\dots ,n-1\},$$

which has the same addition and multiplication as $\mathbb{Z}$, except that every result is always reduced to its smallest non-negative remainder modulo $n$. For instance, in ${\mathbb{Z}}_4$ we have $3+2=1$, since $5$ leaves a remainder of $1$ when divided by $4$.

Each element $a\in {\mathbb{Z}}_n$ is really a representative of a residue class; the set of all integers leaving the same remainder as $a$ when divided by $n$,

$$[a{]}_n=\{a+kn:k\in \mathbb{Z}\}.$$

In ${\mathbb{Z}}_4$ for example, the element $1$ stands for the class $\{\dots ,-7,-3,1,5,9,\dots \}$. Basically, ${\mathbb{Z}}_n$ chops the integers up into $n$ classes and does arithmetic on the classes themselves; we just use the smallest non-negative member of each class as its name.

So ${\mathbb{Z}}_n$ is our first example of a finite ring. Recall that a commutative unital ring is a set closed under two operations $+$ and $\times$, where both operations are associative and commutative, there is an additive identity $0$ and a multiplicative identity $1$, every element has an additive inverse, and multiplication distributes over addition.

Example. Show that ${\mathbb{Z}}_4$ is a ring.
We can draw up the full addition and multiplication tables for ${\mathbb{Z}}_4$;

From the tables we can read off most of the ring laws directly:

• Every entry in both tables lies in $\{0,1,2,3\}$, so ${\mathbb{Z}}_4$ is closed under both operations.
• The $0$ row of the addition table and the $1$ row of the multiplication table copy the headers, so $0$ and $1$ are the additive and multiplicative identities.
• The element $0$ appears in every row of the addition table, so every element has an additive inverse; $-0=0$, $-1=3$, $-2=2$ and $-3=1$.
• Both tables are symmetric about the main diagonal, so both operations are commutative.

Associativity and distributivity hold because they already hold in $\mathbb{Z}$, and reducing modulo $4$ at each step does not change which residue class an answer lands in. Therefore, ${\mathbb{Z}}_4$ satisfies all of the ring axioms and is a ring. The same argument works for any $n$, which is exactly the Fact above.

A First Look at Modular Fields

Recall that a field is a commutative ring in which every nonzero element has a multiplicative inverse; you can divide by anything except $0$.

Notice that ${\mathbb{Z}}_4$ cannot be a field, since the nonzero element $2$ does not have a multiplicative inverse. This is clear from the multiplication table above; $1$ does not appear anywhere in $2$'s row, so no element multiplies with $2$ to give $1$.

Alternatively, we can argue it directly: if there were some $a\in {\mathbb{Z}}_4$ with $2a=1$ in ${\mathbb{Z}}_4$, then we would need $4\mid (2a-1)$; but $2a-1$ is odd for every integer $a$, so $4$ can never divide it.

On the other hand, consider the multiplication table for ${\mathbb{Z}}_3$;

Here every nonzero element does have a multiplicative inverse ($1^{-1}=1$ and $2^{-1}=2$, since $2\times 2=4=1$ in ${\mathbb{Z}}_3$), so ${\mathbb{Z}}_3$ is a field.

A natural question to ask is: for which $n$ is ${\mathbb{Z}}_n$ a field? To answer this, we first need some language for the elements that do have inverses.

Units and Unit Groups

Basically, the units are the elements you are allowed to divide by. In ${\mathbb{Z}}_4$ we just saw that $2$ is not a unit while $3$ is (since $3\times 3=9=1$ in ${\mathbb{Z}}_4$); a field is then simply a commutative ring where every nonzero element is a unit.

Example. Find the following unit groups.

• ${\mathbb{Q}}^{\ast }=\mathbb{Q}\setminus \{0\}$; every nonzero fraction $\frac{p}{q}$ has the inverse $\frac{q}{p}$, but nothing multiplies with $0$ to give $1$.
• ${\mathbb{N}}^{\ast }=\{1\}$; for any $n\ge 2$ we would need $nb=1$ with $b\in \mathbb{N}$, which is impossible since $nb$ is either $0$ or at least $n$.
• ${\mathbb{Z}}^{\ast }=\{-1,1\}$, since $1\times 1=1$ and $(-1)\times (-1)=1$, but no other integer has an integer inverse.
• ${\mathbb{Z}}_3^{\ast }=\{1,2\}$, since $1\times 1=1$ and $2\times 2=4=1$ in ${\mathbb{Z}}_3$.
• ${\mathbb{Z}}_4^{\ast }=\{1,3\}$, since $1\times 1=1$ and $3\times 3=9=1$ in ${\mathbb{Z}}_4$, while $0$ and $2$ have no inverse.

Notice how the unit group depends heavily on the ring; $\frac{1}{2}$ rescues $2$ in $\mathbb{Q}$, but in $\mathbb{Z}$ or ${\mathbb{Z}}_4$ there is no such element available.

Properties of Units

This is why we can safely write $a^{-1}$ for the inverse of $a$; there is never more than one candidate.

So the units are closed under multiplication. This is exactly why $R^{\ast }$ is called the unit group: a group is a set with one operation satisfying the closure, associativity, identity and inverse laws, and $R^{\ast }$ under multiplication has all four. Closure is the Fact we just proved; associativity is inherited from $R$; the identity is $1$ (which is a unit since $1\times 1=1$); and if $a$ is a unit then so is $a^{-1}$, because its inverse is just $a$ again. The remaining details are inherited straight from the ring so I'm not gonna belabour them.

Example. In ${\mathbb{Z}}_{10}$, both $3$ and $7$ are units. Their product $3\times 7=21=1$ in ${\mathbb{Z}}_{10}$, which is certainly a unit; and indeed $(3\times 7{)}^{-1}=1^{-1}=1=7^{-1}\times 3^{-1}=3\times 7$ reduced mod $10$. Closure holds exactly as promised.

Zero Divisors

So units are the "good" elements. The next Fact tells us that, in a finite ring, the non-units are bad in a very specific way.

Basically, a zero divisor is a nonzero element that manages to multiply with another nonzero element and still produce $0$; something that never happens in $\mathbb{Z}$, $\mathbb{Q}$ or $\mathbb{R}$. Combining the Fact and the Definition, we get a clean three-way split:

$$\boxed{\text{In a finite ring, every element is either }0,\text{ a unit, or a zero divisor.}}$$

It is important to remember that $0$ itself is neither a unit nor a zero divisor; it sits in a category of its own.

Example. Find all zero divisors of ${\mathbb{Z}}_{10}$.
We check each nonzero non-unit for a nonzero partner that kills it;

$$\begin{array}{rl}2\times 5& =10=0,\\ 4\times 5& =20=0,\\ 5\times 2& =10=0,\\ 6\times 5& =30=0,\\ 8\times 5& =40=0.\end{array}$$

Therefore, the zero divisors of ${\mathbb{Z}}_{10}$ are $\{2,4,5,6,8\}$; precisely the nonzero elements sharing a common factor with $10$. The remaining nonzero elements $\{1,3,7,9\}$ will turn out to be exactly the units.

You cannot cancel a zero divisor. In ${\mathbb{Z}}_{10}$ we have $2\times 1=2$ and $2\times 6=12=2$, so $2x=2y$ does not imply $x=y$; cancelling is really multiplying both sides by an inverse, and zero divisors have none. Cancellation in ${\mathbb{Z}}_n$ is only valid when the element being cancelled is a unit.

Units in Z_n

We now characterise exactly which elements of ${\mathbb{Z}}_n$ are units.

$$\boxed{a\in {\mathbb{Z}}_n^{\ast }⟺\gcd (a,n)=1.}$$

Basically, being a unit mod $n$ is the same as being coprime with $n$. This makes sense: any common factor $d>1$ shared between $a$ and $n$ can never be multiplied away, because every multiple of $a$ still carries that factor $d$ mod $n$. In fact if $d=\gcd (a,n)>1$, then

$$a\times \frac{n}{d}=\frac{a}{d}\times n=0\text{ in }{\mathbb{Z}}_n,$$

where $\frac{n}{d}$ is nonzero in ${\mathbb{Z}}_n$; so every nonzero non-unit of ${\mathbb{Z}}_n$ is a zero divisor, confirming the three-way split from before.

Example. Find ${\mathbb{Z}}_{10}^{\ast }$ and the inverse of each of its elements.
By the corollary, ${\mathbb{Z}}_{10}^{\ast }=\{1,3,7,9\}$; the four numbers less than $10$ coprime with $10$. We can confirm each is a unit by finding its inverse directly;

$$\begin{array}{rl}1\times 1& =1,\\ 3\times 7& =21=2\times 10+1=1\text{ in }{\mathbb{Z}}_{10},\\ 9\times 9& =81=8\times 10+1=1\text{ in }{\mathbb{Z}}_{10}.\end{array}$$

This gives us the full table for ${\mathbb{Z}}_{10}$;

Notice how inverses come in pairs; once you know $3^{-1}=7$, you get $7^{-1}=3$ for free.

Example. Classify every element of ${\mathbb{Z}}_{12}$ as $0$, a unit, or a zero divisor.
Using the units criterion, we compute $\gcd (a,12)$ for each element;

Therefore, ${\mathbb{Z}}_{12}^{\ast }=\{1,5,7,11\}$ and the zero divisors are $\{2,3,4,6,8,9,10\}$; every element is accounted for by the three-way split. Notice the curious bonus: every unit in ${\mathbb{Z}}_{12}$ is its own inverse, since $5^2=25=1$, $7^2=49=1$ and $11^2=121=1$ in ${\mathbb{Z}}_{12}$.

When Z_n Is a Field

We can now answer the question from the start: since a field needs every nonzero element to be a unit, we need every one of $1,2,\dots ,n-1$ to be coprime with $n$.

$$\boxed{{\mathbb{Z}}_n\text{ is a field}⟺n\text{ is prime}.}$$

This correlates with what we saw earlier; ${\mathbb{Z}}_3$ is a field while ${\mathbb{Z}}_4$ is not, matching the fact that $3$ is prime while $4$ is not.

Example. ${\mathbb{Z}}_7$ must be a field since $7$ is prime, so every nonzero element of ${\mathbb{Z}}_7$ has a multiplicative inverse. We can check this by pairing everything up;

$$\begin{array}{rl}1\times 1& =1,\\ 2\times 4& =8=7+1=1\text{ in }{\mathbb{Z}}_7,\\ 3\times 5& =15=2\times 7+1=1\text{ in }{\mathbb{Z}}_7,\\ 6\times 6& =36=5\times 7+1=1\text{ in }{\mathbb{Z}}_7.\end{array}$$

Every nonzero element appears in the bottom row, so ${\mathbb{Z}}_7$ is indeed a field.

Example. How many solutions does $x^2=1$ have in ${\mathbb{Z}}_8$?
In a field, $x^2=1$ factorises as $(x-1)(x+1)=0$, and since fields have no zero divisors one of the factors must be $0$; so there are at most the two solutions $x=\pm 1$. But $8$ is not prime, so ${\mathbb{Z}}_8$ is not a field, and we should check every element rather than trust the factorisation;

$$\begin{array}{rl}{1}^2& =1,\\ 3^2& =9=8+1=1,\\ 5^2& =25=3\times 8+1=1,\\ 7^2& =49=6\times 8+1=1.\end{array}$$

Therefore, $x^2=1$ has four solutions in ${\mathbb{Z}}_8$: $x\in \{1,3,5,7\}$. The factorisation logic breaks precisely because of zero divisors; taking $x=3$ gives $(x-1)(x+1)=2\times 4=8=0$ with neither factor being zero. In ${\mathbb{Z}}_n$ for composite $n$, a polynomial of degree $d$ can have more than $d$ roots, so always check all candidates rather than assuming field behaviour.

Finding Inverses

Multiplication tables are fine for small $n$, but useless for something like ${\mathbb{Z}}_{283}$. To find the multiplicative inverse (often just called the inverse) of an element $a$ in ${\mathbb{Z}}_n$, we follow these steps:

• Find $\gcd (a,n)$. If it is not $1$, there is no inverse and we stop.
• Find integers $x$ and $y$ such that $1=ax+ny$; either via the extended Euclidean algorithm, or just by checking small multiples of $n$ for a number that is $1$ away from a multiple of $a$.
• The inverse of $a$ in ${\mathbb{Z}}_n$ is the value of its coefficient $x$, reduced into ${\mathbb{Z}}_n$.

This works because reducing $1=ax+ny$ modulo $n$ leaves $ax=1$ in ${\mathbb{Z}}_n$; the $ny$ term vanishes.

Example. Find the multiplicative inverse of $6$ in ${\mathbb{Z}}_{21}$.
First check the gcd;

$$\gcd (6,21)=3\ne 1.$$

Therefore, $6$ is not a unit in ${\mathbb{Z}}_{21}$ and has no multiplicative inverse. (In fact $6\times 7=42=0$ in ${\mathbb{Z}}_{21}$, so $6$ is a zero divisor.)

Example. Find $4^{-1}$ in ${\mathbb{Z}}_{21}$.
Here $\gcd (4,21)=1$, so the inverse exists. Running the Euclidean algorithm;

$$\begin{array}{rl}21& =5\times 4+1,\\ 4& =4\times 1+0.\end{array}$$

The last nonzero remainder is $1$, confirming the gcd. Rearranging the first line for $1$;

$$\begin{array}{rl}1& =21-5\times 4\\ & =(-5)\times 4+1\times 21.\end{array}$$

So $x=-5$, and reducing into ${\mathbb{Z}}_{21}$ gives $-5=16$. Checking: $4\times 16=64=3\times 21+1=1$ in ${\mathbb{Z}}_{21}$. Therefore, $4^{-1}=16$ in ${\mathbb{Z}}_{21}$.

Alternative solution. Check small multiples of $21$ for a number that is $1$ away from a multiple of $4$;

$$\begin{array}{rl}1\times 21+1& =22,4\nmid 22,\\ 2\times 21+1& =43,4\nmid 43,\\ 3\times 21+1& =64=4\times 16.\end{array}$$

So $4\times 16=3\times 21+1$, i.e. $4\times 16=1$ in ${\mathbb{Z}}_{21}$, giving $4^{-1}=16$ as before. This trial method is often faster when $n$ is small; the extended Euclidean algorithm is the reliable choice when the numbers are large.

The inverse produced by the algorithm is frequently negative; always reduce it modulo $n$ before writing the final answer.

Example. Find $193^{-1}$ in ${\mathbb{Z}}_{283}$.
Here trial and error would be painful, so we use the extended Euclidean algorithm in full. First, the Euclidean algorithm to find $\gcd (193,283)$;

$$\begin{array}{rl}283& =1\times 193+90,\\ 193& =2\times 90+13,\\ 90& =6\times 13+12,\\ 13& =1\times 12+1,\\ 12& =12\times 1+0.\end{array}$$

The last nonzero remainder is $1$, so $\gcd (193,283)=1$ and the inverse exists. Now back-substitute from the second-last line, replacing each remainder in turn;

$$\begin{array}{rl}1& =13-1\times 12,\text{ (rearranging line 4)}\\ & =13-1\times (90-6\times 13),\text{ (substituting line 3)}\\ & =7\times 13-1\times 90\\ & =7\times (193-2\times 90)-1\times 90,\text{ (substituting line 2)}\\ & =7\times 193-15\times 90\\ & =7\times 193-15\times (283-1\times 193),\text{ (substituting line 1)}\\ & =22\times 193-15\times 283.\end{array}$$

So $x=22$, which is already in ${\mathbb{Z}}_{283}$. Checking: $193\times 22=4246=15\times 283+1$. Therefore, $193^{-1}=22$ in ${\mathbb{Z}}_{283}$.

Solving Equations with Inverses

The whole point of inverses is that they let us divide, which means we can solve linear equations in ${\mathbb{Z}}_n$ the same way we do in $\mathbb{R}$; provided the coefficient is a unit.

Example. Solve $5x=3$ in ${\mathbb{Z}}_7$.
Since $7$ is prime, $5$ is a unit; from the ${\mathbb{Z}}_7$ table earlier, $5^{-1}=3$. Multiplying both sides by the inverse;

$$\begin{array}{rl}5x& =3\\ 5^{-1}\times 5x& =5^{-1}\times 3\\ x& =3\times 3\\ & =9\\ & =2\text{ in }{\mathbb{Z}}_7.\end{array}$$

Checking: $5\times 2=10=7+3=3$ in ${\mathbb{Z}}_7$. Therefore, $x=2$ is the unique solution; uniqueness is guaranteed because we multiplied by an inverse, which is a reversible step.

Example. Solve $6x=3$ in ${\mathbb{Z}}_{21}$.
Here $\gcd (6,21)=3\ne 1$, so $6$ has no inverse and we cannot just divide; but that does not mean there are no solutions. The equation says $21\mid (6x-3)$, and since $3$ divides every term we can factorise the whole congruence by $3$;

$$\begin{array}{rl}6x& \equiv 3(\mathrm{mod}21)\\ 2x& \equiv 1(\mathrm{mod}7).\end{array}$$

Now $\gcd (2,7)=1$, so $2$ is invertible mod $7$ with $2^{-1}=4$ (since $2\times 4=8=1$ in ${\mathbb{Z}}_7$);

$$\begin{array}{rl}2x& \equiv 1(\mathrm{mod}7)\\ x& \equiv 4(\mathrm{mod}7).\end{array}$$

Lifting back to ${\mathbb{Z}}_{21}$, the elements congruent to $4$ mod $7$ are $x\in \{4,11,18\}$. Checking each: $6\times 4=24=3$, $6\times 11=66=3\times 21+3=3$, and $6\times 18=108=5\times 21+3=3$ in ${\mathbb{Z}}_{21}$. Therefore, the equation has three solutions, $x\in \{4,11,18\}$.

The decision process here is worth internalising: check $\gcd (a,n)$ first. If it is $1$, invert and get a unique solution; if $d=\gcd (a,n)>1$, then solutions exist only when $d$ divides the right hand side, in which case dividing the whole congruence (including the modulus!) by $d$ gives exactly $d$ solutions in ${\mathbb{Z}}_n$.

Irreducible and Prime Elements

Now that we have encountered units, we can refine our earlier definitions of irreducible and prime elements so that they make sense in any ring.

Basically, irreducible means "cannot be factorised except trivially" (a unit times something is a trivial factorisation, since units can always be absorbed), while prime means "whenever it divides a product it divides one of the factors". These used to look like the same idea; in $\mathbb{Z}$ they coincide, which is why we never needed to distinguish them before. The unit condition also explains our old exclusions: for $R=\mathbb{N}$ we banned $p=0,1$ since ${\mathbb{N}}^{\ast }=\{1\}$, and for $R=\mathbb{Z}$ we banned $p=0,\pm 1$ since ${\mathbb{Z}}^{\ast }=\{-1,1\}$.

Example. No element of ${\mathbb{Z}}_5$ is irreducible nor prime.
Since $5$ is prime, ${\mathbb{Z}}_5$ is a field by the field theorem; so every element is either $0$ or a unit, and nothing survives the first bullet point of either definition.

Example. Show that in ${\mathbb{Z}}_6$, the element $2$ is prime but not irreducible.
First, the setup: ${\mathbb{Z}}_6^{\ast }=\{1,5\}$ (the elements coprime with $6$), and $2\ne 0$ with $2\notin {\mathbb{Z}}_6^{\ast }$, so $2$ passes the first bullet of both definitions.

Not irreducible. We need a factorisation of $2$ using no units. Notice that

$$\begin{array}{rl}2\times 4& =8\\ & =6+2\\ & =2\text{ in }{\mathbb{Z}}_6,\end{array}$$

so $2=2\times 4$ where $\gcd (2,6)=2$ and $\gcd (4,6)=2$; neither factor is a unit. Therefore, $2$ is not irreducible in ${\mathbb{Z}}_6$.

Prime. The multiples of $2$ in ${\mathbb{Z}}_6$ are $2\times \{0,1,2,3,4,5\}=\{0,2,4\}$, so $2\mid x$ in ${\mathbb{Z}}_6$ exactly when $x\in \{0,2,4\}$. Suppose $2\nmid a$ and $2\nmid b$, i.e. $a,b\in \{1,3,5\}$. Checking all products of these residues;

$$\begin{array}{rl}1\times 1=1,1\times 3=3,1\times 5& =5,\\ 3\times 3=9& =3,\\ 3\times 5=15& =3,\\ 5\times 5=25& =1\text{ in }{\mathbb{Z}}_6,\end{array}$$

every product lands back in $\{1,3,5\}$, so $2\nmid ab$. By the contrapositive, $2\mid ab$ forces $2\mid a$ or $2\mid b$. Therefore, $2$ is prime in ${\mathbb{Z}}_6$, despite not being irreducible. Prime and irreducible are genuinely different notions in a general ring; they only happen to agree in familiar rings like $\mathbb{Z}$.