560 CHAPTER 9 Mathematical Systems If your birthday is on a Monday this year, on what day of the week will it fall next year? What if next year is a leap year? When will your birthday next fall on a Saturday? These questions can be addressed with the type of arithmetic that we will study in this section. Modular Arithmetic SECTION 9.3 LEARNING GOALS Upon completion of this section, you will be able to: 7 Solve problems involving modulo m systems. 7 Determine whether a mathematical system defined by a modulo m system is a commutative group. Why This Is Important Modular arithmetic is a fundamental part of many branches of mathematics. A wide variety of applications of modular arithmetic can be found in cryptography (the study of writing in secret codes), computer science, chemistry, music, and economics. Modulo m Systems Recall the mathematical system of clock arithmetic that we studied in Section 9.2. If we were to replace the number 12 with the number 0, the elements in the system could be rewritten as {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. This set together with the operation of addition forms a modulo 12 or a mod 12 arithmetic system. In this section we will study such mathematical systems. A modulo m system consists of a set of m elements, … − m {0, 1, 2, 3, , 1}, and a binary operation. In a modulo m system, we refer to m as the modulus. To help explain how modulo m systems work, consider the following question: If today is Sunday, what day of the week will it be in 23 days? The answer, Tuesday, is arrived at by dividing 23 by 7. The quotient is 3 and the remainder is 2. Twenty-three days represent 3 weeks plus 2 days. Since we are interested only in the day of the week on which the twenty-third day will fall, the 3-week segment is unimportant to the answer. The remainder of 2 indicates the answer will be 2 days later than Sunday, which is Tuesday. If we place the days of the week on a clock face as shown in Fig. 9.3, then, starting on Sunday, in 23 days the hand would have made three complete revolutions and end on Tuesday. If we replace the days of the week with numbers, then a modulo 7 arithmetic system will result. See Fig. 9.4: Sunday 0, Monday 1, Tuesday 2, = = = and so on. If we start at 0 and move the hand 23 places, we will end at 2. Sun Sat Fri Thu Wed Tue Mon Figure 9.3 1 2 3 4 5 6 0 Figure 9.4 When working with a modulo m system it is often desirable to construct a table, similar to the ones used in Section 9.2. A modulo 7 addition table is shown in Table 9.11. Suppose we wish to calculate 4 6 + in modulo 7. Consider the clock shown in Fig. 9.5. If we start at 4 and count clockwise 6 hours we end at 3. This number is circled in Table 9.11. The other numbers in Table 9.11 can be obtained in a similar manner. Table 9.11 Modular 7 Addition + 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5 1 2 3 4 5 6 0 Figure 9.5 Shutterstock
RkJQdWJsaXNoZXIy NjM5ODQ=