Number TheorySlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 2.4–2.6 of [email protected] IWhen talking about division over the integers, we mean divisionwith no remainder.DefinitionLet a, b ∈ Z, a 6= 0, we say that a divides b if there exists c ∈ Zsuch that b = ac. We denote this, a | b and a - b when a does notdivide b. When a | b, we say a is a factor of b.TheoremNotesIntroduction IILet a, b, c ∈ Z then1. 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.CorollaryIf a, b, c ∈ Z such that a | b and a | c then a | mb + nc forn, m ∈ Z.NotesDivision Algorithm ILet a be an integer and d be a positive integer. Then there areunique integers q and r, with:I0 ≤ r ≤ dIsuch that a = dq + rNot really an algorithm (traditional name). Further:Ia is called the dividentId is called the divisorIq is called the quotientIr is called the remainder, and is positive.NotesPrimes IDefinitionA positive integer p > 1 is called prime if its only positive factorsare 1 and p.If a positive integer is not prime, it is called compos ite.NotesPrimes IITheorem (Fundamental Theorem of Arithmetic, FTA)Every positive integer n > 1 can be written uniquely as a prime oras the product of the powers of two or more primes written innondecreasing size.That is, for every n ∈ Z, n > 1, can be written asn = p1k1p2k2···plklwhere each piis a prime and each ki≥ 1 is a positive intege r.NotesSieve of EratosthenesPreliminariesGiven a positive integer, n > 1, how can we determine if n is primeor not?For hundreds of years, people have developed various tests andalgorithms for primality testing. We’ll look at the oldest (and mostinefficient) of these.LemmaIf n is a composite integer, then n has a prime divisor x ≤√n.NotesSieve of EratosthenesPreliminariesProof.ILet n be a composite integer.IBy definition, n has a prime divisor a with 1 < a < n, thusn = ab.IIts easy to see that either a ≤√n or b ≤√n. Otherwise, ifon the contrary, a >√n and b >√n, thenab >√n√n = nIFinally, either a or b is prime divisor or has a factor that is aprime divisor by the Fundamental Theorem of Arithmetic,thus n has a prime divisor x ≤√n.NotesSieve of EratosthenesAlgorithmThis result gives us an obvious algorithm. To determine if anumber n is prime, we simple must test every prime number p with2 ≤ p ≤√n.SieveInput : A positive integer n ≥ 4.Output : true if n is prime.foreach prime number p, 2 ≤ p ≤√n do1if p | n then2output false3end4end5output true6Can be improved by reducing the upper bound toqnpat eachiteration.NotesSieve of EratosthenesEfficiency?This procedure, called the Sieve of Eratosthenes, is quite old, butworks.In addition, it is very inefficient. At first glance, this may seemcounter intuitive.IThe outer for-loop runs for every prime p ≤√n.IAssume that we ge t s uch a list for free. The loop stillexecutes about√nln√ntimes (see distribution of primes: next topic, also Theorem 5,page 157).IAssume also that division is our elementary operation.IThen the algorithm is O(√n).IHowever, what is the actual input size?NotesSieve of EratosthenesEfficiency?IRecall that it is log (n). Thus, the algorithm runs inexponential time with respect to the input size.ITo see this, let k = log (n)IThen 2k= n and so√n =√2k= 2k/2IThus the Sieve is exponential in the input size k.The Sieve also gives an algorithm for determining the primefactorization of an integer. To date, no one has been able toproduce an algorithm that runs in sub-exponential time. Thehardness of this problem is the basis of public-key cryptography.NotesSieve of Eratosthenes IPrimality TestingNumerous algorithms for primality testing have been developedover the last 50 years.In 2002, three Indian computer scientists developed the firstdeterministic polynomial-time algorithm for primality testing,running in time O(log12(n)).M. Agrawal and N. Kayal and N. Saxena. Primes is in P. Annalsof Mathematics, 160(2):781-793, 2004.Available at http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.annm/1111770735NotesHow Many Primes?How many primes are there?TheoremThere are infinitely many prime numbers.The proof is a simple proof by contradiction.NotesHow Many Primes?ProofProof.IAssume to the contrary that there are a finite numbe r ofprimes, p1, p2, . . . , pn.ILetQ = p1p2···pn+ 1IBy the FTA, Q is either prime (in which case we are done) orQ can be written as the product of two or more primes.IThus, one of the primes pj(1 ≤ j ≤ n) must divide Q, butthen if pj| Q, it must be the c ase thatpj| Q −p1p2···pn= 1ISince this is not possible, we’ve reached acontradiction—there are not finitely many primes.NotesDistribution of Prime NumbersTheoremThe ratio of the number of prime numbers not exceeding n andnln napproaches 1 as n → ∞.In other words, for a fixed natural number, n, the number ofprimes not greater than n is aboutnln nNotesMersenne Primes IA Mersenne prime is a prime numbe r of the form2k− 1where k is a positive integer. They are related to perfect numbers(if Mnis a Mersenne prime,Mn(Mn+1)2is perfect).Perfect numbers are numbers that are equal to the sum of theirproper factors, for example 6 = 1 · 2 · 3 = 1 + 2 + 3 is p erfec t.NotesMersenne Primes IIIt is an open question as to whether or not there exist o dd perfectnumbers. It is also an open question whether or not there e xist aninfinite number of Mersenne primes.Such primes are useful in testing suites (i.e., be nchmarks) for largesuper computers.To date, 42 Mersenne primes have been found. The last was foundon February 18th, 2005 and contains 7,816,230 digits.NotesDivisionTheorem (The Division “Algorithm”)Let a ∈ Z and d ∈ Z+then there exists unique integers q, r with0 ≤ r < d such thata = dq + rSome terminology:Id is called the divisor.Ia is called the dividend.Iq is called the quotient.Ir is called the remainder.We use the following notation:q = a div dr = a mod dNotesGreatest Common Divisor IDefinitionLet a and b be integers not both zero. The largest integer d suchthat d | a and d | b is called the greatest common divisor of a andb. It is denotedgcd(a, b)The gcd is always guaranteed to exist since the set of commondivisors is finite. Recall that 1 is a divisor of any integer. Also,gcd(a, a) = a, thus1 ≤ gcd(a, b) ≤ min{a,
View Full Document
Unlocking...