§2.3 Arithmetic in ℤ_p and ℤ_n

Overview of Arithmetic in ℤ_p and ℤ_n

We now present some facts about the structure of ℤ_n (particularly when \(n\) is prime) that will provide a model for our future work. First, however, we make a change of notation.

We have been very careful to distinguish integers in ℤ and classes in ℤ_n and have even used different symbols for the operations in the two systems. By now, however, you should be reasonably comfortable with the fundamental ideas and familiar with arithmetic in ℤ_n. So we shall adopt a new notation that is widely used in mathematics, even though it has the flaw that the same symbol represents two totally different entities.

Whenever the context makes clear that we are dealing with ℤ_n, we shall abbreviate the class notation "[a]" and write simply "a." In ℤ₆, for instance, we might say 6 = 0, which is certainly true for classes in ℤ₆ even though it is nonsense if 6 and 0 are ordinary integers. We shall use an ordinary plus sign for addition in ℤ_n and either a small dot or juxtaposition for multiplication. For example, in ℤ₅ we may write things like:

\(4 + 1 = 0 \quad \text{or} \quad 3 \cdot 4 = 2 \quad \text{or} \quad 4 + 4 = 3\).

On those few occasions where this usage might cause confusion, we will return to the bracket notation for classes.

Working within \( \mathbb{Z}_p \), especially when \( p \) is prime, reveals key properties that differentiate it from general modular systems like \( \mathbb{Z}_n \). These properties are foundational for understanding advanced topics in number theory.

Example 2.3.1: Addition and Multiplication in ℤ₃

In this new notation, the addition and multiplication tables for ℤ₃ are:

Understanding Exponents in \( \mathbb{Z}_n \)

CAUTION: Exponents are applied as ordinary integers, not modular elements. For instance, in \( \mathbb{Z}_3 \), \( 2^4 \) refers to multiplying 2 (in the integer sense) four times:

\( 2 \cdot 2 \cdot 2 \cdot 2 = 16 \), and \( 16 \equiv 1 \pmod{3} \).

This is distinct from \( 2^1 = 2 \), even though in \( \mathbb{Z}_3 \), \( 4 \equiv 1 \). Be cautious about interpreting exponents in modular arithmetic, as they follow regular integer rules, not modular equivalence.

Key Properties of ℤ_p When \(p\) Is Prime

Some of the \(\mathbb{Z}_n\) do not share all the nice properties of \(\mathbb{Z}\). For instance, the product of nonzero integers in \(\mathbb{Z}\) is always nonzero, but in \(\mathbb{Z}_6\), we have \(2 \cdot 3 = 0\) even though \(2 \neq 0\) and \(3 \neq 0\). On the other hand, the multiplication table on page 34 shows that the product of nonzero elements in \(\mathbb{Z}_5\) is always nonzero. Indeed, \(\mathbb{Z}_5\) has a much stronger property than \(\mathbb{Z}\). When \(a \neq 0\), the equation \(ax = 1\) has a solution in \(\mathbb{Z}\) if and only if \(a = \pm1\). But the multiplication table for \(\mathbb{Z}_5\) shows that, for any \(a \neq 0\), the equation \(ax = 1\) has a solution in \(\mathbb{Z}_5\); for example:

\(x = 3\) is a solution of \(2x = 1\)
\(x = 4\) is a solution of \(4x = 1\).

More generally, whenever \(n\) is prime, \(\mathbb{Z}_n\) has special properties:

Theorem 2.8: Prime \(p\) and Equivalent Conditions in ℤ_p

If \(p > 1\) is an integer, then the following conditions are equivalent:*

1. \(p\) is prime.
2. For any \(a \neq 0\) in \(\mathbb{Z}_p\), the equation \(ax = 1\) has a solution in \(\mathbb{Z}_p\).
3. Whenever \(bc = 0\) in \(\mathbb{Z}_p\), then \(b = 0\) or \(c = 0\).

The proof of this theorem illustrates the two basic techniques for proving statements that involve \(\mathbb{Z}_n\):

• Translate equations in \(\mathbb{Z}_n\) into equivalent congruence statements in \(\mathbb{Z}\). Then the properties of congruence and arithmetic in \(\mathbb{Z}\) can be used. The bracket notation for elements of \(\mathbb{Z}_n\) may be necessary to avoid confusion.
• Use the arithmetic properties of \(\mathbb{Z}_n\) directly, without involving arithmetic in \(\mathbb{Z}\). In this case, the bracket notation in \(\mathbb{Z}_n\) isn't needed.

Proof of Theorem 2.8

(1) ⇒ (2) We use the first technique. Suppose \(p\) is prime and \([a] \neq [0]\) in \(\mathbb{Z}_p\). Then in \(\mathbb{Z}\), \(a \not\equiv 0 \pmod{p}\) by Theorem 2.3. Hence, \(p \nmid a\) by the definition of congruence. Now the gcd of \(a\) and \(p\) is a positive divisor of \(p\) and thus must be either \(p\) or 1. Since \((a, p)\) also divides \(a\) and \(p \nmid a\), we must have \((a, p) = 1\). By Theorem 1.2, \(au + pv = 1\) for some integers \(u\) and \(v\). Hence, \(au - 1 = p(-v)\), so that \(au \equiv 1 \pmod{p}\). Therefore, \([au] = [1]\) in \(\mathbb{Z}_p\) by Theorem 2.3. Thus \([a][u] = [au] = [1]\), so that \(x = [u]\) is a solution of \([a]x = [1]\).

(2) ⇒ (3) We use the second technique. Suppose \(ab = 0\) in \(\mathbb{Z}_p\). If \(a = 0\), there is nothing to prove. If \(a \neq 0\), then by (2) there exists \(u \in \mathbb{Z}_p\) such that \(au = 1\). Then:

\(0 = u \cdot 0 = u(ab) = (ua)b = (au)b = 1 \cdot b = b\)

In every case, therefore, we have \(a = 0\) or \(b = 0\).

(3) ⇒ (1) Back to the first technique. Suppose that \(b\) and \(c\) are any integers and that \(p \mid bc\). Then \(bc \equiv 0 \pmod{p}\). So by Theorem 2.3:

\([b][c] = [bc] = [0]\) in \(\mathbb{Z}_p\).

Hence, by (3), we have \([b] = [0]\) or \([c] = [0]\). Thus, \(b \equiv 0 \pmod{p}\) or \(c \equiv 0 \pmod{p}\) by Theorem 2.3, which means that \(p \mid b\) or \(p \mid c\) by the definition of congruence. Therefore, \(p\) is prime by Theorem 1.5. \(\blacksquare\)

Exploring the Structure of ℤ_n When \(n\) Is Composite

When \(n\) is not prime, the equation \(ax = 1\) need not have a solution in \(\mathbb{Z}_n\). For instance, the equation \(2x = 1\) has no solution in \(\mathbb{Z}_4\), as you can easily verify. The next result tells us exactly when \(ax = 1\) does have a solution in \(\mathbb{Z}_n\). For clarity, we use bracket notation.

*See page 508 in Appendix A for the meaning of "the following conditions are equivalent" and what must be done to prove such a statement.

Theorem 2.9: Solving \(ax=1\) in ℤ_n

Let \(a\) and \(n\) be integers with \(n > 1\). Then:

The equation \([a]x = [1]\) has a solution in \(\mathbb{Z}_n\) if and only if \((a, n) = 1\) in \(\mathbb{Z}\).

Proof of Theorem 2.9

Since this is an "if and only if" statement, the proof has two parts.

First, we assume that the equation has a solution and show that \((a, n) = 1\). If \([w]\) is a solution of \([a]x = [1]\), then:

\([a][w] = [1]\)

\(aw = [1] \quad \text{[Multiplication in } \mathbb{Z}_n]\)

\(aw = 1 \ (\text{mod} \ n) \text{ in } \mathbb{Z} \quad \text{[Theorem 2.3]}\)

\(aw - 1 = kn \text{ for some integer } k \quad \text{[Definition of congruence]}\)

\(aw + n(-k) = 1 \quad \text{[Rearrange terms]}\)

Denote \((a, n)\) by \(d\). Since \(d\) is a common divisor of \(a\) and \(n\), there are integers \(r\) and \(s\) such that \(dr = a\) and \(ds = n\). So we have:

\(aw + n(-k) = 1\)

\(d r w + d s(-k) = 1\)

\(d(r w + s(-k)) = 1\)

So \(d \mid 1\). Since \(d\) is positive by definition, we must have \(d = 1\), that is, \((a, n) = 1\).

Now we assume that \((a, n) = 1\) and show that \([a]x = [1]\) has a solution in \(\mathbb{Z}_n\). Actually, we've already done this. In the proof of \((1) \Rightarrow (2)\) of Theorem 2.8, the primeness of \(p\) is used only to show that \((a, p) = 1\). From there on, the proof is valid in any \(\mathbb{Z}_n\) where \((a, n) = 1\), and shows that \([a]x = [1]\) has a solution in \(\mathbb{Z}_n\).

Units and Zero Divisors

Some special terminology is often used when dealing with certain equations. An element \(a\) in \(\mathbb{Z}_n\) is called a unit if the equation \(ax = 1\) has a solution. An element \(a\) is a unit if there is an element \(b\) in \(\mathbb{Z}_n\) such that \(ab = 1\). In other words, \(a\) is the inverse of \(b\). Note that \(ab = 1\) also says that \(b\) is a unit (with inverse \(a\)).

Example 2.3.2: Identifying Units in ℤ_n

Both 2 and 8 are units in \(\mathbb{Z}_{15}\) because \(2 \cdot 8 = 1\). 8 is the inverse of 2 and 2 is the inverse of 8. Similarly, 3 is a unit in \(\mathbb{Z}_4\) because \(3 \cdot 3 = 1\). So 3 is its own inverse.

Example 2.3.3: All Nonzero Elements as Units in ℤ_p

Part (2) of Theorem 2.8 says that when \(p\) is prime, every nonzero element of \(\mathbb{Z}_p\) is a unit.

Theorem 2.10: Conditions for Units in ℤ_n

Let \(a\) and \(n\) be integers with \(n > 1\). Then:

\([a] \text{ is a unit in } \mathbb{Z}_n \text{ if and only if } (a, n) = 1 \text{ in } \mathbb{Z}\).

A nonzero element \(a\) of \(\mathbb{Z}_n\) is called a zero divisor if the equation \(ax = 0\) has a nonzero solution (that is, if there is a nonzero element \(c\) in \(\mathbb{Z}_n\) such that \(ac = 0\)).

Example 2.3.4: Zero Divisors in ℤ_n

Both 3 and 5 are zero divisors in \(\mathbb{Z}_{15}\) because \(3 \cdot 5 = 0\). Similarly, 2 is a zero divisor in \(\mathbb{Z}_4\) because \(2 \cdot 2 = 0\).

Example 2.3.5: No Zero Divisors in ℤ_p

Part (3) of Theorem 2.8 says that when \(p\) is prime, there are no zero divisors in \(\mathbb{Z}_p\).