5.5: Division in \(\mathbb{Z}_{b}\)

The next result is a game changer! It tells us that there is a unique element \(a^{-1}\) such that \(aa^{-1} = _{b} 1\) if and only if \(a\) is in the reduced set of residues (modulo \(b\)). Thus division is well-defined in the reduced set of residues modulo \(b\). This serves as a clear signal to emphasize two distinct algebraic structures. A ring is a structure with addition and its inverse subtraction plus multiplication, but where multiplication may not have an inverse. A field is almost the same, but now multiplication always has an inverse: division. A more detailed description of these algebraic construction is given in Section ??. The numbers \(1\) and \(-1\) are always in the reduced set of residues modulo \(b\). This set is sometimes called the set of units (see Definition ??) of \(\mathbb{Z}_{b}\).

Proposition 5.16

Let \(\mathbb{R}\) be a reduced set of residues modulo \(b\). Then

1. for every \(a \in \mathbb{R}\), there is a unique \(a'\) in \(\mathbb{R}\) such that \(a′a = _{b} aa′ = _{b} 1\)
2. for every \(a \notin \mathbb{R}\), there exists no \(x \in \mathbb{Z}_{b}\) such that \(ax = _{b} 1\)
3. let \(\mathbb{R} = \{x_{i}\}_{i=1}^{\varphi (b)}\), then also \(\mathbb{R} = \{x-1\} _{i=1}^{\varphi (b)}\).

Proof

Statement 1: The existence of a solution follows immediately from Be ́zout’s Lemma, namely\(a′ = _{b} x\) solves for \(x\) in \(ax+by = 1\). This solution must be in \(\mathbb{R}\), because \(a\), in turn, is the solution of \(a′x + by = 1\) and thus Be ́zout’s Lemma implies that \(\gcd (a',b) = 1\). Suppose we have two solutions \(ax = _{b} 1\) and \(ay = _{b} 1\), then uniqueness follows from applying the cancelation Theorem 2.7 to the difference of these equations.

Statement 2: By hypothesis, \(\gcd (a,b) > 1\). We have that \(ax = _{b} 1\) is equivalent to \(ax+by = 1\), which contradicts Be ́zout’s Lemma.

Statement 3: This is similar to Lemma 5.3. By (1), we know that all inverses are in \(R\). So if the statement is false, there must be two elements of \(R\). So if the statement is false, there must be two elements of \(R\) with the same inverse: \(ax = _{b} cx\). This is impossible by cancelation.

Lemma 5.17

Let \(p\) be prime. Then \(a^2 = _{p} 1\) if and only if \(a = _{p} \pm 1\)

Proof

We have

\[a^2 = _{p} 1 \Leftrightarrow a^{2}-1 = _{p} (a+1)(a-1) = _{p} 0 \Leftrightarrow p | (a+1)(a-1) \nonumber\]

Because \(p\) is prime, Corollary 2.12 says that either \(p | a+1\) (and so \(a = _{p} -1\)) or \(p | a-1\) (and so \(a = _{p} +1\)).

Perhaps, surprisingly, this last lemma is false if \(p\) is not prime. For example, \(4^2 = _{15} 1\), but \(4 \ne _{15} \pm 1\).

Theorem 5.18 (Wilson's theorem)

If \(p\) prime in \(\mathbb{Z}\), then \((p-1)! = _{p} -1\). If \(b\) is composite, then \((b-1)! \ne _{b} -1\)

Proof

This is true for \(p = 2\). If \(p > 2\), then Proposition 5.16(3) and Lemma 5.17 imply that every factor \(a_{i}\) in the product \((p-1)!\) other than \(-1\) or \(1\) has a unique inverse \(a_{i}'\) different from itself. The factors \(a_{i}'\) run through all factors \(2\) through \(p-2\) exactly once. Thus in the product, we can pair each \(a_{i}\) different from \(\pm 1\) with its inverse. This gives

\[(p-1)! = _{p} (+1)(-1) \prod a_{i}a_{i}' = _{p} -1 \nonumber\]

The second part is easier. If \(b\) is composite, there are least residues \(a\) and \(b\) greater than \(1\) so that \(ad = _{b} 0\). Now either we can choose \(a\) and \(b\) distinct and then \((b-1)!\) contains the product \(ad\), and thus it equals zero mod \(b\). Or else this is impssible and \(b = a^2\). But then still \(\gcd ((b-1)!, b) \ge a\). By Be ́zout, we must have \((b-1)!\) mod \(b\) must be a multiple of \(a\).

Wilson's theorem could be used to test primality of a number \(n\). However, this takes \(n\) multiplications, which in practice is more expensive than trying to divide \(n\) by all numbers less than \(\sqrt{n}\). Note, however, that if you want to compute a list of all primes between \(1\) and \(N\), Wilson’s theorem can be used much more efficiently. After computing \((k-1)! = _{k}\) to determine whether \(k\) is prime, it takes only \(1\) multiplication and \(1\) division to determine whether \(k+1\) is prime.

Here is the take-away that will be important for Chapter ??. More in particular, we have the following result.

Corollary 5.19

Let \(p\) be prime.

For every \(a \in \mathbb{Z}_{p}\) there is a unique \(a′ = _{p} -a\) such that \(a+a′ = _{p} 0\).

For every \(a \in \mathbb{Z}_{p}\) and \(a \ne 0\), there is a unique \(a′ = a^{-1}\) so that \(aa′ = _{p} 1\).

Addition and multiplication are well-defined in \(\mathbb{Z}_{b}\) (see exercises 5.1 and 5.2). Thus when \(p\) is prime, we can add, multiply, subtract, and divide in \(\mathbb{Z}_{p}\). In the words of Chapter ??, when \(p\) is a prime, then \(\mathbb{Z}_{p}\) is a field. It is an interesting fact that the same is not true for a composite number \(b\). According to Proposition 5.16, we need the reduced set of residues for the multiplication to be invertible. At the same time, for the set to be closed under multiplication, we need all of \(\mathbb{Z}_{b}\) (think of \(1+1+\dots\)). Thus the operations addition and multiplication in \(\mathbb{Z}_{b}\) collaborate with each other only if \(b\) is a prime.