62 NUMBER THEORY (Chapter 1) E PRIME NUMBERS An integer p is a prime number (or prime) if p > 1, and if the only positive numbers which divide p are 1 and p itself. 1 is neither prime nor composite. An integer greater than 1 that is not prime is said to be composite. We have already proven that there are an infinite number of primes, but they appear to not follow any pattern. It would be very useful to discover an efficient method for finding prime numbers, because at present no such method exists. This is in fact the basis of the RSA encription system by which international financial and security transactions are protected. The study of number theory is therefore a highly important and applicable area of study. The basis of the RSA encryption system is a suitable topic for an Extended Essay in Mathematics. E Euclid’s Lemma for primes SA M PL For integers a and b and prime p, if p j ab then either p j a or p j b. If p j a the proof is complete, so suppose p =j a. Proof: Since p =j a and p is prime, gcd(a, p) = 1. ) there exist integers r and s such that ar + ps = 1. It is possible that p j a and p j b. ) b = b £ 1 = b(ar + ps) = abr + bps But p j ab, so ab = kp for some integer k ) b = kpr + bps = p(kr + bs) ) p j b. So, either p j a or p j b. If p is a prime and p j a1 a2 a3 ::::an for a1 , a2 , a3 , ...., an 2 Z then there exists i where 1 6 i 6 n such that p j ai . Lemma: For example, if p j 6 £ 11 £ 24 then p j 6 or p j 11 or p j 24. At least one of 6, 11, and 24 must be a multiple of p. Proof: (By Induction) (1) If n = 1 then p j a1 . ) P1 is true. (2) If Pk is true, then p j a1 a2 a3 ::::ak ) p j ai for some i where 1 6 i 6 k. Now if p j a1 a2 a3 ::::ak ak+1 then p j (a1 a2 a3 ::::ak )ak+1 ) p j a1 a2 a3 ::::ak or p j ak+1 fusing Euclid’s Lemma for primesg ) p j ai for some i in 1 6 i 6 k, or p j ak+1 ) p j ai for some i in 1 6 i 6 k + 1 cyan magenta yellow 95 100 50 75 25 0 5 95 100 50 75 25 0 5 95 100 50 75 25 0 5 95 100 50 75 25 0 5 Thus P1 is true, and Pk+1 is true whenever Pk is true. ) Pn is true. fPrinciple of Mathematical Inductiong black IB HL OPT Discrete Mathematics Y:\HAESE\IB_HL_OPT-DM\IB_HL_OPT-DM_01\062IB_HL_OPT-DM_01.cdr Friday, 29 November 2013 2:47:52 PM BRIAN NUMBER THEORY (Chapter 1) 63 THE FUNDAMENTAL THEOREM OF ARITHMETIC Every positive integer greater than 1 is either prime, or is expressible uniquely (up to the ordering) as a product of primes. Proof: Let S be the set of positive integers which cannot be written as a product of primes, and suppose S is non-empty. Existence: By the Well Ordered Principle, S has a smallest number, which we will call a. If the only factors of a are a and 1 then a is a prime, which is a contradiction. ) we can write a as the product of factors a = a1 a2 where 1 < a1 < a, 1 < a2 < a. Neither a1 nor a2 are in S, since a is the smallest member of S. ) a1 and a2 can be factorised into primes: a1 = p1 p2 p3 ::::pr and a2 = q1 q2 q3 ::::qs . ) a = a1 a2 = (p1 p2 p3 ::::pr )(q1 q2 q3 ::::qs ) E ) a2 = S, which is a contradiction. Therefore S is empty, and every positive integer greater than 1 is either prime, or is expressible as a product of primes. SA M PL Uniqueness: Suppose an integer n > 2 has two different factorisations n = p1 p2 p3 ::::ps = q1 q2 q3 ::::qt where pi 6= qj for all i, j. By Euclid’s Lemma for primes, p1 j qj for some j. ) p1 = qj fas these are primesg Relabelling qj as q1 if necessary, we can instead write p1 = q1 ) n = p2 p3 p4 ::::ps = q2 q3 q4 ::::qt p1 By the same reasoning, relabelling if necessary, p2 = q2 and n = p3 p4 ::::ps = q3 q4 ::::qt p1 q 1 This can be done for all pj , showing that s 6 t. The same argument could be made swapping ps and qs, so t 6 s also. ) s = t, the pi s are a rearrangement of the qj s, and the prime factorisation is unique up to the ordering of the primes. Example 27 Discuss the prime factorisation of 360, including how many factors 360 has. magenta yellow 95 100 50 75 25 0 5 95 100 50 75 25 0 5 95 100 50 75 25 0 5 95 100 50 75 25 0 5 cyan 360 = 23 £ 32 £ 51 and this factorisation is unique up to the ordering of the factors. The only prime factors of 360 are 2, 3, and 5. Check this result by listing Including 1 and 360, 360 has all 24 factors in a systematic way. For example: (3 + 1)(2 + 1)(1 + 1) 20 £ 30 £ 50, =4£3£2 22 £ 31 £ 50, .... = 24 factors. 360 180 90 45 15 5 2 2 2 3 3 black Y:\HAESE\IB_HL_OPT-DM\IB_HL_OPT-DM_01\063IB_HL_OPT-DM_01.cdr Monday, 20 January 2014 1:18:54 PM BRIAN IB HL OPT Discrete Mathematics 64 NUMBER THEORY (Chapter 1) Finally, we present a theorem that can be used to reduce the work in identifying whether a given integer, n, p is prime. In it we show that we need only attempt to divide n by all the primes p 6 n. If none of these is a divisor, then n must itself be prime. Theorem: If n 2 Z + is composite, then n has a prime divisor p such that p 6 p n. Proof: Let n 2 Z + be composite. ) n = ab where a, b 2 Z + such that n > a > 1 and n > b > 1. p p If a > n and b > n, then ab > n, which is a contradiction. p ) at least one of a or b must be 6 n. p Without loss of generality, suppose a 6 n. E Since a > 1, there exists a prime p such that p j a. fFundamental Theorem of Arithmeticg EXERCISE 1E SA M PL But a j n, so p j n. fp j a and a j n ) p j ng p p Since p 6 a 6 n, n has a prime divisor p such that p 6 n. 1 Determine which of the following are primes: a 143 b 221 c 199 d 223 c 1111 d 11 111 2 Prove that 2 is the only even prime. 3 Which of the following repunits is prime? a 11 b 111 4 Show that if p and q are primes and p j q, then p = q. 5 28 £ 34 £ 72 is a perfect square. It equals (24 £ 32 £ 7)2 . a Prove that: i all the powers in the prime-power factorisation of n 2 Z + are even , n is a square ii given n 2 Z + , the number of factors of n is odd , n is a square. p b Hence prove that 2 is irrational. cyan magenta yellow 95 100 50 75 25 0 5 95 100 50 75 25 0 5 95 100 50 75 25 0 5 95 50 75 25 0 5 100 a Prove that if a, n 2 Z + , n > 2 and an ¡ 1 is prime, then a = 2. Hint: Consider 1 + a + a2 + :::: + an¡1 and its sum. b It is claimed that 2n ¡ 1 is always prime for n > 2. Is the claim true? c It is claimed that 2n ¡ 1 is always composite for n > 2. Is the claim true? d If n is prime, is 2n ¡1 always prime? Explain your answer. 6 black Primes of the form 2n - 1 are called Mersenne primes. IB HL OPT Discrete Mathematics Y:\HAESE\IB_HL_OPT-DM\IB_HL_OPT-DM_01\064IB_HL_OPT-DM_01.cdr Friday, 14 February 2014 11:27:49 AM BRIAN NUMBER THEORY (Chapter 1) 65 7 Find the prime factorisation of: a 9555 b 989 c 9999 d 111 111 8 Which positive integers have exactly: a three positive divisors 9 b four positive divisors? a Find all prime numbers which divide 50! b How many zeros are at the end of 50! when written as an integer? c Find all n 2 Z such that n! ends in exactly 74 zeros. 10 Given that p is prime, prove that: a p j an ) pn j an b p j a2 ) p j a c p j an ) p j a 11 There are infinitely many primes, and 2 is the only even prime. a Explain why the form of odd primes can be 4n + 1 or 4n + 3. b Prove that there are infinitely many primes of the form 4n + 3. SA M PL E There are also infinitely many primes of the form 4n + 1, but the proof is beyond the scope of this course. n 12 The Fermat primes are primes of the form 22 + 1. a Find the first four Fermat primes. b Fermat conjectured that all such numbers were prime whenever n was prime. By examining the case n = 5, show that Fermat was incorrect. RESEARCH cyan magenta yellow 95 100 50 75 25 0 5 95 100 50 75 25 0 5 95 100 50 75 25 0 5 95 100 50 75 25 0 5 ² The first two perfect numbers are 6 and 28. Research how these numbers are connected to the Mersenne primes of the form 2n ¡ 1. ² The repunits Rk are prime only if k is prime, and even then only rarely. Thus far, the only prime repunits discovered are R2 , R19 , R23 , R317 , and R1031 . Research a proof that a repunit Rk may only be prime if k is prime. black IB HL OPT Discrete Mathematics Y:\HAESE\IB_HL_OPT-DM\IB_HL_OPT-DM_01\065IB_HL_OPT-DM_01.cdr Friday, 14 February 2014 11:58:53 AM BRIAN

© Copyright 2018 ExploreDoc