Math 240 Archives - Page 5 of 9 - Shawn Zhong

4.4 Solving Congruences

Linear Congruences • Definition ○ A congruence of the form ax≡b (mod m), ○ where m is a positive integer, a and b are integers, and x is a variable ○ is called a linear congruence. ○ The solutions to a linear congruence ax≡b (mod m) are ○ all integers x that satisfy the congruence. • Definition ○ An integer ā such that āa≡1 (mod m) is said to be an inverse of a modulo m. • Example ○ 5 is an inverse of 3 modulo 7 since 5∙3=15≡1 (mod 7) • One method of solving linear congruences makes use of an inverse ā, if it exists. • Although we can not divide both sides of the congruence by a • we can multiply by ā to solve for x. Inverse of a modulo m • The following theorem guarantees that • an inverse of a modulo m exists whenever a and m are relatively prime. • Two integers a and b are relatively prime when gcd(a,b) = 1. • Theorem 1 ○ If a and m are relatively prime integers and m 1, then an inverse of a modulo m exists. ○ Furthermore, this inverse is unique modulo m. ○ So, there is a unique positive integer ā less than m that is an inverse of a modulo m ○ And every other inverse of a modulo m is congruent to ā modulo m • Proof ○ Since gcd(a,m) = 1 ○ By Theorem 6 of Section 4.3, there are integers s and t such that sa + tm = 1. ○ Hence, sa + tm ≡ 1 (mod m). ○ Since tm ≡ 0 (mod m), it follows that sa ≡ 1 (mod m) ○ Consequently, s is an inverse of a modulo m. ○ The uniqueness of the inverse is Exercise 7. Finding Inverses • The Euclidean algorithm and Bézout coefficients gives us • a systematic approaches to finding inverses. • Find an inverse of 3 modulo 7. ○ Because gcd(3,7) = 1, by Theorem 1, an inverse of 3 modulo 7 exists. ○ Using the Euclidian algorithm: 7 = 2∙3 + 1. ○ From this equation, we get −2∙3 + 1∙7 = 1 ○ and see that −2 and 1 are Bézout coefficients of 3 and 7. ○ Hence, −2 is an inverse of 3 modulo 7. ○ Also every integer congruent to −2 modulo 7 is an inverse of 3 modulo 7 ○ i.e., 5, −9, 12, etc. • Find an inverse of 101 modulo 42620. ○ First use the Euclidian algorithm to show that gcd(101,42620) = 1. § 42620 = 45∙101 + 75 § 101 = 1∙75 + 26 § 75 = 2∙26 + 23 § 26 = 1∙23 + 3 § 23 = 7∙3 + 2 § 3 = 1∙2 + 1 § 2 = 2∙1 ○ Working Backwards § 1 = 3 − 1 ∙ 2 § 1 = 3 − 1 ∙ (23 − 7∙3) = − 1 ∙ 23 + 8 ∙ 3 § 1 = −1 ∙ 23 + 8 ∙ (26 − 1 ∙ 23) = 8 ∙ 26 − 9 ∙ 23 § 1 = 8 ∙26 − 9 ∙ (75 − 2 ∙ 26)= 26 ∙ 26 − 9 ∙ 75 § 1 = 26 ∙ (101 − 1∙75) − 9 ∙75 = 26 ∙ 101 − 35 ∙ 75 § 1 = 26 ∙ 101 − 35 ∙ (42620 − 45 ∙ 101) = − 35 ∙ 42620 + 1601 ∙ 101 ○ Bézout coefficients : − 35 and 1601 ○ Therefore 1601 is an inverse of 101 modulo 42620 Using Inverses to Solve Congruences • We can solve the congruence ax≡b (mod m) by multiplying both sides by ā. • What are the solutions of the congruence 3x ≡ 4 (mod 7). ○ We found that −2 is an inverse of 3 modulo 7 (two slides back). ○ We multiply both sides of the congruence by −2 giving ○ −2 ∙ 3x ≡ −2 ∙ 4(mod 7). ○ Because −6 ≡ 1 (mod 7) and −8 ≡ 6 (mod 7) ○ It follows that if x is a solution, then x ≡ −8 ≡ 6 (mod 7) ○ We need to determine if every x with x ≡ 6 (mod 7) is a solution. ○ Assume that x ≡ 6 (mod 7). ○ By Theorem 5 of Section 4.1, it follows that 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, … The Chinese Remainder Theorem • 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 ○ When divided by 7, the remainder is 2. ○ What will be the number of things? • This puzzle can be translated into the solution of the system of congruences: ○ x ≡ 2 (mod 3) ○ x ≡ 3 (mod 5) ○ x ≡ 2 (mod 7) • Theorem 2: (The Chinese Remainder Theorem) ○ Let m_1,m_2,…,m_n be pairwise relatively prime positive integers greater than one ○ Let a_1,a_2,…,a_n be arbitrary integers. ○ Then the system § x ≡ a_1 (mod m_1) § x ≡ a_2 (mod m_2) § ⋮ § x ≡ a_n (mod m_n) ○ has a unique solution modulo m=m_1 m_2⋯m_n. ○ That is, there is a solution x with 0≤x m ○ and all other solutions are congruent modulo m to this solution. • Proof ○ We’ll show that a solution exists by describing a way to construct the solution. ○ Showing that the solution is unique modulo m is Exercise 30. • Algorithm ○ To construct a solution first let M_k=m/m_k for k=1,2,…,n and m=m_1 m_2,…,m_n ○ Since gcd(m_k,M_k) = 1, there is an integer y_k, an inverse of M_k modulo m_k, such that § M_k y_k≡1 (mod m_k ) ○ Form the sum § x=a_1 M_1 y_1+a_2 M_2 y_2+a_3 M_3 y_3 ○ Note that because M_j ≡ 0 (mod m_k) whenever j≠k ○ all terms except the kth term in this sum are congruent to 0 modulo m_k . ○ Because M_k y_k ≡ 1 (mod m_k), we see that x ≡ a_k M_K y_k ≡ a_k (mod m_k), for k = 1,2,…,n. ○ Hence, x is a simultaneous solution to the n congruences. § x ≡ a_1 (mod m_1) § x ≡ a_2 (mod m_2) § ⋮ § x ≡ a_n (mod m_n) • Example ○ Consider the 3 congruences from Sun-Tsu’s problem: § x ≡ 2 (mod 3) § x ≡ 3 (mod 5) § x ≡ 2 (mod 7) ○ Let § m = 3∙ 5 ∙ 7 = 105 § M_1=m/3=35 § M_2=m/5=21 § M_3=m/7=15 ○ We see that § y_1= 2 is an inverse of M_1 = 35 modulo 3 since 35 ∙ 2 ≡ 2 ∙ 2 ≡ 1 (mod 3) § y_2= 1 is an inverse of M_2 = 21 modulo 5 since 21 ≡ 1 (mod 5) § y_3= 1 is an inverse of M_3 = 15 modulo 7 since 15 ≡ 1 (mod 7) ○ Hence, § x=a_1 M_1 y_1+a_2 M_2 y_2+a_3 M_3 y_3 § = 2 ∙ 35 ∙ 2 + 3 ∙ 21 ∙ 1 + 2 ∙ 15 ∙ 1 = 233 ≡ 23 (mod 105) ○ We have shown that 23 is the smallest positive integer that is a simultaneous solution. • Back Substitution ○ We can also solve systems of linear congruences with pairwise relatively prime moduli ○ by rewriting a congruences as an equality using Theorem 4 in Section 4.1 ○ substituting the value for the variable into another congruence, ○ and continuing the process until we have worked through all the congruences. ○ This method is known as back substitution. • Example ○ Use the method of back substitution to find all integers x such that § x ≡ 1 (mod 5) § x ≡ 2 (mod 6) § x ≡ 3 (mod 7). ○ By Theorem 4, the first congruence can be rewritten as x = 5t +1, where t is an integer. ○ Substituting into the second congruence yields 5t +1 ≡ 2 (mod 6). ○ Solving this tells us that t ≡ 5 (mod 6). ○ Using Theorem 4 again gives t = 6u + 5 where u is an integer. ○ Substituting this back into x = 5t +1, gives x = 5(6u + 5) +1 = 30u + 26. ○ Inserting this into the third equation gives 30u + 26 ≡ 3 (mod 7). ○ Solving this congruence tells us that u ≡ 6 (mod 7). ○ By Theorem 4, u = 7v + 6, where v is an integer. ○ Substituting this expression for u into x = 30u + 26 ○ tells us that x = 30(7v + 6) + 26 = 210v + 206. ○ Translating this back into a congruence we find the solution x ≡ 206 (mod 210) Fermat’s Little Theorem • Theorem 3: (Fermat’s Little Theorem) ○ If p is prime and a is an integer not divisible by p, then a^(p−1) ≡ 1 (mod p) ○ Furthermore, for every integer a we have a^p ≡ a (mod p) • This is useful in computing the remainders modulo p of large powers of integers. • Find 7^222 mod 11. ○ By Fermat’s little theorem, we know that 7^10 ≡ 1 (mod 11) ○ and so (7^10 )^k ≡ 1 (mod 11), for every positive integer k ○ Therefore, 7^222 = 7^(22×10+2)=(7^10 )^22×7^2 ≡ 1^22×49 ≡ 5 (mod 11). ○ Hence, 7^222 mod 11 = 5. Pseudoprimes • By Fermat’s little theorem n 2 is prime, where ○ 2^(n−1) ≡ 1 (mod n). • But if this congruence holds, n may not be prime. • Composite integers n such that 2^(n−1) ≡ 1 (mod n) are called pseudoprimes to the base 2. • Example: The integer 341 is a pseudoprime to the base 2. ○ 341 = 11 ∙ 31 ○ 2^340 ≡ 1 (mod 341) (see in Exercise 37) ○ We can replace 2 by any integer b ≥ 2. • Definition ○ Let b be a positive integer. ○ If n is a composite integer, and b^(n−1) ≡ 1 (mod n) ○ then n is called a pseudoprime to the base b • Given a positive integer n, such that 2^(n−1) ≡ 1 (mod n): ○ If n does not satisfy the congruence, it is composite. ○ If n does satisfy the congruence, it is either prime or a pseudoprime to the base 2. • Doing similar tests with additional bases b, provides more evidence as to whether n is prime. • Among the positive integers not exceeding a positive real number x, compared to primes • there are relatively few pseudoprimes to the base b. • For example, among the positive integers less than 〖10〗^10 there are 455,052,512 primes • but only 14,884 pseudoprimes to the base 2 Primitive Roots • Definition ○ A primitive root modulo a prime p is an integer r in Zp such that ○ every nonzero element of Zp is a power of r • Example ○ Since every element of Z11 is a power of 2, 2 is a primitive root of 11. ○ Powers of 2 modulo 11 § 2^1=2 § 2^2=4 § 2^3=8 § 2^4=5 § 2^5=10 § 2^6=9 § 2^7=7 § 2^8=3 § 2^9=6 § 2^10=1 • Example ○ Since not all elements of Z11 are powers of 3, 3 is not a primitive root of 11. ○ Powers of 3 modulo 11 § 3^1=3 § 3^2=9 § 3^3=5 § 3^4=4 § 3^5=1 § and the pattern repeats for higher powers. • Important Fact ○ There is a primitive root modulo p for every prime number p Discrete Logarithms • Suppose p is prime and r is a primitive root modulo p. • If a is an integer between 1 and p −1, that is an element of Zp, • there is a unique exponent e such that r^e = a in Zp, that is, r^e mod p = a. • Definition ○ Suppose p is prime ○ r is a primitive root modulo p ○ and a is an integer between 1 and p −1, inclusive. ○ If r^3 mod p = a and 1 ≤ e ≤ p − 1 ○ We say that e is the discrete logarithm of a modulo p to the base r and we write log_r⁡a=e • Example 1 ○ We write log_2⁡3=8 ○ Since the discrete logarithm of 3 modulo 11 to the base 2 is 8 as 28 = 3 modulo 11. • Example 2 ○ We write log_2⁡5=4 ○ since the discrete logarithm of 5 modulo 11 to the base 2 is 4 as 24 = 5 modulo 11. • There is no known polynomial time algorithm for computing the discrete logarithm • The problem plays a role in cryptography as will be discussed in Section 4.6.

4.3 Primes and Greatest Common Divisors

Primes • Definition ○ A positive integer p greater than 1 is called prime if the only positive factors are 1 and p. ○ A positive integer that is greater than 1 and is not prime is called composite. • Example ○ The integer 7 is prime because its only positive factors are 1 and 7 ○ But 9 is composite because it is divisible by 3. The Fundamental Theorem of Arithmetic • Theorem ○ Every positive integer greater than 1 can be written uniquely as ○ a prime or as the product of two or more primes ○ where the prime factors are written in order of nondecreasing size. • Examples ○ 100=2∙2∙5∙5=2^2∙5^2 ○ 641=641 ○ 999=3∙3∙3∙37=3^3∙37 ○ 1024=2∙2∙2∙2∙2∙2∙2∙2∙2∙2=2^10 The Sieve of Erastosthenes • The Sieve of Erastosthenes can be used to find all primes not exceeding a specified positive integer. • For example, begin with the list of integers between 1 and 100. • Delete all the integers, other than 2, divisible by 2. • Delete all the integers, other than 3, divisible by 3. • Next, delete all the integers, other than 5, divisible by 5. • Next, delete all the integers, other than 7, divisible by 7. • Since all the remaining integers are not divisible by any of the previous integers, other than 1 • The primes are: {2,3,5,7,11,15,1719,23,29,31,37,41,43,47,53, 59,61,67,71,73,79,83,89, 97} • If an integer n is a composite integer, then it has a prime divisor less than or equal to √n. • To see this, note that if n=ab, then a≤√n or b≤√n. • Trial division, a very inefficient method of determining if a number n is prime, • is to try every integer i≤√n and see if n is divisible by i. Infinitude of Primes • Theorem ○ There are infinitely many primes. (Euclid) • Proof ○ Assume finitely many primes: p_1, p_2, …, p_n ○ Let q = p_1 p_2⋯p_n+1 ○ Either q is prime or by the fundamental theorem of arithmetic it is a product of primes. ○ But none of the primes p_j divides q since if p_j | q, then ○ p_j divides q−p_1 p_2⋯p_n=1 . ○ Hence, there is a prime not on the list p_1, p_2, …, p_n. ○ It is either q, or if q is composite, it is a prime factor of q. ○ This contradicts the assumption that p_1, p_2, …, p_n are all the primes. ○ Consequently, there are infinitely many primes. Mersene Primes • Prime numbers of the form 2^p−1 , where p is prime, are called Mersene primes. • 2^2 − 1 = 3, 2^3 − 1 = 7, 2^5 − 1 = 37 , and 2^7 − 1 = 127 are Mersene primes. • 2^11 − 1 = 2047 is not a Mersene prime since 2047 = 23∙89. • There is an efficient test for determining if 2^p − 1 is prime. • The largest known prime numbers are Mersene primes. • As of mid-2011, 47 Mersene primes were known, the largest is 2^43,112,609 − 1, which has nearly 13 million decimal digits. Distribution of Primes • Mathematicians have been interested in the distribution of prime numbers among the positive integers. • In the nineteenth century, the prime number theorem was proved which gives an asymptotic estimate for the number of primes not exceeding x. • Prime Number Theorem ○ The ratio of the number of primes not exceeding x ○ and x/ln⁡x approaches 1 as x grows without bound. ○ The theorem tells us that the number of primes not exceeding x, can be approximated by x/ln⁡x . ○ The odds that a randomly selected positive integer less than n is prime are approximately (n/ln⁡n )/n =1/ln⁡n . Primes and Arithmetic Progressions • Euclid’s proof that there are infinitely many primes can be easily adapted to show that there are infinitely many primes in the following 4k+3 (k=1,2,3…) • In the 19th century G. Lejuenne Dirchlet showed that ○ every arithmetic progression ka+b, (k=1,2,3…) ○ where a and b have no common factor greater than 1 contains infinitely many primes. • Are there long arithmetic progressions made up entirely of primes? ○ 5,11, 17, 23, 29 is an arithmetic progression of five primes. ○ 199, 409, 619, 829, 1039,1249,1459,1669,1879,2089 is an arithmetic progression of ten primes. • In the 1930s, Paul Erdős conjectured that for every positive integer n greater than 1 • there is an arithmetic progression of length n made up entirely of primes. • This was proven in 2006, by Ben Green and Terrence Tau. Generating Primes • The problem of generating large primes is of both theoretical and practical interest. • We will see that finding large primes with hundreds of digits is important in cryptography. • So far, no useful closed formula that always produces primes has been found. • There is no simple function f(n) such that f(n) is prime for all positive integers n. • But f(n)= n^2−n+41 is prime for all integers 1,2,…, 40. • Because of this, we might conjecture that f(n) is prime for all positive integers n. • But f(41)=〖41〗^2 is not prime. • More generally, there is no polynomial with integer coefficients such that f(n) is prime for all positive integers n. • Fortunately, we can generate large integers which are almost certainly primes. See Chapter 7. Conjectures about Primes • Even though primes have been studied extensively for centuries, many conjectures about them are unresolved, including: • Goldbach’s Conjecture ○ Every even integer n, n 2, is the sum of two primes. ○ It has been verified by computer for all positive even integers up to 1.6 ∙1018. ○ The conjecture is believed to be true by most mathematicians. • There are infinitely many primes of the form n^2+1, where n is a positive integer. ○ But it has been shown that there are infinitely many primes of the form n^2+1 ○ where n is a positive integer or the product of at most two primes. • The Twin Prime Conjecture ○ The twin prime conjecture is that there are infinitely many pairs of twin primes. ○ Twin primes are pairs of primes that differ by 2. ○ Examples are 3 and 5, 5 and 7, 11 and 13, etc. ○ The current world’s record for twin primes (as of mid 2011) consists of numbers ○ 65,516,468,355∙〖23〗^33,333±1, which have 100,355 decimal digits. Greatest Common Divisor • Definition ○ Let a and b be integers, not both zero. ○ The largest integer d such that d | a and also d | b is calledthe greatest common divisor ○ The greatest common divisor of a and b is denoted by gcd(a,b). • What is the greatest common divisor of 24 and 36? ○ gcd(24, 36) = 12 • What is the greatest common divisor of 17 and 22? ○ gcd(17,22) = 1 • Definition ○ The integers a and b are relatively prime if their greatest common divisor is 1. ○ Example: 17 and 22 • Definition ○ The integers a_1, a_2, …, a_n are pairwise relatively prime ○ if gcd(a_i, a_j)= 1 whenever 1≤ i j≤n. • Determine whether the integers 10, 17 and 21 are pairwise relatively prime. ○ Because gcd(10,17) = 1, gcd(10,21) = 1, and gcd(17,21) = 1 ○ 10, 17, and 21 are pairwise relatively prime. • Determine whether the integers 10, 19, and 24 are pairwise relatively prime. ○ Because gcd(10,24) = 2, 10, 19, and 24 are not pairwise relatively prime. Finding the Greatest Common Divisor Using Prime Factorizations • Suppose the prime factorizations of a and b are: ○ a=p_1^(a_1 ) p_2^(a_2 )⋯p_n^(a_n ), b=p_1^(b_1 ) p_2^(b_2 )⋯p_n^(b_n ) ○ where each exponent is a nonnegative integer ○ and where all primes occurring in either prime factorization are included in both. • Then: ○ gcd⁡〖(a,b)=p_1^min⁡(a_1,b_1 ) p_2^min⁡(a_2,b_2 ) ⋯p_n^min⁡(a_n,b_n ) 〗 • This formula is valid since the integer on the right (of the equals sign) divides both a and b. • No larger integer can divide both a and b. • Example ○ 120 = 23 ∙3 ∙5 ○ 500 = 22 ∙53 ○ gcd(120,500) = 2^min⁡(3,2) ⋅3^min⁡(1,0) ⋅5^min⁡(1,3) = 2^2∙3^0∙5^1=20 • Finding the gcd of two positive integers using their prime factorizations is not efficient • because there is no efficient algorithm for finding the prime factorization of a positive integer. Least Common Multiple • Definition ○ The least common multiple of the positive integers a and b is ○ the smallest positive integer that is divisible by both a and b. It is denoted by lcm(a,b). • The least common multiple can also be computed from the prime factorizations. ○ lcm⁡〖(a,b)=p_1^max⁡(a_1,b_1 ) p_2^max⁡(a_2,b_2 ) ⋯p_n^max⁡(a_n,b_n ) 〗 • This number is divided by both a and b and no smaller number is divided by a and b. • Example ○ lcm(2^3 3^5 7^2, 2^4 3^3) = 2^max⁡(3,4) ⋅3^max⁡(5,3) ⋅7^max⁡(2,0) =2^4⋅3^5⋅7^2 • The greatest common divisor and the least common multiple of two integers are related by: • Theorem 5 ○ Let a and b be positive integers. ○ Then ab=gcd(a,b)∙lcm(a,b) Euclidean Algorithm • The Euclidian algorithm is an efficient method for computing the greatest common divisor of two integers. • It is based on the idea that gcd(a,b) is equal to gcd(a,c) • when a b and c is the remainder when a is divided by b. • Find gcd(91, 287): ○ 287 = 91 ∙ 3 + 14 ○ 91 = 14 ∙ 6 + 7 ○ 14 = 7 ∙ 2 + 0 ○ gcd(287, 91) = gcd(91, 14) = gcd(14, 7) = 7 • The Euclidean algorithm expressed in pseudocode is ○ In Section 5.3, we’ll see that the time complexity of the algorithm is O(log b), where a b. Correctness of Euclidean Algorithm • Lemma 1: Let a=bq+r, where a, b, q, and r are integers. Then gcd(a,b) = gcd(b,r). ○ Suppose that d divides both a and b. ○ Then d also divides a−bq=r ○ Hence, any common divisor of a and b must also be any common divisor of b and r. ○ Suppose that d divides both b and r. ○ Then d also divides bq+r=a. ○ Hence, any common divisor of a and b must also be a common divisor of b and r. ○ Therefore, gcd(a,b) = gcd(b,r). • Proof ○ Suppose that a and b are positive integers with a≥b. ○ Let r_0 = a and r_1 = b. ○ Successive applications of the division algorithm yields: § r_0=r_1 q_1+r_2, 0≤r_2 r_1 § r_1=r_2 q_2+r_3, 0≤r_3 r_2 § ⋮ § r_(n−2)=r_(n−1) q_(n−1)+r_2, 0≤r_n r_(n−1) § r_(n−1)=r_n q_n ○ Eventually, a remainder of zero occurs in the sequence of terms: a=r_0 r_1 r_2 …≥0. ○ The sequence can’t contain more than a terms. ○ By Lemma 1 , gcd(a,b) = gcd(r_0,r_1) = ∙ ∙ ∙ = gcd(r_(n−1),r_n) = gcd(r_n , 0) = r_n. ○ Hence the greatest common divisor is the last nonzero remainder in the sequence of divisions gcds as Linear Combinations • Bézout’s Theorem ○ If a and b are positive integers, then there exist integers s and t such that gcd(a,b) = sa + tb. • Definition ○ If a and b are positive integers, then ○ integers s and t such that gcd(a,b) = sa + tb are called Bézout coefficients of a and b. ○ The equation gcd(a,b) = sa + tb is called Bézout’s identity. ○ By Bézout’s Theorem, the gcd of integers a and b can be expressed in the form ○ sa + tb where s and t are integers. ○ This is a linear combination with integer coefficients of a and b. • Example ○ gcd(6,14) = (−2)∙6 + 1∙14 Finding gcds as Linear Combinations • Express gcd(252,198) = 18 as a linear combination of 252 and 198. • First use the Euclidean algorithm to show gcd(252,198) = 18 ○ 252 = 1∙198 + 54 ○ 198 = 3 ∙54 + 36 ○ 54 = 1 ∙36 + 18 ○ 36 = 2 ∙18 • Now working backwards ○ 18 = 54 − 1 ∙36 ○ 36 = 198 − 3 ∙54 • Substituting the 2nd equation into the 1st yields: ○ 18 = 54 − 1 ∙(198 − 3 ∙54 )= 4 ∙54 − 1 ∙198 • Substituting 54 = 252 − 1 ∙198 (from 1)) yields: ○ 18 = 4 ∙(252 − 1 ∙198) − 1 ∙198 = 4 ∙252 − 5 ∙198 • This method illustrated above is a two pass method. • It first uses the Euclidian algorithm to find the gcd and then • works backwards to express the gcd as a linear combination of the original two integers. • A one pass method, called the extended Euclidean algorithm, is developed in the exercises. Consequences of Bézout’s Theorem • Lemma 2: If a, b, and c are positive integers such that gcd(a, b) = 1 and a | bc, then a | c. ○ Assume gcd(a, b) = 1 and a | bc ○ Since gcd(a, b) = 1, by Bézout’s Theorem there are integers s and t such that § sa+tb=1 ○ Multiplying both sides of the equation by c, yields sac+tbc=c. ○ From Theorem 1 of Section 4.1: § a | tbc (part 2) § and a divides sac+tbc since a | sac and a | tbc (part 1) ○ We conclude a | c, since sac+tbc=c. • Lemma 3: If p is prime and p | a_1 a_2∙∙∙a_n, then ├ p┤|├ a_i ┤ for some i. • Lemma 3 is crucial in the proof of the uniqueness of prime factorizations. ○ If ├ p┤|├ a_1 a_2…a_n ┤ and p does not divide a_1 then gcd⁡〖(a_1,p)=1〗, so ├ p┤|├ a_2…a_n ┤ ○ If ├ p┤|├ a_2…a_n ┤ and p does not divide a_2 then gcd⁡〖(a_2,p)=1〗, so ├ p┤|├ a_3…a_n ┤ ○ ⋮ ○ Either this process stops because some ├ p┤|├ a_i ┤ for some i n or p|a_n Uniqueness of Prime Factorization • A prime factorization of a positive integer where the primes are in nondecreasing order is unique. ○ This part of the fundamental theorem of arithmetic. ○ Every positive integer has a prime factorization into primes, will be proved in Section 5.2. • Proof: (by contradiction) ○ Suppose that the positive integer n can be written as a product of primes in two distinct ways § n=p_1 p_2…p_s and n=q_1 q_2…q_t ○ Remove all common primes from the factorizations to get § n=p_(i_1 ) p_(i_2 )…p_(i_u ) and n=q_(j_1 ) q_(j_2 )…q_(j_v ) ○ By Lemma 3, it follows that p_(i_1 ) divides q_(j_k ), for some k ○ contradicting the assumption that p_(i_1 ) and q_(j_k ) are distinct primes. ○ Hence, there can be at most one factorization of n into primes in nondecreasing order. 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 7 ○ Let m be a positive integer and let a, b, and c be integers. ○ If ac≡bc (mod m) and gcd(c,m) = 1, then a≡b (mod m). • Proof ○ Since ac≡bc (mod m), m | (ac−bc)=c(a−b) by Lemma 2 and gcd(c,m) = 1 ○ It follows that m | (a−b). Hence, a≡b (mod m).

4.2 Integer Representations and Algorithms

$Representations of Integers • In the modern world, we use decimal, or base 10, notation to represent integers. • For example when we write 965, we mean 9∙102 + 6∙101 + 5∙100 . • We can represent numbers using any base b, where b is a positive integer greater than 1. • The bases b = 2 (binary), b = 8 (octal), and b= 16 (hexadecimal) are important for computing and communications • The ancient Mayans used base 20 and the ancient Babylonians used base 60. Base b Representations • We can use positive integer b greater than 1 as a base, because of this theorem: • Theorem 1 ○ Let b be a positive integer greater than 1. ○ Then if n is a positive integer, it can be expressed uniquely in the form: ○ n=a_k b^k+a_(k−1) b^(k−1)+…+a_1 b+a_0 ○ where k is a nonnegative integer, a_0,a_1,…,a_k are nonnegative integers less than b ○ and ak≠0. The a_j (j=0,…,k) are called the base-b digits of the representation. • The representation of n given in Theorem 1 is called the base b expansion of n • and is denoted by (a_k a_(k−1)…a_1 a_0 )_b. • We usually omit the subscript 10 for base 10 expansions. Binary Expansions • Most computers represent integers and do arithmetic with binary expansions of integers. • In these expansions, the only digits used are 0 and 1. • What is the decimal expansion of the integer that has (1 0101 1111)_2 as its binary expansion? ○ (1 0101 1111)_2 = 1∙2^8 + 0∙2^7 + 1∙2^6 + 0∙2^5 + 1⋅2^4 + 1∙2^3 + 1∙2^2 + 1∙2^1 + 1 = 351 • What is the decimal expansion of the integer that has (11011)2 as its binary expansion? ○ (11011)_2 = 1 ∙2^4 + 1∙2^3 + 0∙2^2 + 1∙2^1 + 1 = 27 Octal Expansions • The octal expansion (base 8) uses the digits {0,1,2,3,4,5,6,7}. • What is the decimal expansion of the number with octal expansion (7016)_8 ? ○ 7∙8^3 + 0∙8^2 + 1∙8^1 + 6 =3598 • What is the decimal expansion of the number with octal expansion (111)_8 ? ○ 1∙8^2 + 1∙8^1 + 1 = 64 + 8 + 1 = 73 Hexadecimal Expansions • The hexadecimal expansion needs 16 digits, but our decimal system provides only 10. • So letters are used for the additional symbols. • The hexadecimal system uses the digits {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. • The letters A through F represent the decimal numbers 10 through 15. • What is the decimal expansion of the number with hexadecimal expansion (2AE0B)_16 ? ○ 2∙〖16〗^4 + 10∙〖16〗^3 + 14∙〖16〗^2 + 0∙〖16〗^1 + 11 =175627 What is the decimal expansion of the number with hexadecimal expansion (E5)_16 ? ○ 14∙〖16〗^1 + 5 = 224 + 5 = 229 Base Conversion • To construct the base b expansion of an integer n: • Divide n by b to obtain a quotient and remainder. ○ n=bq_0+a_0, 0≤a_0 b • The remainder, a_0 , is the rightmost digit in the base b expansion of n. Next, divide q_0 by b. ○ q_0=bq_1+a_1, 0≤a_1 b • The remainder, a_1, is the second digit from the right in the base b expansion of n. • Continue by successively dividing the quotients by b • obtaining the additional base b digits as the remainder. • The process terminates when the quotient is 0. • Algorithm ○ q represents the quotient obtained by successive divisions by b, starting with q = n. ○ The digits in the base b expansion are the remainders of the division given by q mod b. ○ The algorithm terminates when q = 0 is reached. • Find the octal expansion of (12345)_10 ○ Successively dividing by 8 gives: ○ 12345 = 8 ∙ 1543 + 1 ○ 1543 = 8 ∙ 192 + 7 ○ 192 = 8 ∙ 24 + 0 ○ 24 = 8 ∙ 3 + 0 ○ 3 = 8 ∙ 0 + 3 ○ The remainders are the digits from right to left yielding (30071)_8. Comparison of Hexadecimal, Octal, and Binary Representations • Each octal digit corresponds to a block of 3 binary digits. • Each hexadecimal digit corresponds to a block of 4 binary digits. • So, conversion between binary, octal, and hexadecimal is easy. Conversion Between Binary, Octal, and Hexadecimal Expansions • Find the octal and hexadecimal expansions of (11 1110 1011 1100)_2. • To convert to octal, we group the digits into blocks of three • (011 111 010 111 100)_2, adding initial 0s as needed. • The blocks from left to right correspond to the digits 3,7,2,7, and 4. • Hence, the solution is (37274)_8. • To convert to hexadecimal, we group the digits into blocks of four • (0011 1110 1011 1100)_2, adding initial 0s as needed. • The blocks from left to right correspond to the digits 3,E,B, and C. • Hence, the solution is (3EBC)_16. Binary Addition of Integers • Algorithms for performing operations with integers using their binary expansions are important as computer chips work with binary numbers. Each digit is called a bit. • The number of additions of bits used by the algorithm to add two n-bit integers is O(n).$

4.1 Divisibility and Modular Arithmetic

$Division • Definition ○ If a and b are integers with a ≠ 0, ○ then a divides b if there exists an integer c such that b = ac. ○ When a divides b we say that a is a factor or divisor of b and that b is a multiple of a. ○ The notation a | b denotes that a divides b. ○ If a | b, then b/a is an integer. ○ If a does not divide b, we write a ∤ b. • Example ○ Determine whether 3 | 7 and whether 3 | 12. ○ 3 | 7 is false ○ 3 | 12 is true Properties of Divisibility • Theorem 1: Let a, b, and c be integers, where a ≠0. ○ If a | b and a | c, then a | (b + c); ○ If a | b, then a | bc for all integers c; ○ If a | b and b | c, then a | c. • Proof (i) ○ Suppose a | b and a | c, then it follows that ○ there are integers s and t with b = as and c = at. ○ Hence, b + c = as + at = a(s + t). ○ Hence, a | (b + c) • Corollary ○ If a, b, and c be integers, where a ≠0, such that a | b and a | c, ○ then a | mb + nc whenever m and n are integers. Division Algorithm • When an integer is divided by a positive integer, there is a quotient and a remainder. • This is traditionally called the “Division Algorithm,” but is really a theorem. • Division Algorithm ○ If a is an integer and d a positive integer, then ○ there are unique integers q and r, with 0 ≤ r d, such that ○ a = dq + r ○ d is called the divisor. ○ a is called the dividend. ○ q is called the quotient. ○ r is called the remainder. • Example: What are the quotient and reminder when 101 is divided by 11? ○ 101=11⋅9+2 ○ Thus the quotient is 9, and the remainder is 2 ○ 101 div 11 = 9 ○ 101 mod 11 = 2 • Example: What are the quotient and reminder when -11 is divided by 3? ○ −11=3⋅(−4)+1 Congruence Relation • Definition ○ If a and b are integers and m is a positive integer, ○ then a is congruent to b modulo m if m divides a – b. ○ The notation a ≡ b (mod m) says that a is congruent to b modulo m. ○ We say that a ≡ b (mod m) is a congruence and that m is its modulus. ○ Two integers are congruent mod m if and only if they have the same remainder when divided by m. ○ If a is not congruent to b modulo m, we write a ≢ b (mod m) • Determine whether 17 is congruent to 5 modulo 6 ○ 17 ≡ 5 (mod 6) because 6 divides 17 − 5 = 12. • Determine whether 24 and 14 are congruent modulo 6. ○ 24 ≢ 14 (mod 6) since 24 − 14 = 10 is not divisible by 6. The Relationship between (mod m) and mod m Notations • The use of “mod” in a ≡ b (mod m) and a mod m = b are different. ○ a ≡ b (mod m) is a relation on the set of integers. ○ In a mod m = b, the notation mod denotes a function. • The relationship between these notations is made clear in this theorem. • Theorem 3 ○ Let a and b be integers, and let m be a positive integer. ○ Then a ≡ b (mod m) if and only if ○ a mod m = b mod m. More on Congruence • Theorem 4 ○ Let m be a positive integer. ○ The integers a and b are congruent modulo m if and only if ○ there is an integer k such that a = b + km. • Proof: ○ If a ≡ b (mod m), then (by the definition of congruence) m | a – b. ○ Hence, there is an integer k such that a – b = km and equivalently a = b + km. ○ Conversely, if there is an integer k such that a = b + km, then km = a – b. ○ Hence, m | a – b and a ≡ b (mod m). Congruence of Sums and Products • Theorem 5 ○ Let m be a positive integer. ○ If a ≡ b (mod m) and c ≡ d (mod m), then § a + c ≡ b + d (mod m) § ac ≡ bd (mod m) • Proof: ○ Because a ≡ b (mod m) and c ≡ d (mod m) ○ by Theorem 4 there are integers s and t with b = a + sm and d = c + tm. ○ Therefore, § b + d = (a + sm) + (c + tm) = (a + c) + m(s + t) and § b d = (a + sm) (c + tm) = ac + m(at + cs + stm). ○ Hence, a + c ≡ b + d (mod m) and ac ≡ bd (mod m). • Example ○ Because 7 ≡ 2 (mod 5) and 11 ≡ 1 (mod 5) , it follows from Theorem 5 that ○ 18 = 7 + 11 ≡ 2 + 1 = 3 (mod 5) ○ 77 = 7 ∙ 11 ≡ 2 ∙ 1 = 2 (mod 5) Algebraic Manipulation of Congruence • Multiplying both sides of a valid congruence by an integer preserves validity. ○ If a ≡ b (mod m) holds then c∙a ≡ c∙b (mod m), where c is any integer, ○ holds by Theorem 5 with d = c. • Adding an integer to both sides of a valid congruence preserves validity. ○ If a ≡ b (mod m) holds then c + a ≡ c + b (mod m), where c is any integer, ○ holds by Theorem 5 with d = c. • Dividing a congruence by an integer does not always produce a valid congruence. ○ The congruence 14≡ 8 (mod 6) holds. ○ But dividing both sides by 2 does not produce a valid congruence since ○ 14/2 = 7 and 8/2 = 4, but 7≢4 (mod 6). Computing the mod m Function of Products and Sums • We use the following corollary to Theorem 5 to compute the remainder of the product or sum of two integers when divided by m from the remainders when each is divided by m. • Corollary: Let m be a positive integer and let a and b be integers. Then ○ (a + b) (mod m) = ((a mod m) + (b mod m)) mod m ○ ab mod m = ((a mod m) (b mod m)) mod m. Arithmetic Modulo m • Definitions ○ Let Zm be the set of nonnegative integers less than m: {0,1, …., m−1} ○ The operation +m is defined as a +_m b = (a + b) mod m. ○ This is addition modulo m. ○ The operation ∙m is defined as a ∙_m b = (a ∙ b) mod m. ○ This is multiplication modulo m. • Example: Find 7 +_11 9 and 7 ∙_11 9. ○ 7 +_11 9 = (7 + 9) mod 11 = 16 mod 11 = 5 ○ 7 ∙_11 9 = (7 ∙ 9) mod 11 = 63 mod 11 = 8 • The operations +_m and ∙_m satisfy many of the same properties as ordinary addition and multiplication. ○ Closure § If a and b belong to Zm , then a +_m b and a ∙_m b belong to Zm. ○ Associativity § If a, b, and c belong to Zm , then § (a +_m b) +_m c = a +_m (b +_m c) § (a ∙_m b) ∙_m c = a ∙_m (b ∙_m c). ○ Commutativity § If a and b belong to Zm , then § a +_m b = b +_m a § a ∙_m b = b ∙_m a. ○ Identity elements § The elements 0 and 1 are identity elements for addition and multiplication modulo m, respectively. § If a belongs to Zm , then a +_m 0 = a and a ∙_m 1 = a. ○ Additive inverses § If a≠ 0 belongs to Zm § then m − a is the additive inverse of a modulo m § and 0 is its own additive inverse. § a +_m (m− a) = 0 § 0 +_m 0 = 0 ○ Distributivity § If a, b, and c belong to Zm , then § a ∙_m (b +_m c) = (a ∙_m b) +_m (a ∙_m c) § (a +_m b) ∙_m c = (a ∙_m c) +_m (b ∙_m c). • Multiplicative inverses have not been included since they do not always exist. • For example, there is no multiplicative inverse of 2 modulo 6. • Using the terminology of abstract algebra ○ Zm with +_m is a commutative group ○ Zm with +_m and ∙_m is a commutative ring$

3.3 Complexity of Algorithms

The Complexity of Algorithms • Given an algorithm, how efficient is this algorithm for solving a problem given input of a particular size? • To answer this question, we ask: ○ How much time does this algorithm use to solve a problem? ○ How much computer memory does this algorithm use to solve a problem? • When we analyze the time the algorithm uses to solve the problem given input of a particular size, we are studying the time complexity of the algorithm. • When we analyze the computer memory the algorithm uses to solve the problem given input of a particular size, we are studying the space complexity of the algorithm. • In this course, we focus on time complexity. • The space complexity of algorithms is studied in later courses. • We will measure time complexity in terms of the number of operations an algorithm uses and we will use big-O and big-Theta notation to estimate the time complexity. • We can use this analysis to see whether it is practical to use this algorithm to solve problems with input of a particular size. • We can also compare the efficiency of different algorithms for solving the same problem. • We ignore implementation details because it is extremely complicated to consider them. Time Complexity • To analyze the time complexity of algorithms, we determine the number of operations, such as comparisons and arithmetic operations (addition, multiplication, etc.). • We can estimate the time a computer may actually use to solve a problem using the amount of time required to do basic operations. • We ignore minor details, such as the “house keeping” aspects of the algorithm. • We will focus on the worst-case time complexity of an algorithm. • This provides an upper bound on the number of operations an algorithm uses to solve a problem with input of a particular size. • It is usually much more difficult to determine the average case time complexity of an algorithm. • This is the average number of operations an algorithm uses to solve a problem over all inputs of a particular size. Complexity Analysis of Algorithms • Example: Describe the time complexity of the algorithm for finding the maximum element in a finite sequence. ○ Count the number of comparisons. ○ The max a_i comparison is made n − 1 times. ○ Each time i is incremented, a test is made to see if i≤n. ○ One last comparison determines that i>n. ○ Exactly 2(n−1)+1=2n−1 comparisons are made. ○ Hence, the time complexity of the algorithm is Θ(n). • Example: Determine the time complexity of the linear search algorithm. ○ Count the number of comparisons. ○ At each step two comparisons are made; i≤n and x≠a_i . ○ To end the loop, one comparison i≤n is made. ○ After the loop, one more i≤n comparison is made. ○ If x=a_i, 2i+1 comparisons are used. ○ If x is not on the list, 2n+1 comparisons are made and then an additional comparison is used to exit the loop. ○ So, in the worst case 2n+2 comparisons are made. ○ Hence, the complexity is Θ(n). • Example: Describe the average case performance of the linear search algorithm. ○ Assume the element is in the list and that the possible positions are equally likely. ○ By the argument on the previous slide, if x=a_i , the number of comparisons is 2i+1 ○ (3+5+7+…+(2n+1))/n=(2(1+2+3+…+n)+n)/n=2[n(n+1)/2]/n+1=n+2 ○ Hence, the average-case complexity of linear search is Θ(n). • Example: Describe the time complexity of binary search in terms of the number of comparisons used. ○ Assume (for simplicity) n = 2^k elements. Note that k=log⁡n. ○ Two comparisons are made at each stage; i<j, and x>a_m. ○ At the first iteration the size of the list is 2k and after the first iteration it is 2k−1. ○ Then 2k−2 and so on until the size of the list is 2^1=2. ○ At the last step, a comparison tells us that the size of the list is the size is 2^0=1 and the element is compared with the single remaining element. ○ Hence, at most 2k+2=2 log⁡n+2 comparisons are made. ○ Therefore, the time complexity is Θ (log⁡n), better than linear search. • Example: What is the worst-case complexity of bubble sort in terms of the number of comparisons made? ○ A sequence of n−1 passes is made through the list. ○ On each pass n−i comparisons are made. ○ (n−1)+(n−2)+…+2+1=n(n−1)/2=1/2 n^2−1/2 n ○ The worst-case complexity of bubble sort is Θ(n^2) • Example: What is the worst-case complexity of insertion sort in terms of the number of comparisons made? ○ The total number of comparisons are ○ 2+3+…+n=n(n−1)/2−1 ○ Therefore the complexity is Θ(n^2) • Example: How many additions of integers and multiplications of integers are used by the matrix multiplication algorithm to multiply two n×n matrices. ○ There are n^2 entries in the product. ○ Finding each entry requires n multiplications and n−1 additions. ○ Hence, n^3 multiplications and n^2 (n−1) additions are used. ○ Hence, the complexity of matrix multiplication is O(n^3). Understanding the Complexity of Algorithms Complexity of Problems • Tractable Problem ○ There exists a polynomial time algorithm to solve this problem. ○ These problems are said to belong to the Class P. • Intractable Problem ○ There does not exist a polynomial time algorithm to solve this problem • Unsolvable Problem ○ No algorithm exists to solve this problem, e.g., halting problem. • Class NP ○ Solution can be checked in polynomial time. ○ But no polynomial time algorithm has been found for finding a solution to problems in this class. • NP Complete Class ○ If you find a polynomial time algorithm for one member of the class, ○ it can be used to solve all the problems in the class. P Versus NP Problem • The P versus NP problem asks whether the class P = NP? • Are there problems whose solutions can be checked in polynomial time, but can not be solved in polynomial time? • Note that just because no one has found a polynomial time algorithm is different from showing that the problem can not be solved by a polynomial time algorithm. • If a polynomial time algorithm for any of the problems in the NP complete class were found, then that algorithm could be used to obtain a polynomial time algorithm for every problem in the NP complete class. • Satisfiability (in Section 1.3) is an NP complete problem. • It is generally believed that P≠NP since no one has been able to find a polynomial time algorithm for any of the problems in the NP complete class. • The problem of P versus NP remains one of the most famous unsolved problems in mathematics (including theoretical computer science). • The Clay Mathematics Institute has offered a prize of $1,000,000 for a solution.

Shawn Zhong

Shawn Zhong

Math 240

4.4 Solving Congruences

4.3 Primes and Greatest Common Divisors

4.2 Integer Representations and Algorithms

4.1 Divisibility and Modular Arithmetic

3.3 Complexity of Algorithms

Search

WeChat Account