Modular Arithmetic
The finite set ℤn, is closely related to the infinite set ℤ. So it is natural to ask if it is possible to define addition and multiplication in ℤn and do some reasonable kind of arithmetic there. To define addition in ℤn, we must have some way of taking two classes in ℤn and producing another class− their sum. Because addition of integers is defined, the following tentative definition seems worth investigating: The sum of the classes [a] and [c] is the class containing a + c or, in symbols,
Definition 4.2.1. Let [a] and [b] be elements of ℤn, then By proposition 4.2 the following operations can be defined
[a]n + [b]n := [a + b]n
[a]n ⋅ [b]n := [a ⋅ b]n □
Example 4.2.2. In ℤ5; we have [3] + [4] = [3 + 4] = [7] = [2] and [3] ⋅ [2] = [3 ⋅ 2] = [6] = [1]. ■
Proposition 4.2.3. Addition and multiplication ℤn x ℤn → ℤn are well defined functions: that is independent of which class representative is chosen.
Proof. It is clear that the rule [a]n + [b]n yields an element of ℤn (closure of the operation), but the uniqueness of this result needs to be verified. In other words, closure is obvious, but we need to show that the operation is well-defined. To do this, suppose that [a] = [c] and [b] = [d]. Then
[a] = [c] ⇒ a ≡ c (mod n) and [b] = [d] ⇒ b ≡ d (mod n).
a + b ≡ c + d (mod n),
and therefore [a + b]n = [c + d]n. A similar argument holds true for multiplication.□
New 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 ℤ6 for instance, we might say 6 = 0, which is certainly true for classes in ℤ6 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 ℤ5 we may write things like
4 + 1 = 0 or 3 ⋅ 4 = 2 or 4 + 4 = 3
On those few occasions where this usage might cause confusion, we will return to the brackets notation for classes.
When dealing with finite groups, is useful to write down a table representing the operations. For example the tables for ℤ4 and ℤ5 are
ℤ4
| + | [0]4 | [1]4 | [2]4 | [3]4 |
|---|---|---|---|---|
| [0]4 | [0]4 | [1]4 | [2]4 | [3]4 |
| [1]4 | [1]4 | [2]4 | [3]4 | [0]4 |
| [2]4 | [2]4 | [3]4 | [0]4 | [1]4 |
| [3]4 | [3]4 | [0]4 | [1]4 | [2]4 |
| ⋅ | [0]4 | [1]4 | [2]4 | [3]4 |
|---|---|---|---|---|
| [0]4 | [0]4 | [0]4 | [0]4 | [0]4 |
| [1]4 | [0]4 | [1]4 | [2]4 | [3]4 |
| [2]4 | [0]4 | [2]4 | [0]4 | [2]4 |
| [3]4 | [0]4 | [3]4 | [2]4 | [1]4 |
ℤ5
| + | 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 |
ℤ6
| + | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | 2 | 3 | 4 | 5 | 0 |
| 2 | 2 | 3 | 4 | 5 | 0 | 1 |
| 3 | 3 | 4 | 5 | 0 | 1 | 2 |
| 4 | 4 | 5 | 0 | 1 | 2 | 3 |
| 5 | 5 | 0 | 1 | 2 | 3 | 4 |
| ⋅ | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| 2 | 0 | 2 | 4 | 0 | 2 | 4 |
| 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 4 | 0 | 4 | 2 | 0 | 4 | 2 |
| 5 | 0 | 5 | 4 | 3 | 2 | 1 |
The first table relates to addition and the second to multiplication in ℤn. We've written for sake of simplicity, 0, 1, 2, 3, 4 instead of [0]5, [1]5, [2]5, [3]5, [4]5. We see that [2]5 + [3]5 = [0]5 = [3+2]5.
Units and zero divisors
Notice the different structure of ℤ4 and ℤ5, the first set has zero divisors (see Definition 2.2.3) indeed we see that [2]4 ⋅ [2]4 = [0]4 whilst ℤ5 has no zero divisors. Thus ℤ4 is not an integral domain, but ℤ5 is.
Definition 4.2.4 An element [a] ∈ ℤ/nℤ distinct from 0 is called invertible if there is an element [b] ∈ ℤ/nℤ such that [a][b] = [1]. □
An integer a will also be called invertible modulo n if the class a is invertible.
In ℤ7, every nonzero element is invertible: [1][1] = [1], [2][4] = [8], [3][5] = [15] = [1], and [6][6] = [−1][−1] = [1].
In ℤ5 any element different from zero is invertibile, i.e. multiplied for a specific element yields [1]5, which is, the neuter element with regards to multiplication in ℤ5. This is noticeable in the multiplicative Cayley's table for ℤ5: in each row, except the one labelled with 0, appears 1. For example, in the row labelled with 2 we have 1 by crossing with the column labelled with 3, because [2]5 · [3]5 = [1]5; hence [2]5 is invertible in ℤ5 with [3]5 the inverse of [2]3.
The subset of ℤn that consists of exaclty those elements of ℤn with multiplicative inverses is denoted U(ℤn).
U(ℤn) = {[a] ∈ ℤn: [a][b] = [1] for some [b] ∈ ℤn} = {[a] ∈ ℤn: gcd(a,n) = 1}
U(ℤ4) = {[1], [3]} as the determination of the invertible elements of ℤ4, consists in resolving the congruence
ax ≡ 1 (mod n)
and 3 ⋅ 3 ≡ 1 mod 4. Similarly U(ℤ5) = {[1], [2], [3], [4]}; whereas U(ℤ6) = {[1], [5]}.
We shall prove that the set U(ℤn) under multiplication mod n provides the standard example of finite multiplicative group.
ℤ5 behaves as the ring ℚ of rational numbers or ℝ of real numbers (rings of this kind are known as fields), in which all elements different from zero are invertible, equivalently, in which is always possible to divide an element by another element different from zero, and not as in ℤ, in which these properties do not hold true. Conversely, ℤ6, hsa weaker properties than those whihc hold in ℤ. For example, in ℤ (as in ℚ and in ℝ, and as well in ℤ5) the cancellation law for the product holds true: if the product of two elements is zero, one of them must be zero. This does not hold in ℤ6, as we can see from its multiplicative table; for example [2]6 · [3]6 = [0]6, even if [2]6 ≠ [0]6 ≠ [3]6.
The multiplicative inverse element of 3 modulo 10 is 7 (because 3 ⋅ 7 = 21 ≡ 1 (mod 10) ), but the inverse of 4 modulo 10 does not exists. The criterion for the existence of solutions of a linear congruence (Corollary 4.5.8) implies that a class [a]n is invertible if and only if (a, n) = 1. In this case, the multiplicative inverse modulo n can be computed using the extended Euclidean algorithm. Therefore, it is clear that the product of two invertible classes is itself invertible.
We see that ℤ, ℤ5 and ℤ6 are very different algebraic structure. As we are going to study the properties of ℤn are determined by the arithemtical properties of the numbers n which define them. For example, we can prove that ℤn is an integral domaing only if n is a prime number.
Proposition 4.2.5. For n > 1, ℤn is an integral domain if and only if n is a prime.
Proof. Suppose first that n is a prime. Let [a] ≠ [0] in ℤn, and suppose [a][b] = 0 for some [b] in ℤn. Now [a][b] = 0 implies that [ab] = 0, and therefore, n| ab. However, [a] ≠ 0 means that n ∤ a. Thus n | ab and n ∤ a imply by Euclid's lemma that n|b, that is [b] = 0. We have shown that if [a] ≠ [0], the only way that [a][b] = 0 can be [0] is for [b] to be [0]. Therefore, ℤn has no zero divisors and is an integral domain.
Suppose now that n is not a prime and [a][b] = 0 holds true. Then n has divisors other than ± 1 and ± n, so there are integers a and b such that
n = ab where 1 < a < n and 1 < b < n
This means that [a] ≠ [0], [b] ≠ 0, but
[a] [b] = [ab] = [n] = [0]
Therefore, [a] is a zero divisor in ℤn, and ℤn is not an integral domain. Combining the two cases, we see that n is a prime if and only if ℤn is an integral domain. □
Corollary 4.2.6 . Let n a given positive integer. Then for every a,b,c,d ∈ ℤ and if a ≡ b mod n, then following relations hold
a+b ≡ b + c (mod n) (4.2.1)
ac ≡ bc (mod n) (4.2.2)
ai ≡ bi (mod n) (4.2.3)
Proof. It is a corollary of Proposition 4.1.10, 4.2.1 and 4.2.2 are particular cases of the relations present in the proposition, whist (2.6.4) can be obtained by induction.
P(0) is trivially true, as a0 = b0 = 1.
P(1) is true, as this just says: a ≡ b (mod m)
Suppose ak ≡ bk (mod m).
Then aak ≡ bbk (mod m) by definition of modulo multiplication.
Thus ak+1 ≡ bk+1 (mod m). □
We have seen that some of the properties holding for the = hold true also for ≡. However, it would be wrong to assume that every property holding for the equality holds for congruences as well. For instance, in ℤ we have the following cancellation property:
ac = bc (c ≠ 0) implies a = b,
In other words, ℤ is an integral domain. This property does not hold, in general, for congruences, as the following example shows:
3 · 5 ≡ 3 · 8, mod 9
but you could use the cancellation law here
2 · 3 ≡ 7 · 3 (mod 5)
2 ≡ 7 (mod 5)
because ℤ5 is an integral domain.
Remark. Don't use the cancellation law in cases such as 5 · 3 = 5 · 2 mod 5, you cannot cancel 5 becaus is the 0 of the ring.
Nevertheless, the following result holds:
Proposition 4.12. (Cancellation Law) Let n > 1 be an integer. If ac ≡n bc and (c, n) = 1, then
a ≡n b.
Proof. If ac ≡n bc, then n | (a − b)c. As GCD(c, n) = 1, there exist s, t such that 1 = sc + tn and by multiplying both members by a − b, it is possible to write
a − b = (a − b) sc + (a − b) tn = (a − b) c ⋅ s + (a − b)tn
thus n | a − b, because it divides the second member, consequenlty a ≡n b.□
Proposition 4.13. Let n > 1 be an integer. If ac ≡ bc (mod n), then a ≡ b (mod n/d), where d = GCD(c, n).
Proof. The proposition says that it's possible to simplify a congruence eliminating a term, but the module must be changed accordingly. ac ≡ bc (mod n) ⇐⇒ (a − b) c = kn, from which dividing by d = GCD(c, n), we find that
(a − b) c/d = k(n/d)
(the fraction c/d and n/d are integers numbers). Thus n/d divides the product (a − b) c/d and n/d and c/d are coprime: f = c/d, m = n/d, d = gcd(c,n) so gcd(f,m) = gcd(c,n)/d = 1, and so n/d divides a − b, thus a ≡n/d b. □
For instance, 21 = 3 · 7 ≡9 30 = 3 · 10 and 7 ≢ 10 (mod 9), while 7 ≡ 10 (mod 3).
5 ≢ 8 (mod 9), 5 ≡ 8 (mod 9/3).
Remark 4.14. As a consequence of the above, we may see, for instance, that in ℤ5 the same cancellation property holds as in ℤ; in other words, ℤ5 is, like ℤ, an integral domain, and consequently, since it is finite, a field (see Exercise A1.48). Indeed, if ā · b̄ = 0 with ā, b̄ ∈ ℤ5 and b̄ ≠ = 0, then ā = 0 by Proposition 4.8, as GCD(b, 5) = 1. So ℤ5 is an integral domain. On the other hand, the same results say nothing about ℤ4. In fact, in ℤ4 there are zero-divisors: we have 2 ·2 = 0 with 2 ≠ 0.
Proposition 4.15. The following properties hold:
if a ≡n b and d | n, then a ≡i b;
if a ≡n b and a ≡m b, then a ≡ b (mod lcm(n, m)).
Proof. They follow directly from the definition of congruence.□
Exercise 4.13 - On the set ℤ consider the following two equivalence relations:
a ≡ b (mod n), that is a𝓡b if and only if a − b = nh for some integer h.
a𝓢b if and only if if a and b have the same remainder when divided by n.
Show that a ≡ b (mod n) if and only if a𝓢b; and the two equivalence relations determine the same classes.
Solution. We prove first that a ≡ b (mod n), implies a𝓢b. If
a − b = hn for some integer h (2.0)
then a and b have the same remainder when divided by n. Suppose that a has been divided by n, producing the quotient q and the remainder r with 0 ≤ r < n. This means that a = nq + r. Replacing a in (2.0) with nq + r yields
b = a − hn = (nq + r) − hn = n(q − h) + r
Let's now divide b by n:
b / n = [n(q − h) + r]/n = (q − h) + r/n
This means that the quotient of the division is the integer q − h, and the remainder is r. Thus, a and b have the same remainder when divided by n.
Let’s now prove the converse: a𝓢b, implies a ≡n b. By hypothesis a and b have the same remainder when divided by n; call this common remainder r. Then a = nh + r and b = nk + r with h and k integers, and 0 ≤ r < n. To prove that a ≡n b we need to check whether a − b is divisible by n. Using the information we have for a and b we obtain
a − b = (nh + r) − (nk + r) = nh − nk = n(h − k)
The number h − k is an integer because h and k are integers. Thus a ≡n b.
Part 2. We must prove that the relations "≡m" and "𝓢" are equal. By definition [a]m = {b ∈ ℤ| b ≡ a (mod m)} and [a]𝓢 = {b ∈ ℤ|b𝓢a}. Let b ∈ [0]m, or equivalently, let a ≡m b. By part 1 this is equivalent to stating that a𝓢b. In turn, this is equivalent to saying that b ∈ [a]𝓢. Since b ∈ [a]m if and only if b ∈ [a]m, the two equivalence classes are identical.□
It is important to know when two relations produce the same equivalence classes, because it is then possible to use either one of the two relations, depending on which one is handier in a given setting.