Properties of Modular Arithmetic

Properties of Modular Arithmetic

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

Zn = {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 r (mod 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 Zn, there exists a z such that w + z 0 mod n

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)

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) + a + c)(mod n)

b c (mod 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) ((a¹)ac)(mod n)

b c (mod 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,   Z8 0 1 2 3 4 5 6 7   Multiply by 6 0 6 12 18 24 30 36 42   Residues 0 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 Z8 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,   Z8 0 1 2 3 4 5 6 7   Multiply by 6 0 5 10 15 20 25 30 35   Residues 0 5 2 7 4 1 6 3 The line of residues contains all the integers in Z8, in a different order.