Modular arithmetic Secondary Mathematics Masterclass Gustavo Lau Introduction On what day were you born? Worksheet 1 Going round in circles Modulo 12 How to represent time? t 0 1 2 3 6 9 12 12 t 9 3 6 Modulo 12 Instead of 13 = 1, in modular arithmetic we write 13 ≡ 1 (mod 12) and read it “13 is congruent to 1 modulo 12” or, to abbreviate, “13 is 1 modulo 12”. Examples: 12 ≡ 0 (mod 12) 17 ≡ 5 (mod 12) 37 ≡ 1 (mod 12) -1 ≡ 11 (mod 12) In general, a ≡ b (mod n) if a-b is a multiple of n. Equivalently, a ≡ b (mod n) if a and b have the same remainder when divided by n (remainder modulo n). Clock addition table + 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 Modulo 12 In modular arithmetic we use the numbers 0-11 instead of the numbers 1-12. The reason is that 0-11 are the remainders modulo 12. In general, when we work modulo n we replace all the numbers by their remainders modulo n. Modulo 12 addition table + 0 1 2 3 4 5 6 7 8 9 10 11 0 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 3 4 5 6 7 8 9 10 11 0 2 2 3 4 5 6 7 8 9 10 11 0 1 3 3 4 5 6 7 8 9 10 11 0 1 2 4 4 5 6 7 8 9 10 11 0 1 2 3 5 5 6 7 8 9 10 11 0 1 2 3 4 6 6 7 8 9 10 11 0 1 2 3 4 5 7 7 8 9 10 11 0 1 2 3 4 5 6 8 8 9 10 11 0 1 2 3 4 5 6 7 9 9 10 11 0 1 2 3 4 5 6 7 8 10 10 11 0 1 2 3 4 5 6 7 8 9 11 11 0 1 2 3 4 5 6 7 8 9 10 Examples: 7 + 8 ≡ 3 (mod 12) 10 + 2 ≡ 0 (mod 12) 13 + 2 ≡ 3 (mod 12) -1 + 14 ≡ 1 (mod 12) Modulo 12 Can we use arithmetic modulo 12 to represent something else?