Modular Arithmetic: Symbols PDF

Modular Arithmetic Zodiac Cycles, Digital Time, etc. Jonathan Caalim, PhD 1 Chinese Zodiac Cycle The Chinese zodiac cycle (or shengxiao 生肖) follows a twelve-year cycle, each year associated with a specific animal sign. 0. Monkey 3. Pig...

Modular Arithmetic Zodiac Cycles, Digital Time, etc. Jonathan Caalim, PhD 1 Chinese Zodiac Cycle The Chinese zodiac cycle (or shengxiao 生肖) follows a twelve-year cycle, each year associated with a specific animal sign. 0. Monkey 3. Pig 6. Tiger 9. Snake 1. Rooster 4. Rat 7. Rabbit 10. Horse 2. Dog 5. Ox 8. Dragon 11. Sheep 2 Chinese Zodiac Cycle The Chinese zodiac cycle (or shengxiao 生肖) follows a twelve-year cycle, each year associated with a specific animal sign. 0. Monkey 3. Pig 6. Tiger 9. Snake 1. Rooster 4. Rat 7. Rabbit 10. Horse 2. Dog 5. Ox 8. Dragon 11. Sheep To get the zodiac animal for this year, divide 2024 by 12 to get the quotient 168 and remainder 8. So, 2024 is a Year of the Drag-on. 2 Chinese Zodiac Cycle The Chinese zodiac cycle (or shengxiao 生肖) follows a twelve-year cycle, each year associated with a specific animal sign. 0. Monkey 3. Pig 6. Tiger 9. Snake 1. Rooster 4. Rat 7. Rabbit 10. Horse 2. Dog 5. Ox 8. Dragon 11. Sheep To get the zodiac animal for this year, divide 2024 by 12 to get the quotient 168 and remainder 8. So, 2024 is a Year of the Drag-on. 2 Chinese Zodiac To get your own Chinese zodiac animal sign, divide your birth year by 12. The remainder gives your sign. You can also refer to a Chinese zodiac wheel. 3 Clock Arithmetic If you go to bed at 11:00 PM and aim for 10 hours of sleep, what time should you set your alarm clock? 4 Clock Arithmetic If you go to bed at 11:00 PM and aim for 10 hours of sleep, what time should you set your alarm clock? 11+10 = 21 When 21 is divided by 12, the remainder is 9. The answer is 9:00 AM. 4 Partition of Z according to remainders We can partition the integers into disjoint sets according to their remainder when divided by a certain divisor. 5 Partition of Z according to remainders We can partition the integers into disjoint sets according to their remainder when divided by a certain divisor. For example, if the divisor is 3, there are three possible remainders: 0, 1, and 2. 5 Partition of Z according to remainders We can partition the integers into disjoint sets according to their remainder when divided by a certain divisor. For example, if the divisor is 3, there are three possible remainders: 0, 1, and 2. remainder 0: {... , −6, −3, 0, 3, 6, 9, 12,... } 5 Partition of Z according to remainders We can partition the integers into disjoint sets according to their remainder when divided by a certain divisor. For example, if the divisor is 3, there are three possible remainders: 0, 1, and 2. remainder 0: {... , −6, −3, 0, 3, 6, 9, 12,... } remainder 1: {... , −5, −2, 1, 4, 7, 10, 13,... } 5 Partition of Z according to remainders We can partition the integers into disjoint sets according to their remainder when divided by a certain divisor. For example, if the divisor is 3, there are three possible remainders: 0, 1, and 2. remainder 0: {... , −6, −3, 0, 3, 6, 9, 12,... } remainder 1: {... , −5, −2, 1, 4, 7, 10, 13,... } remainder 2: {... , −4, −1, 2, 5, 8, 11, 14,... } 5 Partition of Z according to remainders We can partition the integers into disjoint sets according to their remainder when divided by a certain divisor. For example, if the divisor is 3, there are three possible remainders: 0, 1, and 2. remainder 0: {... , −6, −3, 0, 3, 6, 9, 12,... } remainder 1: {... , −5, −2, 1, 4, 7, 10, 13,... } remainder 2: {... , −4, −1, 2, 5, 8, 11, 14,... } Remark: Any two elements in a set have the same remainder. 5 Partition of Z according to remainders We can partition the integers into disjoint sets according to their remainder when divided by a certain divisor. For example, if the divisor is 3, there are three possible remainders: 0, 1, and 2. remainder 0: {... , −6, −3, 0, 3, 6, 9, 12,... } remainder 1: {... , −5, −2, 1, 4, 7, 10, 13,... } remainder 2: {... , −4, −1, 2, 5, 8, 11, 14,... } Remark: Any two elements in a set have the same remainder. Question: Which set contains 25? 5 Congruence Modulo m Fix a positive integer m (called the modulus). For integers a and b, we say that a and b are congruent modulo m if 6 Congruence Modulo m Fix a positive integer m (called the modulus). For integers a and b, we say that a and b are congruent modulo m if a − b is divisible by m 6 Congruence Modulo m Fix a positive integer m (called the modulus). For integers a and b, we say that a and b are congruent modulo m if a − b is divisible by m equivalently, a and b have the same remainder when divided by m 6 Congruence Modulo m Fix a positive integer m (called the modulus). For integers a and b, we say that a and b are congruent modulo m if a − b is divisible by m equivalently, a and b have the same remainder when divided by m We write a ≡ b (mod m). 6 Congruence Modulo m Fix a positive integer m (called the modulus). For integers a and b, we say that a and b are congruent modulo m if a − b is divisible by m equivalently, a and b have the same remainder when divided by m We write a ≡ b (mod m). Example: 8 and 22 have the same remainder (= 1) when divided by 7, so 8 ≡ 22 (mod 7) 22 ≡ 8 (mod 7) 6 Example 29 ≡ 8 (mod 3) because 29 − 8 = 21 is divisible by 3 The remainder when 29 is divided by 3 is 2. This is also the remainder when 8 is divided by 3. 7 Exercise: 1. Is 30 ≡ 11 (mod 3)? 4. Is 12 ≡ 24 (mod 6)? 2. Is −6 ≡ 5 (mod 2)? 5. Is 13 ≡ 13 (mod 7)? 3. Is 18 ≡ −7 (mod 5)? 6. Is −10 ≡ −32 (mod 4)? 8 Example: Odd vs Even If x is an odd integer (e.g. −5, −3, −1, 1, 3, 5, 7), then x ≡1 (mod 2). 9 Example: Odd vs Even If x is an odd integer (e.g. −5, −3, −1, 1, 3, 5, 7), then x ≡1 (mod 2). If y is an even integer (e.g. −4, −2, 0, 2, 4, 6), then y ≡0 (mod 2). 9 Odd-Even Arithmetic Observe that 1. Odd + Odd = Even 2. Odd + Even = Odd 3. Even + Odd = Odd 4. Even + Even = Even 10 Odd-Even Arithmetic Observe that 1. Odd + Odd = Even 2. Odd + Even = Odd 3. Even + Odd = Odd 4. Even + Even = Even In modular notation, we write 1. 1 ⊕ 1 ≡ 0 (mod 2) 10 Odd-Even Arithmetic Observe that 1. Odd + Odd = Even 2. Odd + Even = Odd 3. Even + Odd = Odd 4. Even + Even = Even In modular notation, we write 1. 1 ⊕ 1 ≡ 0 (mod 2) 2. 1 ⊕ 0 ≡ 1 (mod 2) 10 Odd-Even Arithmetic Observe that 1. Odd + Odd = Even 2. Odd + Even = Odd 3. Even + Odd = Odd 4. Even + Even = Even In modular notation, we write 1. 1 ⊕ 1 ≡ 0 (mod 2) 2. 1 ⊕ 0 ≡ 1 (mod 2) 3. 0 ⊕ 1 ≡ 1 (mod 2) 10 Odd-Even Arithmetic Observe that 1. Odd + Odd = Even 2. Odd + Even = Odd 3. Even + Odd = Odd 4. Even + Even = Even In modular notation, we write 1. 1 ⊕ 1 ≡ 0 (mod 2) 2. 1 ⊕ 0 ≡ 1 (mod 2) 3. 0 ⊕ 1 ≡ 1 (mod 2) 4. 0 ⊕ 0 ≡ 0 (mod 2) 10 Odd-Even Arithmetic 1. Odd x Odd = Odd 2. Odd x Even = Even 3. Even x Odd = Even 4. Even x Even = Even 11 Odd-Even Arithmetic 1. Odd x Odd = Odd 2. Odd x Even = Even 3. Even x Odd = Even 4. Even x Even = Even In modular notation, we write 1. 1 ⊗ 1 ≡ 1 (mod 2) 11 Odd-Even Arithmetic 1. Odd x Odd = Odd 2. Odd x Even = Even 3. Even x Odd = Even 4. Even x Even = Even In modular notation, we write 1. 1 ⊗ 1 ≡ 1 (mod 2) 2. 1 ⊗ 0 ≡ 0 (mod 2) 11 Odd-Even Arithmetic 1. Odd x Odd = Odd 2. Odd x Even = Even 3. Even x Odd = Even 4. Even x Even = Even In modular notation, we write 1. 1 ⊗ 1 ≡ 1 (mod 2) 2. 1 ⊗ 0 ≡ 0 (mod 2) 3. 0 ⊗ 1 ≡ 0 (mod 2) 11 Odd-Even Arithmetic 1. Odd x Odd = Odd 2. Odd x Even = Even 3. Even x Odd = Even 4. Even x Even = Even In modular notation, we write 1. 1 ⊗ 1 ≡ 1 (mod 2) 2. 1 ⊗ 0 ≡ 0 (mod 2) 3. 0 ⊗ 1 ≡ 0 (mod 2) 4. 0 ⊗ 0 ≡ 0 (mod 2) 11 Modular Number System For a fixed modulus m, we set Zm := {0, 1, 2,... , m − 1}. The elements of Zm are the possible remainders when a number is divided by m. We define two operations on Zm. Addition modulo m: a⊕b ≡a+b (mod m) Multiplication modulo m: a⊗b ≡a·b (mod m) 12 Examples 8 ⊕ 7 ≡ 15 (mod 9) ≡ 6 (mod 9). In other words, in Z9 , when we add 8 and 7, we get 6. 8 ⊗ 7 ≡ 56 (mod 9) ≡ 2 (mod 9). In other words, in Z9 , when we multiply 8 and 7, we get 2. 13 Z2 When the modulus m = 2, we have Z2 = {0, 1}. The number 0 represents the even numbers and 1 represents the odd numbers. We have the following tables for addition and multiplication. ⊕ 0 1 ⊗ 0 1 0 0 1 0 0 0 1 1 0 1 0 1 14 Z3 When the modulus m = 3, we have Z3 = {0, 1, 2}. We have the following tables for addition and multiplication. ⊕ 0 1 2 ⊗ 0 1 2 0 0 1 2 0 0 0 0 1 1 2 0 1 0 1 2 2 2 0 1 2 0 2 1 15 Z4 When the modulus m = 4, we have Z4 = {0, 1, 2, 3}. We have the following tables for addition and multiplication. ⊕ 0 1 2 3 ⊗ 0 1 2 3 0 0 1 2 3 0 0 0 0 0 1 1 2 3 0 1 0 1 2 3 2 2 3 0 1 2 0 2 0 2 3 3 0 1 2 3 0 3 2 1 16 Caesar Cipher In Caesar cipher, each letter in a plain text is replaced by a letter by some fixed number down the alphabet. This encryption technique is named after Julius Caesar who used this in his private correspondence. 17 Generalized Caesar Cipher A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25 0 Let Z26 = {0, 1, 2,... , 23, 24, 25}. We will devise a simple encoding and decoding scheme using modular arithmetic. 18 Encryption In cryptography, encryption is the process of transforming the original representation of an information, known as plaintext, into an alternative (or secret) form known as ciphertext. Let us encode the secret message MATH. We will use an encoding formula, say y ≡ 3x + 2 (mod 26). 19 M = 13 Using the formula y ≡ 3x + 2 (mod 26), we get y = 3x + 2 (mod 26) = 3(13) + 2 (mod 26) = 41 (mod 26) = 15 (mod 26) So, M is encoded as the 15th letter O. 20 A=1 y = 3x + 2 (mod 26) = 3(1) + 2 (mod 26) = 5 (mod 26) So, A is encoded as the 5th letter E. 21 T = 20 y = 3x + 2 (mod 26) = 3(20) + 2 (mod 26) = 62 (mod 26) = 10 (mod 26) So, A is encoded as the 10th letter J. 22 H =8 y = 3x + 2 (mod 26) = 3(8) + 2 (mod 26) = 26 (mod 26) = 0 (mod 26) So, A is encoded as Z. So, MATH is encoded as OEJZ. 23 Decryption How does the receiver of the message OEJZ transform it back to its original form? We need to get the inverse of the line y = 3x + 2. Step 1: Interchange x and y. We get x = 3y + 2. Step 2: Solve for y. x = 3y + 2 x − 2 = 3y 1 y = (x − 2). 3 24 Inverses in Z26 x 1 3 5 7 9 11 15 17 19 21 23 25 1 x 1 9 21 15 3 19 7 23 11 5 17 25 1 Thus, in Z26 , the number 3 is the same as 9. So, 1 y = (x − 2) 3 is the same as y ≡ 9(x − 2) (mod 26) 25 O = 15 Using the formula 9(x − 2) (mod 26), we get y = 9(x − 2) (mod 26) = 9(15 − 2) (mod 26) = 9(13) (mod 26) = 117 (mod 26) = 13 (mod 26) So, 0 is decoded as the 13th letter M. 26 E =5 y = 9(x − 2) (mod 26) = 9(5 − 2) (mod 26) = 9(3) (mod 26) = 27 (mod 26) = 1 (mod 26) So, 0 is decoded as the 1st letter A. 27 J = 10 y = 9(x − 2) (mod 26) = 9(10 − 2) (mod 26) = 9(8) (mod 26) = 72 (mod 26) = 20 (mod 26) So, J is decoded as the 20th letter T. 28 Z =0 y = 9(x − 2) (mod 26) = 9(0 − 2) (mod 26) = 9(−2) (mod 26) = −18 (mod 26) = 8 (mod 26) So, Z is decoded as the 8th letter H. Therefore, the secret message OEJZ means MATH. 29