Section 4.2. Modular Arithmetic

[Page 101]

4.2. Modular Arithmetic

Given any positive integer n and any nonnegative integer a, if we divide a by n, we get an integer quotient q and an integer remainder r that obey the following relationship:

Equation 4-1

where is the largest integer less than or equal to Figure 4.2 demonstrates that, given a and positive n, it is always possible to find q and r that satisfy the preceding relationship. Represent the integers on the number line; a will fall somewhere on that line (positive a is shown, a similar demonstration can be made for negative a). Starting at 0, proceed to n, 2n, up to qn such that qn q + 1)n > a. The distance from qn to a is r, and we have found the unique values of q and r. The remainder r is often referred to as a residue.

Figure 4.2. The Relationship a = qn + r, 0 n

a = 11;	n = 7;	11 = 1 x 7 + 4;	r = 4	q = 1
a = -11;	n = 7;	-11 = (-2) x 7 + 3;	r = 3	q = -2

If a is an integer and n is a positive integer, we define a mod n to be the remainder when a is divided by n. The integer n is called the modulus. Thus, for any integer a, we can always write:

a = n x a mod n)

11 mod 7 = 4;	-11 mod 7 = 3

Two integers a and b are said to be congruent modulo n, if (a mod n) = (b mod n). This is written as a n).^[3]

^[3] We have just used the operator mod in two different ways: first as a binary operator that produces a remainder, as in the expression a mod b; second as a congruence relation that shows the equivalence of two integers, as in the expression To distinguish the two uses, the mod term is enclosed in parentheses for a congruence relation; this is common but not universal in the literature. See Appendix D for a further discussion.

73 4 (mod 23);	21 -9 (mod 10)

[Page 102]

Divisors

We say that a nonzero b divides a if a = mb for some m, where a, b, and m are integers. That is, b divides a if there is no remainder on division. The notation is commonly used to mean b divides a. Also, if b|a, we say that b is a divisor of a.

The positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24.

The following relations hold:

If a|1, then a = ±1.
If a|b and b|a, then a = ±b.
Any b 0 divides 0.
b|g and b|h, then b|(mg + nh) for arbitrary integers m and n.

To see this last point, note that

If b|g, then g is of the form g = b x g₁ for some integers g₁.

If b|h, then h is of the form h = b x h₁ for some integers h₁.

mg + nh = mbg₁ + nbh₁ = b x (mg₁ + nh₁)

and therefore b divides mg + nh.

b = 7; g = 14; h = 63; m = 3; n = 2.

7|14 and 7|63. To show: 7|(3 x 14 + 2 x 63)

We have (3 x 14 + 2 x 63) = 7(3 x 2 + 2 x 9)

And it is obvious that 7|(7(3 x 2 + 2 x 9))

Note that if a 0 (mod n|a.

Properties of Congruences

Congruences have the following properties:

a n) if n|(a b).
a n) implies b n)..
a n) and b n) imply a n).

To demonstrate the first point, if n|(a b), then (a b) = kn for some k. So we can write a = b + kn. Therefore, (a mod n) = (reminder when b + kn is divided by n) = (reminder when b is divided by n) = (b mod n)

23 8 (mod 5)	because	23 8 = 15 = 5 3
11 5 (mod 8)	because	11 5 = 16 = 8 x (2)
81 0 (mod 27)	because	81 0 = 81 = 27 x 3

The remaining points are as easily proved.

[Page 103]

Modular Arithmetic Operations

Note that, by definition (Figure 4.2), the (mod n) operator maps all integers into the set of integers {0, 1,... (n 1)}. This suggests the question: Can we perform arithmetic operations within the confines of this set? It turns out that we can; this technique is known as modular arithmetic.

Modular arithmetic exhibits the following properties:

[(a mod n) + (b mod n)] mod n = (a + b) mod n
[(a mod n) (b mod n)] mod n = (a b) mod n
[(a mod n) x (b mod n)] mod n = (a x b) mod n

We demonstrate the first property. Define (a mod n) = r_a and (b mod n) = r_b. Then we can write a = r_a + jn for some integer j and b = r_b + kn for some integer k. Then

(a + b) mod n = (r_a + jn + r_b +kn) mod n

= (r_a + r_b (k + j)n) mod n

= (r_a + r_b) mod n

= [(a mod n] + (b mod n)] mod n

The remaining properties are as easily proved. Here are examples of the three properties:

11 mod 8 = 3; 15 mod 8 = 7
[(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2 (11 + 15) mod 8 = 26 mod 8 = 2
[(11 mod 8) (15 mod 8)] mod 8 = 4 mod 8 = 4 (11 15) mod 8 = 4 mod 8 = 4
[(11 mod 8) x (15 mod 8)] mod 8 = 21 mod 8 = 5 (11 x 15) mod 8 = 165 mod 8 = 5

Exponentiation is performed by repeated multiplication, as in ordinary arithmetic. (We have more to say about exponentiation in Chapter 8.)

To find 11⁷ mod 13, we can proceed as follows:
11² = 121 4 (mod 13)
11⁴ = (11²)² 4² 3 (mod 13)
11⁷ 11 x 4 x 3 132 2 (mod 13)

Thus, the rules for ordinary arithmetic involving addition, subtraction, and multiplication carry over into modular arithmetic.

[Page 104]

Table 4.1 provides an illustration of modular addition and multiplication modulo 8. Looking at addition, the results are straightforward and there is a regular pattern to the matrix. Both matrices are symmetric about the main diagonal, in conformance to the commutative property of addition and multiplication. As in ordinary addition, there is an additive inverse, or negative, to each integer in modular arithmetic. In this case, the negative of an integer x is the integer y such that (x + y) mod 8 = 0. To find the additive inverse of an integer in the left-hand column, scan across the corresponding row of the matrix to find the value 0; the integer at the top of that column is the additive inverse; thus (2 + 6) mod 8 = 0. Similarly, the entries in the multiplication table are straightforward. In ordinary arithmetic, there is a multiplicative inverse, or reciprocal, to each integer. In modular arithmetic mod 8, the multiplicative inverse of x is the integer y such that (x x y) mod 8 = 1 mod 8. Now, to find the multiplicative inverse of an integer from the multiplication table, scan across the matrix in the row for that integer to find the value 1; the integer at the top of that column is the multiplicative inverse; thus (3 x 3) mod 8 = 1. Note that not all integers mod 8 have a multiplicative inverse; more about that later.

Table 4.1. Arithmetic Modulo 8

[Page 105]

Properties of Modular Arithmetic

Define the set Z_n as the set of nonnegative integers less than n:

Z_n = {0, 1,...,(n 1)}

This is referred to as the set of residues, or residue classes modulo n. To be more precise, each integer in Z_n represents a residue class. We can label the residue classes modulo n as [0], [1], [2],...,[n 1], where

[r] = {a: a is an integer, a n)}

The residue classes modulo 4 are
	[0] = { ..., 16, 12, 8, 4, 0, 4, 8, 12, 16,... }
	[1] = { ..., 15, 11, 7, 3, 1, 5, 9, 13, 17,... }
	[2] = { ..., 14, 10, 6, 2, 2, 6, 10, 14, 18,... }
	[3] = { ..., 13, 9, 5, 1, 3, 7, 11, 15, 19,... }

Of all the integers in a residue class, the smallest nonnegative integer is the one usually used to represent the residue class. Finding the smallest nonnegative integer to which k is congruent modulo n is called reducing k modulo n.

If we perform modular arithmetic within Z_n, the properties shown in Table 4.2 hold for integers in Z_n. Thus, Z_n is a commutative ring with a multiplicative identity element (Figure 4.1).

Table 4.2. Properties of Modular Arithmetic for Integers in Z_n

Property

Expression

Commutative laws

(w + x) mod n = (x + w) mod n
(w x x) mod n = (x x w) mod n

Associative laws

[(w + x) + y] mod n = [w + (x + y)] mod n
[(w x x) x y] mod n = [w x (x x y)] mod n

Distributive laws

[w + (x + y)] mod n = [(w x x) + (w x y)] mod n
[w + (x x y)] mod n = [(w + x) x (w + y)] mod n

Identities

(0 + w) mod n = w mod n
(1 + w) mod n = w mod n

Additive inverse (-w)

For each w Z_{z such that w + z 0 mod There is one peculiarity of modular arithmetic that sets it apart from ordinary arithmetic. First, observe that, as in ordinary arithmetic, we can write the following:}

Equation 4-2

(5 + 23) (5 + 7)(mod 8}; 23 7 (mod 8)

[Page 106]

Equation (4.2) is consistent with the existence of an additive inverse. Adding the additive inverse of a to both sides of Equation (4.2), we have:

((a) + a + b) ((a + c)(mod n)

b n)

However, the following statement is true only with the attached condition:

Equation 4-3

where the term relatively prime is defined as follows: two integers are relatively prime if their only common positive integer factor is 1. Similar to the case of Equation (4.2), we can say that Equation (4.3) is consistent with the existence of a multiplicative inverse. Applying the multiplicative inverse of a to both sides of Equation (4.2), we have:

((a¹)ab) ((ac)(mod n)

b n)

To see this, consider an example in which the condition of Equation (4.3) does not hold. The integers 6 and 8 are not relatively prime, since they have the common factor 2. We have the following:

6 x 3 = 18 2 (mod 8)

6 x 7 = 42 2 (mod 8)

Yet 3 7 (mod 8).

The reason for this strange result is that for any general modulus n, a multiplier a that is applied in turn to the integers 0 through (n 1) will fail to produce a complete set of residues if a and n have any factors in common.

With a = 6 and n = 8,

Z₈	1	2	3	4	5	6	7
Multiply by 6	6	12	18	24	30	36	42
Residues	6	4	2	0	6	4	2

Because we do not have a complete set of residues when multiplying by 6, more than one integer in Z₈ maps into the same residue. Specifically, 6 x 0 mod 8 = 6 x 4 mod 8; 6 x 1 mod 8 = 6 x 5 mod 8; and so on. Because this is a many-to-one mapping, there is not a unique inverse to the multiply operation.

However, if we take a = 5 and n = 8, whose only common factor is 1,

Z₈	1	2	3	4	5	6	7
Multiply by 6	5	10	15	20	25	30	35
Residues	5	2	7	4	1	6	3

The line of residues contains all the integers in Z₈, in a different order.

[Page 107]

In general, an integer has a multiplicative inverse in Z_n if that integer is relatively prime to n. Table 4.1c shows that the integers 1, 3, 5, and 7 have a multiplicative inverse in Z₈, but 2, 4, and 6 do not.

Table of content