Section 9.3 \(\mathbb{Z}/m\)
In this section we introduce a set \(\mathbb{Z}/m\) that will be important your future algebra classes. Just like the integers, the rationals, and the reals, it is what is called a ring: it is equipped with addition, subtraction, and multiplication operations. Unlike \(\mathbb{Z}\text{,}\) \(\mathbb{Q}\text{,}\) or \(\mathbb{R}\text{,}\) the set \(\mathbb{Z}/m\) is finite.
As a set,
On this set we shall define addition and multiplication operations: for any \(x,y \in \mathbb{Z}/m\text{,}\)
and
There is an additive inverse:
(Some books write \(\mathbb{Z}_m\) for \(\mathbb{Z}/m\text{,}\) but most algebraists reserve this notation for a very different object!!)
Example 9.3.1.
Let's write the addition and multiplication tables for \(\mathbb{Z}/5=\{0,1,2,3,4\}\text{.}\)
| {\(+\)} | {0} | {1} | {2} | {3} | {4} |
| {0} | {0} | {1} | {2} | {3} | {4} |
| {1} | {1} | {2} | {3} | {4} | {0} |
| {2} | {2} | {3} | {4} | {0} | {1} |
| {3} | {3} | {4} | {0} | {1} | {2} |
| {4} | {4} | {0} | {1} | {2} | {3} |
| {×} | {0} | {1} | {2} | {3} | {4} |
| {0} | {0} | {0} | {0} | {0} | {0} |
| {1} | {0} | {1} | {2} | {3} | {4} |
| {2} | {0} | {2} | {4} | {1} | {3} |
| {3} | {0} | {3} | {1} | {4} | {2} |
| {4} | {0} | {4} | {3} | {2} | {1} |
We can check that for \(m\in\mathbb{N}\text{,}\) \(\mathbb{Z}/m\) has all the nice algebraic properties of being a field (recall this definition from Week 1) apart from perhaps property (M4), which said that each nonzero element must have a multiplicative inverse. An element \(x\in \mathbb{Z}/m\) is invertible if there exists \(y\in \mathbb{Z}/m\) so that \(x\cdot y=1\text{.}\)
If \(m\) is composite, then not every nonzero element \(\mathbb{Z}/m\) is invertible. Consider the multiplication table of \(\mathbb{Z}/4\text{:}\)
| {×} | {0} | {1} | {2} | {3} |
| {0} | {0} | {0} | {0} | {0} |
| {1} | {0} | {1} | {2} | {3} |
| {2} | {0} | {2} | {0} | {2} |
| {3} | {0} | {3} | {2} | {1} |
As you can see, \(2x=1\) has no solution modulo \(4\text{.}\)
Observe that an element \(a \in \mathbb{Z}/m\) is invertible if and only if the equation \(ax = 1 \mod m\) admits a solution. Such a solution exists if and only if \(\gcd(a,m)\) divides \(1\text{,}\) hence if and only if \(a\) and \(m\) are coprime. Thus the invertible elements of \(\mathbb{Z}/m\) are precisely those elements that are coprime to \(m\text{.}\) In particular, if \(p\) is prime, then every nonzero element of \(\mathbb{Z}/p\) is coprime to \(p\text{,}\) so we deduce the following.
Proposition 9.3.2.
Let \(m\geq 2\) be a natural number. Then \(\mathbb{Z}/m\) is a field if and only if \(m\) is prime.
Exercise 9.3.3.
How many invertible elements are there in \(\mathbb{Z}/{81}\text{?}\)
An element \(y\in\mathbb{Z}/{81}\) is invertible if and only if \(x\) and \(81\) are coprime. The is possible if and only if \(3\) does not divide \(y\text{.}\) The number of numbers in \(\{0,1,...,80\}\) divisible by \(3\) is \(\frac{81}{3}=27\text{,}\) so the number of invertible elements is \(81-27 = 54\text{.}\)
Just like there is a notion of inverses for \(\mathbb{Z}/m\text{,}\) we also have a notion of a root. We say \(y\in\mathbb{Z}/m\) is the \(n\)-th root of \(x\in\mathbb{Z}\) if \(x^n=y\text{.}\)
Example 9.3.4.
In \(\mathbb{Z}/{5}\text{,}\) does \(2\) have a cubed root? Let us test the values:
\(0^{3}=0\text{.}\)
\(1^{3}=1\text{.}\)
\(2^{3}=3\) since \(2^{3} = 8 = 3\mod 5\text{.}\)
\(3^{3}=2\) since \(3^{3} = 27 = 2\mod 5\text{.}\)
\(4^{3}=4\) since \(4^{3} = (-1)^{3}=-1 = 4 \mod 5\text{.}\)
Thus, the unique cubed root of \(2\) is \(3\text{.}\)
However, not all numbers in every \(\mathbb{Z}/m\) have roots! Confirm for yourself that \(2\in\mathbb{Z}/{4}\) has no cubed root.
Theorem 9.3.5. Chinese Remainder Theorem.
Let \(a,b \in \NN\text{.}\) Consider the map \(\theta \colon \ZZ/(ab) \to \ZZ/a \times \ZZ/b \) that carries \(n\) to the pair \((r,s)\) in which \(r = n \mod a\) and \(s = n \mod b\text{.}\) If \(a\) and \(b\) are coprime, then \(\theta\) is a bijection.
Proof.
Let \((r,s) \in \ZZ/a \times \ZZ/b\text{.}\) We must show that there exists a unique \(n \in \ZZ/(ab)\) such that \(r = n \mod a\) and \(s = n \mod b\text{.}\)
Let's prove uniqueness first. Suppose that \(n_1, n_2\) are two natural numbers such that \(r = n_i \mod a\) and \(s = n_i \mod b\) for \(i \in \{1,2\}\text{.}\) Then \(n_1 -n_2\) is divisible by both \(a\) and \(b\text{,}\) and since \(a \) and \(b \) are coprime, it follows that \(ab\) divides \(n_1 - n_2\text{.}\)
Now let's prove existence. By the Bezout theorem, there exist integers \(c,d\in \ZZ\) such that \(ca+db = 1\text{.}\) Thus \(ca = 1 \mod b\) and \(db = 1 \mod a\text{.}\) Now let \(N = cas+dbr\text{,}\) so that \(N = cas = s \mod b\) and \(N = bdr = r \mod a\text{.}\) Thus \(n = N \mod (ab)\) is the desired element of \(\ZZ/(ab)\text{.}\)