9.3 Modular Arithmetic 561 A second method can be used to determine the sum of 4 6 + in modulo 7. We add 4 and 6 to get the number 10. Next, divide 10 by 7 and observe the remainder. 10 7 1, remainder 3 ÷ = Therefore, the sum 4 6 + is 3 in a modulo 7 arithmetic system. We say that 10 is congruent to 3 in modulo 7. The concept of congruence is important in modular arithmetic. Definition: Congruent a is congruent to b modulo m, written, a b m (mod ), ≡ if a and b have the same remainder when divided by m. For example, continuing to work with a modulo 7 system, we have the following. 10 7 1, remainder 3 and 3 7 0, remainder 3 ÷ = ÷ = Since the remainders are the same, 3 in each case, 10 is congruent to 3 modulo 7, and we write 10 3 (mod 7). ≡ Other whole numbers that are congruent to 3 in modulo 7, are 17, 24, 31, 38, 45, and so on. Each of these numbers, when divided by 7, has a remainder of 3. If we were to place all of the numbers that are congruent to 3 in modulo 7 into a set, it would be {3, 10, 17, 24, 31, 38, 45, }. … We refer to this set as a modulo class and we say that 3 is the representative of this class. If we continue dividing other whole numbers by 7, we see that the remainder must always be one of the numbers 0, 1, 2, 3, 4, 5, or 6. Each of these remainders is a representative of a modulo class. Table 9.12 shows us the modulo 7 classes. The top row shows the representatives 0 through 6 and that every whole number is congruent to one of the representatives. The solution to a problem in modular arithmetic, if it exists, will always be a number from 0 through m 1, − where m is the modulus of the system. For example, in a modulo 7 system, because 7 is the modulus, the solution will be a number from 0 through 6. Table 9.12 Modulo 7 Classes 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 9 10111213 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 Example 1 Congruence in Modulo 7 Determine which number, 0 through 6, the following numbers are equivalent to in modulo 7. a) 44 b) 91 c) 165 Solution Although we could determine the answers by listing more entries in Table 9.12, this method becomes impractical with larger numbers. We will divide the given number by 7 and observe the remainder. a) To determine the number 44 is equivalent to in mod 7, we divide 44 by 7 and observe the remainder. ) ← 6 7 44 42 2 remainder 44 7 6, ÷ = remainder 2 Therefore, 44 is congruent to 2 in mod 7. We write 44 2 (mod7). ≡ b) Divide 91 by 7 and observe the remainder. ÷ = 91 7 13, remainder 0 Thus, 91 0 (mod7). ≡
RkJQdWJsaXNoZXIy NjM5ODQ=