Number Theory CSE235 Number Theory Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics 1 1 Sections 2 4 2 6 of Rosen Introduction I Number Theory CSE235 When talking about division over the integers we mean division with no remainder Definition Let a b Z a 6 0 we say that a divides b if there exists c Z such that b ac We denote this a b and a b when a does not divide b When a b we say a is a factor of b Theorem Let a b c Z then 2 1 1 If a b and a c then a b c 2 If a b then a bc for all c Z 3 If a b and b c then a c Introduction II Number Theory CSE235 Corollary If a b c Z such that a b and a c then a mb nc for n m Z 3 1 Division Algorithm I Number Theory CSE235 Let a be an integer and d be a positive integer Then there are unique integers q and r with 0 r d such that a dq r Not really an algorithm traditional name Further a is called the divident d is called the divisor q is called the quotient r is called the remainder and is positive 4 1 Primes I Number Theory CSE235 Definition A positive integer p 1 is called prime if its only positive factors are 1 and p If a positive integer is not prime it is called composite 5 1 Primes II Number Theory CSE235 Theorem Fundamental Theorem of Arithmetic FTA Every positive integer n 1 can be written uniquely as a prime or as the product of the powers of two or more primes written in nondecreasing size That is for every n Z n 1 can be written as n p 1 k 1 p 2 k 2 pl k l where each pi is a prime and each ki 1 is a positive integer 6 1 Sieve of Eratosthenes Preliminaries Number Theory CSE235 Given a positive integer n 1 how can we determine if n is prime or not For hundreds of years people have developed various tests and algorithms for primality testing We ll look at the oldest and most inefficient of these Lemma If n is a composite integer then n has a prime divisor x 7 1 n Sieve of Eratosthenes Preliminaries Number Theory CSE235 8 1 Proof Sieve of Eratosthenes Preliminaries Number Theory CSE235 9 1 Proof Let n be a composite integer Sieve of Eratosthenes Preliminaries Number Theory CSE235 Proof Let n be a composite integer By definition n has a prime divisor a with 1 a n thus n ab 10 1 Sieve of Eratosthenes Preliminaries Number Theory CSE235 Proof Let n be a composite integer By definition n has a prime divisor a with 1 a n thus n ab Its easy to see that either a n or b n Otherwise if on the contrary a n and b n then ab n n n 11 1 Sieve of Eratosthenes Preliminaries Number Theory CSE235 Proof Let n be a composite integer By definition n has a prime divisor a with 1 a n thus n ab Its easy to see that either a n or b n Otherwise if on the contrary a n and b n then ab n n n Finally either a or b is prime divisor or has a factor that is a prime divisor by the Fundamental Theorem of Arithmetic thus n has a prime divisor x n 12 1 Sieve of Eratosthenes Algorithm Number Theory CSE235 This result gives us an obvious algorithm To determine if a number n is prime we simple must test every prime number p with 2 p n Sieve 1 2 3 4 Input A positive integer n 4 Output true if n is prime foreach prime number p 2 p n do if p n then output false end 5 end 6 output true Can be improved by reducing the upper bound to 13 1 iteration q n p at each Sieve of Eratosthenes Efficiency Number Theory CSE235 This procedure called the Sieve of Eratosthenes is quite old but works In addition it is very inefficient At first glance this may seem counter intuitive 14 1 Sieve of Eratosthenes Efficiency Number Theory CSE235 This procedure called the Sieve of Eratosthenes is quite old but works In addition it is very inefficient At first glance this may seem counter intuitive The outer for loop runs for every prime p 15 1 n Sieve of Eratosthenes Efficiency Number Theory CSE235 This procedure called the Sieve of Eratosthenes is quite old but works In addition it is very inefficient At first glance this may seem counter intuitive The outer for loop runs for every prime p n Assume that we get such a list for free The loop still executes about n ln n times see distribution of primes next topic also Theorem 5 page 157 16 1 Sieve of Eratosthenes Efficiency Number Theory CSE235 This procedure called the Sieve of Eratosthenes is quite old but works In addition it is very inefficient At first glance this may seem counter intuitive The outer for loop runs for every prime p n Assume that we get such a list for free The loop still executes about n ln n times see distribution of primes next topic also Theorem 5 page 157 Assume also that division is our elementary operation 17 1 Sieve of Eratosthenes Efficiency Number Theory CSE235 This procedure called the Sieve of Eratosthenes is quite old but works In addition it is very inefficient At first glance this may seem counter intuitive The outer for loop runs for every prime p n Assume that we get such a list for free The loop still executes about n ln n times see distribution of primes next topic also Theorem 5 page 157 Assume also that division is our elementary operation Then the algorithm is O n 18 1 Sieve of Eratosthenes Efficiency Number Theory CSE235 This procedure called the Sieve of Eratosthenes is quite old but works In addition it is very inefficient At first glance this may seem counter intuitive The outer for loop runs for every prime p n Assume that we get such a list for free The loop still executes about n ln n times see distribution of primes next topic also Theorem 5 page 157 Assume also that division is our elementary operation Then the algorithm is O n However what is the actual input size 19 1 Sieve of Eratosthenes Efficiency Number Theory CSE235 20 1 Recall that it is log n Thus the algorithm runs in exponential time with respect to the input size Sieve of Eratosthenes Efficiency Number Theory CSE235 Recall that it is log n Thus the algorithm runs in exponential time with respect to the input size To see this let k log n 21 1 Sieve of Eratosthenes Efficiency Number Theory CSE235 Recall that it is log n Thus …
View Full Document
Unlocking...