Notes Number Theory Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 3 4 3 6 of Rosen cse235 cse unl edu Introduction I Notes 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 Introduction II Let a b c Z then 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 Corollary If a b c Z such that a b and a c then a mb nc for n m Z Notes Division Algorithm I Notes Let a be an integer and d be a positive integer Then there are unique integers q and r with I 0 r d I such that a dq r Not really an algorithm traditional name Further I a is called the divident I d is called the divisor I q is called the quotient I r is called the remainder and is positive Primes I Notes 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 Notes 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 p1 k 1 p2 k 2 pl k l where each pi is a prime and each ki 1 is a positive integer Sieve of Eratosthenes Notes Preliminaries 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 n Sieve of Eratosthenes Notes Preliminaries Proof I Let n be a composite integer I 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 I I 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 Sieve of Eratosthenes Notes Algorithm 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 iteration q n p at each Sieve of Eratosthenes Notes Efficiency 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 I The outer for loop runs for every prime p I Assume that we get such a list for free The loop still executes about n ln n n times see distribution of primes next topic also Theorem 4 page 213 I Assume also that division is our elementary operation Then the algorithm is O n I However what is the actual input size I Sieve of Eratosthenes Notes Efficiency I Recall that it is log n Thus the algorithm runs in exponential time with respect to the input size I To see this let k log n I Then 2k n and so I n 2k 2k 2 Thus the Sieve is exponential in the input size k The Sieve also gives an algorithm for determining the prime factorization of an integer To date no one has been able to produce an algorithm that runs in sub exponential time The hardness of this problem is the basis of public key cryptography Sieve of Eratosthenes I Primality Testing Numerous algorithms for primality testing have been developed over the last 50 years In 2002 three Indian computer scientists developed the first deterministic polynomial time algorithm for primality testing running in time O log12 n M Agrawal and N Kayal and N Saxena Primes is in P Annals of Mathematics 160 2 781 793 2004 Available at http projecteuclid org Dienst UI 1 0 Summarize euclid annm 1111770735 Notes How Many Primes Notes How many primes are there Theorem There are infinitely many prime numbers The proof is a simple proof by contradiction How Many Primes Notes Proof Proof I Assume to the contrary that there are a finite number of primes p1 p2 pn I Let I By the FTA Q is either prime in which case we are done or Q can be written as the product of two or more primes I Thus one of the primes pj 1 j n must divide Q but then if pj Q it must be the case that Q p1 p2 pn 1 pj Q p1 p2 pn 1 I Since this is not possible we ve reached a contradiction there are not finitely many primes Distribution of Prime Numbers Theorem The ratio of the number of prime numbers not exceeding n and n ln n approaches 1 as n In other words for a fixed natural number n the number of primes not greater than n is about n ln n Notes Mersenne Primes I Notes A Mersenne prime is a prime number of the form 2k 1 where k is a positive integer They are related to perfect numbers if Mn is a Mersenne prime Mn M2 n 1 is perfect Perfect numbers are numbers that are equal to the sum of their proper factors for example 6 1 2 3 1 2 3 is perfect Mersenne Primes II Notes It is an open question as to whether or not there exist odd perfect numbers It is also an open question whether or not there exist an infinite number of Mersenne primes Such primes are useful in testing suites i e benchmarks for large super computers To date 42 Mersenne primes have been found The last was found on February 18th 2005 and contains 7 816 230 digits Division Notes Theorem The Division Algorithm Let a Z and d Z then there exists unique integers q r with 0 r d such that a dq r Some terminology I I I I d is called the divisor a is called the dividend q is called the quotient r is called the remainder We …
View Full Document
Unlocking...