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=22∙52 ○ 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/lnx approaches 1 as x grows without bound. ○ The theorem tells us that the number of primes not exceeding x, can be approximated by x/lnx . ○ The odds that a randomly selected positive integer less than n is prime are approximately (n/lnn )/n =1/lnn . 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) = 22∙30∙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) =24⋅35⋅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).
