Chapter 9a: Introduction to Modular Arithmetic PDF

CHAPTER 9. Mathematical System– Introduction to Modular Arithmetic Core Idea “Mathematics creates connections and fosters efficiency through visual tools like graphs and algorithms.” learning objectives 1...

CHAPTER 9. Mathematical System– Introduction to Modular Arithmetic Core Idea “Mathematics creates connections and fosters efficiency through visual tools like graphs and algorithms.” learning objectives 1. perform clock arithmetic; 2. describe modulus and congruence; 3. verify different modular congruence; 4. perform addition and subtraction modulo 𝑛; and 5. calculate time or day using modulo. challenge… It’s Your BirthDAY TUESDAY MONDAY WEDNESDAY What day of the week where you born? THURSDAY FRIDAY SATURDAY SUNDAY MODULAR ARITHMETIC is also called as “clock arithmetic”. In real life, this idea can also be used to deal with “time” in terms of a 12-hour clock. MODULAR ARITHMETIC Addition on a 12-hour clock Notation: ⊕ 1. What is 8 hours after 3 o’clock? 3 8 = 11 o’ clock MODULAR ARITHMETIC Addition on a 12-hour clock Notation: ⊕ 2. What is 8 hours after 9 o’clock? 9 8 = 5 o’ clock MODULAR ARITHMETIC Subtraction on a 12-hour clock Notation: ⊝ 3. If the time now is 3 o’clock, what is the time 7 hours ago? 3 ⊝ 7 = 8 o’ clock MODULAR ARITHMETIC Subtraction on a 12-hour clock Notation: ⊝ 4. What is 7 hours before 10 o’clock? 10 ⊝ 7 = 3 o’ clock MODULAR ARITHMETIC Evaluate each of the following, where ⊕ and ⊝ indicate addition and subtraction, respectively, on a 12-hour clock. 1. 8 7 = 3 o’ clock 2. 7 12 = 7 o’ clock 3. 8 ⊝ 11 = 9 o’ clock 4. 2 ⊝ 8 = 6 o’ clock MODULO n Two integers 𝒂 and 𝒃 are said to be congruent modulo 𝒏 , where 𝑛 is a 𝒂−𝒃 natural number, if is an integer. In this case, we write 𝒂 ≡ 𝒏 𝒃 𝐦𝐨𝐝 𝒏. The number 𝒏 is called the modulus. The statement 𝒂 ≡ 𝒃 𝐦𝐨𝐝 𝒏 is called a congruence. Determine whether the following congruence is true. 1. 29 ≡ 8 mod 3 3. 7 ≡ 12 mod 5 2. 15 ≡ 4 mod 6 4. 15 ≡ 1 mod 8 MODULO n Days of the Week Consider a day-of-the-week arithmetic. Monday = 1 Friday = 5 Suppose each day is associated with a Tuesday = 2 Saturday = 6 number as shown on the right. Wednesday = 3 Sunday = 7 Thursday = 4 1. What is 6 days after Friday? 5 6 = 11 − 7 = 4 Hence, 6 days after Friday is Thursday. 2. What is 16 days after Monday? 1 16 → 1 + 16 ≡ ___ mod 7 2 7 17 17 ≡ ___ mod 7 14 17 ≡ 𝟑 mod 7 3 Hence, 16 days after Monday is Wednesday. MODULO n Days of the Week Consider a day-of-the-week arithmetic. Monday = 1 Friday = 5 Suppose each day is associated with a Tuesday = 2 Saturday = 6 number as shown on the right. Wednesday = 3 Sunday = 7 Thursday = 4 3. If today is Friday, what day is it 16 days from now? 5 16 → 5 + 16 ≡ ___ mod 7 3 7 21 21 ≡ ___ mod 7 21 17 ≡ 0 or 7 mod 7 0 If there is no remainder, let the answer be equal to the value of the modulus 𝒏. Hence, 16 days after Friday is Sunday. MODULO n Days of the Week Consider a day-of-the-week arithmetic. Monday = 1 Friday = 5 Suppose each day is associated with a Tuesday = 2 Saturday = 6 number as shown on the right. Wednesday = 3 Sunday – 7 Thursday = 4 1. If July 4, 2010 was a Sunday, what day of the week is July 4, 2015? 261 7 1833 2010 ↔ 2015 = 5 years 7 + 1826 ≡ ___ mod 7 1827 1 leap year → 2012 6 1833 ≡ 𝟔 mod 7 Total number of days: 5(365) +1 = 1826 Hence, July 4, 2015 is Saturday. MODULO n Days of the Week Monday = 1 Friday = 5 Consider a day-of-the-week arithmetic. Tuesday = 2 Saturday = 6 Suppose each day is associated with a number as shown on the right. Wednesday = 3 Sunday = 7 Thursday = 4 2. In 2008, Abraham Lincoln’s birthday fell on Tuesday, February 12. On what day of the week does Lincoln’s birthday fall in 2017? 470 2008↔ 2017 = 9 years 7 3290 3 leap years → 2008,2012,2016 2 + 3,288 ≡ ___ mod 7 3290 0 Total number of days: 3,290 ≡ 0 𝑜𝑟 7 mod 7 9(365) +3 = 3,288 Hence, February 12, 2017 is Sunday. ARITHMETIC OPERATIONS MODULO n Addition Modulo 𝒏 Evaluate the following: 1. (23 + 38) mod 12 2. (51 + 72) mod 3 ARITHMETIC OPERATIONS MODULO n Subtraction Modulo 𝒏 Evaluate the following: 1. (33 – 16) mod 6 2. (14 – 27) mod 5 Find the value of 𝑥. 3. 37 – 13 ≡ 𝑥 mod 15 4. 21 – 43 ≡ 𝑥 mod 7 5. 9 – 100 ≡ 𝑥 mod 12 CALCULATING DAYS AND TIME 1. If today is Tuesday, what day of the week will it be 93 days from now? 2. Disregarding A.M. or P.M., if it is 10 o’clock now, what time will it be 500 hours after? 3. If today is Thursday, what day of the week will it be 100 days from now? End of Discussion…