Slide 1Chapter 5: Number TheorySlide 3Prime and Composite NumbersNumber TheoryDivisibilityTerminologyExample: Finding FactorsSlide 9Alternative Definition of a Prime NumberSieve of EratosthenesSlide 12Divisibility TestsSlide 14Divisibility Tests (continued)Example: Divisibility TestsThe Fundamental Theorem of ArithmeticExample: Unique Prime FactorizationThe Infinitude of PrimesThe Search for Large PrimesMersenne Numbers and Mersenne PrimesExample: Mersenne NumbersFermat NumbersEuler’s and Escott’s Formulas for Finding PrimesChapter 5Number Theory© 2008 Pearson Addison-Wesley.All rights reserved© 2008 Pearson Addison-Wesley. All rights reserved5-1-2Chapter 5: Number Theory5.1 Prime and Composite Numbers 5.2 Selected Topics From Number Theory5.3 Greatest Common Factor and Least Common Multiple 5.4 The Fibonacci Sequence and the Golden Ratio© 2008 Pearson Addison-Wesley. All rights reserved5-1-3Chapter 1Section 5-1Prime and Composite Numbers© 2008 Pearson Addison-Wesley. All rights reserved5-1-4Prime and Composite Numbers•Primes, Composites, and Divisibility•The Fundamental Theorem of Arithmetic•The Infinitude of Primes•The Search for Large Primes© 2008 Pearson Addison-Wesley. All rights reserved5-1-5Number TheoryNumber Theory is the branch of mathematics devoted to the study of the properties of the natural numbers.© 2008 Pearson Addison-Wesley. All rights reserved5-1-6DivisibilityA counting number is divisible by another if the operation of dividing the first by the second leaves a remainder of 0.Formally: the natural number a is divisible by the natural number b if there exists a natural number k such that a = bk. If b divides a, then we write b|a.© 2008 Pearson Addison-Wesley. All rights reserved5-1-7TerminologyIf the natural number a is divisible by the natural number b, then b is a factor (or divisor) of a, and a is a multiple of b.The number 30 equals 6 · 5; this product is called a factorization of 30.© 2008 Pearson Addison-Wesley. All rights reserved5-1-8Example: Finding FactorsFind all the natural number factors of each number. a) 24 b) 13Solutiona) To find factors try to divide by 1, 2, 3, 4, 5, 6 and so on to get the factors 1, 2, 3, 4, 6, 8, 12, and 24.b) The only factors are 1 and 13.© 2008 Pearson Addison-Wesley. All rights reserved5-1-9Prime and Composite NumbersA natural number greater than 1 that has only itself and 1 as factors is called a prime number. A natural number greater than 1 that is not prime is called composite.© 2008 Pearson Addison-Wesley. All rights reserved5-1-10Alternative Definition of a Prime NumberA prime number is a natural number that has exactly two different natural number factors.© 2008 Pearson Addison-Wesley. All rights reserved5-1-11Sieve of EratosthenesOne systematic method for identifying primes is known as the Sieve of Eratosthenes. To construct a sieve, list all the natural numbers from 2 through some given natural number. The number 2 is prime, but all multiples of it are composite. Circle the 2 and cross out all other multiples of 2. Continue this process for all primes less than or equal to the square root of the last number in the list. Circle all remaining numbers that are not crossed out.© 2008 Pearson Addison-Wesley. All rights reserved5-1-12Sieve of Eratosthenes© 2008 Pearson Addison-Wesley. All rights reserved5-1-13Divisibility TestsDivisibility tests are an aid to determine whether a natural number is divisible by another natural number. Simple tests are given on the next two slides. There are tests for 7 and 11, but they are more involved.© 2008 Pearson Addison-Wesley. All rights reserved5-1-14Divisibility TestsDivisible by Test2 Number ends in 0, 2, 4, 6, or 8.3 Sum of the digits is divisible by 3.4 Last two digits form a number divisible by 4.5 Number ends in 0 or 5.6 Number is divisible by both 2 and 3.© 2008 Pearson Addison-Wesley. All rights reserved5-1-15Divisibility Tests (continued)Divisible by Test8 Last three digits form a number divisible by 8.9 Sum of the digits is divisible by 9.10 The last digit is 0.12 Number is divisible by both 3 and 4.© 2008 Pearson Addison-Wesley. All rights reserved5-1-16Example: Divisibility TestsIs the number 4,355,211 divisible by 3?SolutionCheck: 4 + 3 + 5 + 5 + 2 + 1 + 1 = 21, which is divisible by 3. Therefore, the given number is divisible by 3.© 2008 Pearson Addison-Wesley. All rights reserved5-1-17The Fundamental Theorem of ArithmeticEvery natural number can be expressed in one and only one way as a product of primes (if the order of the factors is disregarded). This unique product of primes is called the prime factorization of the natural number.© 2008 Pearson Addison-Wesley. All rights reserved5-1-18Example: Unique Prime FactorizationFind the prime factorization of 240.SolutionUsing a tree format:2402 120 2 60 2 30 2 15 3 5 240 = 24 · 3 · 5© 2008 Pearson Addison-Wesley. All rights reserved5-1-19The Infinitude of PrimesThere is no largest prime number. Euclid proved this around 300 B.C.© 2008 Pearson Addison-Wesley. All rights reserved5-1-20The Search for Large PrimesPrimes are the basis for modern cryptography systems, or secret codes. Mathematicians continue to search for larger and larger primes.© 2008 Pearson Addison-Wesley. All rights reserved5-1-21Mersenne Numbers and Mersenne PrimesFor n = 1, 2, 3, …, the Mersenne numbers are those generated by the formula2 1.nnM = -1) If n is composite, then Mn is composite2) If n is prime, then Mn may be prime or compositeThe prime values of Mn are called Mersenne primes.© 2008 Pearson Addison-Wesley. All rights reserved5-1-22Example: Mersenne Numbers Find the Mersenne number for n = 5.SolutionM 5 = 2 5 – 1 = 32 – 1 = 31© 2008 Pearson Addison-Wesley. All rights reserved5-1-23Fermat NumbersThe Fermat numbers are generated by the formula22 1.n+The first five Fermat numbers (through n = 4) are prime.© 2008 Pearson Addison-Wesley. All rights reserved5-1-24Euler’s and Escott’s Formulas for Finding PrimesEuler’s prime number formula first fails at n = 41:Escott’s prime number formula first fails at n = 80:241n n- +279 1601n n-