Number Theory Fall 2023-2024 Lecture Notes (PDF)

Number Theory Fall 2023-2024 Dr. Lama Affara Last Lecture Number Theory Modular Divisibility Primes Arithmetic Congruence De...

Number Theory Fall 2023-2024 Dr. Lama Affara Last Lecture Number Theory Modular Divisibility Primes Arithmetic Congruence Definition and Modulo Relation properties Properties of Congruence GCD and LCM Modulo Arithmetic Euclidean Modulo 𝑚 Algorithm The Division Algorithm 𝑏 ÷ 𝑎 = 𝑞 with remainder 𝑟 𝑏 is an integer 𝑎 is a positive integer there exists unique integers 𝑞 and 𝑟, with 0 ≤ 𝑟 < 𝑎, such that 𝑏 = 𝑞𝑎 + 𝑟 Quotient 𝑞 = 𝑏 𝒅𝒊𝒗 𝑎 Remainder 𝑟 = 𝑏 𝒎𝒐𝒅 𝑎 12/4/2023 Discrete Structures II 3 Divisibility b ÷ 𝑎 = 𝑞 with remainder 0 𝑎 is an integer where 𝒂 ≠ 𝟎 𝑏 is an integer there exists an integer 𝑞 such that 𝑏 = 𝑎𝑞 ➔ 𝑎 divides 𝑏 denoted as 𝑎|𝑏 We write 𝑎 ∤ 𝑏 when a does not divide b 12/4/2023 Discrete Structures II 4 Properties of Divisibility Theorem 1 Let 𝑎, 𝑏, and 𝑐 be integers, where 𝑎 ≠ 0 i. If 𝑎 | 𝑏 and 𝑎 | 𝑐, then 𝒂 | (𝒃 + 𝒄) ii. If 𝑎 | 𝑏, then 𝒂 | 𝒃𝒄 for all integers 𝑐 iii. If 𝑎 | 𝑏 and 𝑏 | 𝑐, then 𝒂 | 𝒄 Congruence Relation Notice (𝑚𝑜𝑑 m) here refers to the notation of the relation 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚) Notice 𝒎𝒐𝒅 here refers to the modulus operator 𝑎 and 𝑏 are integers 𝑎 is congruent to 𝑏 modulo 𝑚 𝑚 is a positive integer 𝑎 𝒎𝒐𝒅 𝑚 = 𝑏 𝒎𝒐𝒅 𝑚 𝑎 and 𝑏 have the same remainder 𝑚 divides 𝑎 – 𝑏 when divided by 𝑚 If a is not congruent to b modulo m, we write 𝑎 ≢ 𝑏 (𝑚𝑜𝑑 𝑚) Algebraic Manipulation of Congruences Thus, By theorem 4, 𝑎 + 𝑏 ≡ (𝑎 𝒎𝒐𝒅 𝑚) + 𝑏 𝒎𝒐𝒅 𝑚 (𝑚𝑜𝑑 𝑚) 𝑎𝑏 ≡ (𝑎 𝒎𝒐𝒅 𝑚)(𝑏 𝒎𝒐𝒅 𝑚) (𝑚𝑜𝑑 𝑚) Thus, (𝑎 + 𝑏) 𝒎𝒐𝒅 𝑚 = 𝑎 𝒎𝒐𝒅 𝑚 + 𝑏 𝒎𝒐𝒅 𝑚 𝒎𝒐𝒅 𝑚 𝑎𝑏 𝒎𝒐𝒅 𝑚 = 𝑎 𝒎𝒐𝒅 𝑚 𝑏 𝒎𝒐𝒅 𝑚 𝒎𝒐𝒅 𝑚 12/4/2023 Discrete Structures II 7 Arithmetic Modulo m Let Zm = {0, 1,... , m − 1} Addition modulo 𝑚: 𝑎 +𝑚 𝑏 = (𝑎 + 𝑏) 𝒎𝒐𝒅 𝑚 Multiplication modulo 𝑚: 𝑎.𝑚 𝑏 = (𝑎𝑏) 𝒎𝒐𝒅 𝑚 Finding GCD Using Prime Factorizations Suppose the prime factorizations of a and b are: where each exponent is a nonnegative integer, and where all primes occurring in either prime factorization are included in both. Then: Greatest Common Divisor The integers 𝑎1 , 𝑎2 , … , 𝑎𝑛 are pairwise relatively prime if gcd(𝑎𝑖 , 𝑎𝑗 ) = 1 whenever 1 ≤ 𝑖 < 𝑗 ≤ 𝑛. 77 7 11 77 Finding LCM Using Prime Factorizations Suppose the prime factorizations of a and b are: where each exponent is a nonnegative integer, and where all primes occurring in either prime factorization are included in both. Then: Euclidean Algorithm The Euclidian algorithm is an efficient method for computing the greatest common divisor of two integers. Let r = gcd(a,b) so, r|a and r|b Let c = a mod b, so r|c If a and b have a common divisor, then the remainder of their division have the same divisor Thus gcd(a,b) = gcd(b,c) = gcd(a,c) Today’s Lecture Number Theory Solving Primes congruences gcd as linear Linear combinations Congruences Extended Chinese Euclidean Remainder Algorithm Theorem Fermat’s Little Theorem GCDs as Linear Combinations Bezout’s Theorem If a and b are positive integers, then there exist integers s and t such that gcd(a,b) = sa + tb. This is a linear combination with integer coefficients of a and b. s and t are called Bézout coefficients of a and b. The equation gcd(a,b) = sa + tb is called Bézout’s identity. Let’s Solve Write the gcd of 𝑎 = 6 and 𝑏 = 14 using linear combination of 𝑎 and 𝑏 i.e. What are integers 𝑠 and 𝑡 such that gcd(6,14) = 6(𝑠) + 14(𝑡)? gcd(6,14) = 2 = 6(−2) + 14(1) So 𝑠 = −2 and 𝑡 = 1 12/4/2023 Discrete Structures II 15 GCDs as Linear Combinations How to compute The Bézout coefficients? 1. Use the Euclidian algorithm to find the gcd 2. work backwards (by division and substitution) to express the gcd as a linear combination of the original two integers. 12/4/2023 Discrete Structures II 16 Let’s Solve Write the gcd of 𝑎 = 252 and 𝑏 = 198 using linear combination of 𝑎 and 𝑏 1. Euclidean Algorithm 2. Working Backward 252 = 198 (1) + 54 18 = 54 (1) - 36 198 = 54 (3) + 36 = 54(1) - (198 – 54(3)) = 198(-1) + 54(4) 54 = 36 (1) + 18 = 198(-1) + 4(252– 198) = 252(4) + 198(-5) 36 = 18(2) + 0 So gcd(252,198)=18 So gcd(252,198)=252(4) + 198(-5) ➔ Extended Euclidean Algorithm 12/4/2023 Discrete Structures II 17 Dividing Congruences by an Integer Dividing both sides of a valid congruence by an integer does not always produce a valid congruence. But dividing by an integer relatively prime to the modulus does produce a valid congruence: Theorem Let 𝑚 be a positive integer and let 𝑎, 𝑏, and 𝑐 be integers. If 𝑎𝑐 ≡ 𝑏𝑐 (𝑚𝑜𝑑 𝑚) and gcd(𝑐, 𝑚) = 1, then 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚). Today’s Lecture Number Theory Solving Primes congruences gcd as linear Linear combinations Congruences Extended Chinese Euclidean Remainder Algorith Theorem Fermat’s Little Theorem Linear Congruence Just as solving linear equations plays an important role in calculus and linear algebra, linear congruence is an essential task in number theory 𝑎𝑥 ≡ 𝑏 𝑚𝑜𝑑 𝑚 𝑚 is a positive integer 𝑎, 𝑏 are integers 𝑥 is a variable Solving Linear Congruence Solving linear congruence ➔ Finding all 𝑥 that satisfy below equation 𝑎𝑥 ≡ 𝑏 𝑚𝑜𝑑 𝑚 Can we divide by 𝑎 to find 𝑥? No! Congruence is not close under division. We can multiply by a number that cancels out 𝑎 (if exists) ➔ inverse modulo ā: Integer ā such that ā𝑎 ≡ 1( 𝑚𝑜𝑑 𝑚) Inverse Modulo Theorem If 𝑎 and 𝑚 are relatively prime integers, then a unique inverse of 𝑎 modulo 𝑚 exists. Proof: 𝑎 and 𝑚 are relatively prime gcd(𝑎, 𝑚) = 1 𝑠𝑎 + 𝑡𝑚 = 1 𝑠𝑎 + 𝑡𝑚 ≡ 1 (𝑚𝑜𝑑 𝑚) But, 𝑡𝑚 ≡ 0 (𝑚𝑜𝑑 𝑚) Then 𝑠𝑎 ≡ 1 (𝑚𝑜𝑑 𝑚) So 𝑠 is an inverse of 𝑎 modulo m 12/4/2023 Discrete Structures II 23 Let’s Solve! Find the inverse of 3 modulo 7 3 5 ≡ 1 (𝑚𝑜𝑑 7) So, 5 is the inverse of 3 modulo 7 Note that every integer congruent to 5 modulo 7 is also an inverse of 3, such as − 2,−9, 12, and so on. ➔ look for a multiple of 𝒂 that exceeds a multiple of 𝒎 by 1 12/4/2023 Discrete Structures II 24 Let’s Solve! Find the inverse of 8 modulo 15 8 2 ≡ 1 (𝑚𝑜𝑑 15) So, 2 is the inverse of 8 modulo 15 Note that every integer congruent to 2 modulo 15 is also an inverse of 8, such as -28,-13,17… 12/4/2023 Discrete Structures II 25 Let’s Solve Find the inverse of 101 modulo 4620 101 ≡ 1 (𝑚𝑜𝑑 4620) Not straightforward!! 12/4/2023 Discrete Structures II 26 Finding Inverses The Euclidean algorithm and Bézout coefficients gives us a systematic approaches to finding inverses. Using the Euclidian algorithm: 7 = 2∙3 + 1. 1 as linear combination: 3(−2) + 7(1) = 1, ➔ −2 and 1 are Bézout coefficients of 3 and 7. So, −2 is an inverse of 3 modulo 7. Let’s Solve Find an inverse of 101 modulo 4620. 1. Euclidean Algorithm 2. Working Backward 4620 = 101 (45) + 75 1 = 3 - 2(1) 101 = 75 (1) + 26 = 3- (23 – 3(7))=-23+8(3) 75 = 26 (2) + 23 = -23 + 8(26-23)=8(26)-9(23) 26 = 23(1) + 3 = 8(26)-9(75-26(2))=-9(75)+26(26) 23 = 3(7) + 2 = -9(75)+26(101-75)=26(101)-35(75) 3 = 2(1) + 1 = 26(101)-35(4620-101(45))=-35(4620)+1601(101) So gcd(4620,101)=1 So, 1601 is the inverse of 101 modulo 4620 12/4/2023 Discrete Structures II 28 Let’s Solve Find the inverse of 5 modulo 15 5 ≡ 1 (𝑚𝑜𝑑 15) 5 does not have any inverse modulo 15! 12/4/2023 Discrete Structures II 29 Using Inverses to Solve Congruences Solving linear congruence ➔ Finding all 𝑥 that satisfy below equation 𝑎𝑥 ≡ 𝑏 𝑚𝑜𝑑 𝑚 ➔ inverse modulo ā: Integer ā such that ā𝑎 ≡ 1( 𝑚𝑜𝑑 𝑚) solve the congruence 𝒂𝒙 ≡ 𝒃( 𝒎𝒐𝒅 𝒎) by multiplying both sides by ā. Let’s Solve! What are the solutions of the congruence 3𝑥 ≡ 4( 𝑚𝑜𝑑 7) We found that −2 is an inverse of 3 modulo 7. We multiply both sides of the congruence by −2 giving −2 ∙ 3𝑥 ≡ −2 ∙ 4(𝑚𝑜𝑑 7) So, if x is a solution, then 𝑥 ≡ −8 (𝑚𝑜𝑑 7) But, 6 ≡ -8 (mod 7). So x = 6 Verify: 3x ≡ 3 ∙ 6 = 18 ≡ 4( mod 7) which shows that all such x satisfy the congruence. ➔ The solutions are the integers x such that x ≡ 6 (mod 7), namely, 6,13,20 … and −1, − 8, − 15,… 12/4/2023 Discrete Structures II 31 System of Linear Congruences basis for a method that can be used to perform arithmetic with large integers can be found as word puzzles in the writings of ancient Chinese and Hindu mathematicians In the first century, the Chinese mathematician Sun-Tsu asked: There are certain things whose number is unknown. When divided by 3, the remainder is 2; when divided by 5, the remainder is 3; and when divided by 7, the remainder is 2. What will be the number of things? 12/4/2023 Discrete Structures II 32 The Chinese Remainder Theorem Let 𝑚1 , 𝑚2 , … , 𝑚𝑛 be pairwise relatively prime positive integers greater than one and 𝑎1 , 𝑎2 , … , 𝑎𝑛 arbitrary integers. Then the system 𝑥 ≡ 𝑎1 ( 𝑚𝑜𝑑 𝑚1 ) 𝑥 ≡ 𝑎2 ( 𝑚𝑜𝑑 𝑚2 ) ∙ ∙ ∙ 𝑥 ≡ 𝑎𝑛 ( 𝑚𝑜𝑑 𝑚𝑛 ) has a unique solution modulo 𝑚 = 𝑚1 𝑚2 ∙ ∙ ∙ 𝑚𝑛. The Chinese Remainder Theorem 𝑥 ≡ 𝑎1 ( 𝑚𝑜𝑑 𝑚1 ) 𝑥 ≡ 𝑎2 ( 𝑚𝑜𝑑 𝑚2 ) ∙ ∙ 𝑥 ≡ 𝑎𝑛 ( 𝑚𝑜𝑑 𝑚𝑛 ) 1. 𝑚 = 𝑚1 𝑚2 ∙ ∙ ∙ 𝑚𝑛 2. Let 𝑀𝑘 = 𝑚/𝑚𝑘 3. Find 𝑦𝑘 , an inverse of 𝑀𝑘 modulo 𝑚𝑘 , i.e. 𝑀𝑘 𝑦𝑘 ≡ 1 ( 𝑚𝑜𝑑 𝑚𝑘 ) 4. The sum 𝑥 = 𝑎1 𝑀1 𝑦1 + 𝑎2 𝑀2 𝑦2 + ∙ ∙ ∙ + 𝑎𝑛 𝑀𝑛 𝑦𝑛 Is the simultaneous solution for the system of linear congruences The Chinese Remainder Theorem 1. 𝑚 = 3 ∙ 5 ∙ 7 = 105 2. 𝑀1 = 𝑚/3 = 35, 𝑀2 = 𝑚/5 = 21, 𝑀3 = 𝑚/7 = 15. 3. Find 𝑦𝑘 , inverse of 𝑀𝑘 modulo 𝑚𝑘 2 is an inverse of 𝑀1 modulo 3 since 35 (2) ≡ 1 (mod 3) 1 is an inverse of 𝑀2 modulo 5 since 21 (1) ≡ 1 (mod 5) 1 is an inverse of 𝑀3 modulo 7 since 15(1) ≡ 1 (mod 7) 4. Hence, 𝑥 = 𝑎1 𝑀1 𝑦1 + 𝑎2 𝑀2 𝑦2 + 𝑎3𝑀3 𝑦3 = 2 ∙ 35 ∙ 2 + 3 ∙ 21 ∙ 1 + 2 ∙ 15 ∙ 1 = 233 ≡ 23 (𝑚𝑜𝑑 105) Then 23 is the smallest positive integer that is a simultaneous solution Fermat’s Little Theorem If 𝑝 is prime and 𝑎 is an integer not divisible by 𝑝, then 𝑎 𝑝−1 ≡ 1 (𝑚𝑜𝑑 𝑝) Furthermore, for every integer 𝑎 we have 𝑎𝑝 ≡ 𝑎 (𝑚𝑜𝑑 𝑝) ➔ Fermat’s little theorem is useful in computing the remainders modulo p of large powers of integers. Let’s Solve! Find 7222 mod 11. By Fermat’s little theorem, we know that 710 ≡ 1 (mod 11), so (710 )k ≡ 1 (mod 11), for every positive integer k. Therefore, ∙ 10 + 2 7222 = 7 22 = 710 2272 ≡ 1 22 ∙ 49 ≡ 5 𝑚𝑜𝑑 11 Hence, 7222 mod 11 = 5. Today’s Lecture Number Theory Solving Primes Cryptography congruences gcd as linear Linear Caesar Cipher combinations Congruences Extended Chinese Euclidean Remainder Shift Ciphers Algorith Theorem Fermat’s Little Affine Ciphers Theorem RSA Cryptosystem Cryptography transforming information so that it cannot be easily recovered without special knowledge Number theory is the basis of many classical ciphers, first used thousands of years ago used extensively until the 20th century ciphers encrypt messages by changing each letter to a different letter, or each block of letters to a different block of letters 12/4/2023 Discrete Structures II 40 Caesar Cipher Julius Caesar created secret messages shifting each letter three letters forward in the alphabet (sending the last three letters to the first three letters.) For example, the letter B is replaced by E and the letter X is replaced by A. Caesar Cipher Replace each letter by an integer from 𝑍26 that is 0 to 25 The encryption function is 𝑓(𝑝) = (𝑝 + 3) 𝑚𝑜𝑑 26 ➔ replace each integer 𝑝 ∈ {0,1,2,…,25} by 𝑓(𝑝) ∈ {0,1,2,…,25} Let’s Solve Encrypt the message “MEET YOU IN THE PARK” using the Caesar cipher. Replace each letter by its position - 1 12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10 Now replace each of these numbers p by f(p) = (p + 3) mod 26 15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13 Translate the numbers back to letters “PHHW BRX LQ WKH SDUN.” Caesar Cipher The encryption function is 𝑓(𝑝) = (𝑝 + 3) 𝑚𝑜𝑑 26 What is the decryption function? 𝑓 −1 (𝑝) = (𝑝 − 3) 𝑚𝑜𝑑 26 Each letter in the coded message is shifted back three letters in the alphabet, with the first three letters sent to the last three letters 12/4/2023 Discrete Structures II 44 Shift Cipher The Caesar cipher is one of a family of ciphers called shift ciphers. Letters can be shifted by an integer 𝑘, such as 3 The encryption function is 𝑓(𝑝) = (𝑝 + 𝑘) 𝑚𝑜𝑑 26 and the decryption function is 𝑓 −1 (𝑝) = (𝑝 − 𝑘) 𝑚𝑜𝑑 26 ➔ The integer 𝑘 is called a key. Let’s Solve Encrypt the message “STOP GLOBAL WARMING” using the shift cipher with k = 11. Replace each letter with the corresponding element of 𝑍26 18 19 14 15 6 11 14 1 0 11 22 0 17 12 8 13 6 Apply the shift 𝑓(𝑝) = (𝑝 + 11) 𝑚𝑜𝑑 26, yielding 3 4 25 0 17 22 25 12 11 22 7 11 2 23 19 24 17 Translate the numbers back to letters “DEZA RWZMLW HLCXTYR.” Let’s Solve Decrypt the message “LEWLYPLUJL PZ H NYLHA ALHJOLY” that was encrypted using the shift cipher with k = 7. Replace each letter with the corresponding element of Z26. 11 4 22 11 24 15 11 20 9 11 15 25 7 13 24 11 7 0 0 11 7 9 14 11 24 Shift each of the numbers by −𝑘 = −7 𝑚𝑜𝑑𝑢𝑙𝑜 26, yielding 4 23 15 4 17 8 4 13 2 4 8 18 0 6 17 4 0 19 19 4 0 2 7 4 17 Translate the numbers back to letters “EXPERIENCE IS A GREAT TEACHER.” Affine Ciphers Shift ciphers are a special case of affine ciphers which use functions of the form 𝑓(𝑝) = (𝑎𝑝 + 𝑏) 𝑚𝑜𝑑 26 where 𝑎 and 𝑏 are integers, chosen so that 𝑓 is a bijection The function is a bijection if and only if gcd(𝑎, 26) = 1. Let’s Solve! Example: What letter replaces the letter K when the function 𝑓(𝑝) = (7𝑝 + 3) 𝑚𝑜𝑑 26 is used for encryption. 10 represents K 𝑓(10) = (7 ∙ 10 + 3) 𝑚𝑜𝑑 26 = 21 21 corresponds to V So K is replaced by V Let’s Solve! To decrypt a message encrypted by an affine cipher, the congruence c ≡ ap + b (mod 26) needs to be solved for p. Subtract b from both sides to obtain c− b ≡ ap (mod 26). Multiply both sides by the inverse of a modulo 26, which exists since gcd(a,26) = 1. ā(c− b) ≡ āap (mod 26), which simplifies to ā(c− b) ≡ p (mod 26). p ≡ ā(c− b) (mod 26) is used to determine p in Z26. Private Key Cryptography All classical ciphers, including shift and affine ciphers, are private key cryptosystems. Knowing the encryption key allows one to quickly determine the decryption key. All parties who wish to communicate using a private key cryptosystem must share the key and keep it a secret. Public Key Cryptography In public key cryptosystems, first invented in the 1970s, knowing how to encrypt a message does not help one to decrypt the message. Therefore, everyone can have a publicly known encryption key. The only key that needs to be kept secret is the decryption key. The RSA Cryptosystem A public key cryptosystem, now known as the RSA system was introduced in 1976 by three researchers at MIT. Ronald Rivest Adi Shamir Leonard Adelman (Born 1948) (Born 1952) (Born 1945) The public encryption key is 𝑛, 𝑒 𝑛 = 𝑝𝑞 (the modulus) is the product of two large (200 digits) primes 𝑝 and 𝑞, exponent 𝑒 relatively prime to (𝑝 − 1)(𝑞 − 1) RSA Encryption To encrypt a message using RSA using a key (𝑛, 𝑒): Translate the plaintext message M into sequences of two digit integers representing the letters. Use 00 for A, 01 for B, etc. Concatenate the two digit integers into strings of digits. Divide this string into equally sized blocks of 2N digits where 2N is the largest even number 2525…25 with 2N digits that does not exceed n. The plaintext message M is now a sequence of integers 𝑚1 , 𝑚2 , … , 𝑚𝑘. Each block (an integer) is encrypted using the function 𝐶 = 𝑀𝑒 𝑚𝑜𝑑 𝑛. RSA Encryption Encrypt the message STOP using the RSA cryptosystem with key(2537,13). Note that 2537 = 43∙ 59, p = 43 and q = 59 are primes and gcd(13, 42∙ 58) = 1. Translate the letters in STOP to their numerical equivalents 18 19 14 15. Divide into blocks of four digits (because 2525 < 2537 < 252525) to obtain 1819 1415. Encrypt each block using the mapping 𝐶 = 𝑀13 𝑚𝑜𝑑 2537. Since 181913 𝑚𝑜𝑑 2537 = 2081 and 141513 𝑚𝑜𝑑 2537 = 2182, the encrypted message is 2081 2182. RSA Decryption To decrypt a RSA ciphertext message, the decryption key d, an inverse of e modulo (p−1)(q −1) is needed. The inverse exists since gcd(e,(p−1)(q −1)) = gcd(13, 42∙ 58) = 1. With the decryption key d, we can decrypt each block with the computation 𝑀 = 𝐶 𝑑 𝑚𝑜𝑑 𝑝 ∙ 𝑞. RSA works as a public key system since the only known method of finding d is based on a factorization of n into primes. There is currently no known feasible method for factoring large numbers into primes. RSA Decryption Example: The message 0981 0461 is received. What is the decrypted message if it was encrypted using the RSA cipher from the previous example. The message was encrypted with n = 43∙ 59 and exponent 13. An inverse of 13 modulo 42∙ 58 = 2436 is d = 937. To decrypt a block C, 𝑀 = 𝐶 937 𝑚𝑜𝑑 2537. Since 0981937 𝑚𝑜𝑑 2537 = 0704 and 0461937 𝑚𝑜𝑑 2537 = 1115, the decrypted message is 0704 1115. Translating back to English letters, the message is HELP.