Modular Arithmetic

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 x is the largest integer less than or equal to x.

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 a and (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.

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.
• If 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₁.

So

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), then n|a.

Properties of Congruences

Congruences have the following properties:

1. a b (mod n) if n|(a b).
2. a b (mod n) implies b a (mod n)..
3. a b (mod n) and b c (mod n) imply a c (mod 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:

1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
2. [(a mod n) (b mod n)] mod n = (a b) mod n
3. [(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 117 mod 13, we can proceed as follows:
112 = 121 4 (mod 13)
114 = (112)2 42 3 (mod 13)
117 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.