Number Theory CSE235 Number Theory Division Primes Division Modular Arithmetic Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics 1 30 Sections 3 4 3 6 of Rosen Introduction I Number Theory CSE235 Division Primes Division Modular Arithmetic 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 30 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 Division Primes Division Modular Arithmetic 3 30 Corollary If a b c Z such that a b and a c then a mb nc for n m Z Division Algorithm I Number Theory CSE235 Division Primes Division Modular Arithmetic 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 30 Primes I Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 5 30 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 Primes II Number Theory CSE235 Division Primes Sieve Distribution Interesting Items 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 Division Modular Arithmetic That is for every n Z n 1 can be written as n p1 k 1 p2 k 2 pl k l where each pi is a prime and each ki 1 is a positive integer 6 30 Sieve of Eratosthenes Preliminaries Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 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 30 n Sieve of Eratosthenes Preliminaries Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 8 30 Proof Sieve of Eratosthenes Preliminaries Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 8 30 Proof Let n be a composite integer Sieve of Eratosthenes Preliminaries Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 8 30 Proof Let n be a composite integer By definition n has a prime divisor a with 1 a n thus n ab Sieve of Eratosthenes Preliminaries Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 8 30 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 Sieve of Eratosthenes Preliminaries Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 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 8 30 Sieve of Eratosthenes Algorithm Number Theory CSE235 Division Primes 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 Sieve Distribution Interesting Items Division Modular Arithmetic 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 9 30 iteration q n p at each Sieve of Eratosthenes Efficiency Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 10 30 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 Sieve of Eratosthenes Efficiency Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 10 30 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 Sieve of Eratosthenes Efficiency Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 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 4 page 213 10 30 Sieve of Eratosthenes Efficiency Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 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 4 page 213 Assume also that division is our elementary operation 10 30 Sieve of Eratosthenes Efficiency Number Theory CSE235 Division Primes Sieve Distribution Interesting Items Division Modular Arithmetic 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 4 page 213 Assume also that division is our elementary operation Then the algorithm is O n 10 30 Sieve of Eratosthenes Efficiency Number Theory CSE235
View Full Document
Unlocking...