NumberTheoryCSE235Number TheorySlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 2.4–2.6 of [email protected] / 1NumberTheoryCSE235Introduction IWhen talking about division over the integers, we meandivision with 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 doesnot divide b. When a | b, we say a is a factor of b.TheoremLet a, b, c ∈ Z then1If a | b and a | c then a | (b + c).2If a | b, then a | bc for all c ∈ Z.3If a | b and b | c, then a | c.2 / 1NumberTheoryCSE235Introduction IICorollaryIf a, b, c ∈ Z such that a | b and a | c then a | mb + nc forn, m ∈ Z.3 / 1NumberTheoryCSE235Division Algorithm ILet a be an integer and d be a positive integer. Then there areunique integers q and r, with:0 ≤ r ≤ dsuch that a = dq + rNot really an algorithm (traditional name). Further:a is called the dividentd is called the divisorq is called the quotientr is called the remainder, and is positive.4 / 1NumberTheoryCSE235Primes IDefinitionA positive integer p > 1 is called prime if its only positivefactors are 1 and p.If a positive integer is not prime, it is called com posite.5 / 1NumberTheoryCSE235Primes IITheorem (Fundamental Theorem of Arithmetic, FTA)Every positive integer n > 1 can be written uniquely as a primeor as the product of the powers of two or more primes writtenin nondecreasing 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 integer.6 / 1NumberTheoryCSE235Sieve of EratosthenesPreliminariesGiven a positive integer, n > 1, how can we determine if n isprime or not?For hundreds of years, people have developed various tests andalgorithms for primality testing. We’ll look at the oldest (andmost inefficient) of these.LemmaIf n is a composite integer, then n has a prime divisor x ≤√n.7 / 1NumberTheoryCSE235Sieve of EratosthenesPreliminariesProof.Let n be a composite integer.By definition, n has a prime divisor a with 1 < a < n, thusn = ab.Its easy to see that either a ≤√n or b ≤√n. Otherwise,if on the contrary, a >√n and b >√n, thenab >√n√n = nFinally, either a or b is prime divisor or has a factor that isa prime divisor by the Fundamental Theorem ofArithmetic, thus n has a prime divisor x ≤√n.8 / 1NumberTheoryCSE235Sieve of EratosthenesPreliminariesProof.Let n be a composite integer.By definition, n has a prime divisor a with 1 < a < n, thusn = ab.Its easy to see that either a ≤√n or b ≤√n. Otherwise,if on the contrary, a >√n and b >√n, thenab >√n√n = nFinally, either a or b is prime divisor or has a factor that isa prime divisor by the Fundamental Theorem ofArithmetic, thus n has a prime divisor x ≤√n.9 / 1NumberTheoryCSE235Sieve of EratosthenesPreliminariesProof.Let n be a composite integer.By definition, n has a prime divisor a with 1 < a < n, thusn = ab.Its easy to see that either a ≤√n or b ≤√n. Otherwise,if on the contrary, a >√n and b >√n, thenab >√n√n = nFinally, either a or b is prime divisor or has a factor that isa prime divisor by the Fundamental Theorem ofArithmetic, thus n has a prime divisor x ≤√n.10 / 1NumberTheoryCSE235Sieve of EratosthenesPreliminariesProof.Let n be a composite integer.By definition, n has a prime divisor a with 1 < a < n, thusn = ab.Its easy to see that either a ≤√n or b ≤√n. Otherwise,if on the contrary, a >√n and b >√n, thenab >√n√n = nFinally, either a or b is prime divisor or has a factor that isa prime divisor by the Fundamental Theorem ofArithmetic, thus n has a prime divisor x ≤√n.11 / 1NumberTheoryCSE235Sieve of EratosthenesPreliminariesProof.Let n be a composite integer.By definition, n has a prime divisor a with 1 < a < n, thusn = ab.Its easy to see that either a ≤√n or b ≤√n. Otherwise,if on the contrary, a >√n and b >√n, thenab >√n√n = nFinally, either a or b is prime divisor or has a factor that isa prime divisor by the Fundamental Theorem ofArithmetic, thus n has a prime divisor x ≤√n.12 / 1NumberTheoryCSE235Sieve of EratosthenesAlgorithmThis result gives us an obvious algorithm. To determine if anumber n is prime, we simple m ust te st every prime number pwith 2 ≤ 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.13 / 1NumberTheoryCSE235Sieve of EratosthenesEfficiency?This procedure, called the Sieve of Eratosthenes, is quite old,but works.In addition, it is very inefficient. At first glance, this may seemcounter intuitive.The outer for-loop runs for every prime p ≤√n.Assume that we get such a list for free. The loop stillexecutes about√nln√ntimes (see distribution of primes: next topic, also Theorem5, page 157).Assume also that division is our elementary operation.Then the algorithm is O(√n).However, what is the actual input size?14 / 1NumberTheoryCSE235Sieve of EratosthenesEfficiency?This procedure, called the Sieve of Eratosthenes, is quite old,but works.In addition, it is very inefficient. At first glance, this may seemcounter intuitive.The outer for-loop runs for every prime p ≤√n.Assume that we get such a list for free. The loop stillexecutes about√nln√ntimes (see distribution of primes: next topic, also Theorem5, page 157).Assume also that division is our elementary operation.Then the algorithm is O(√n).However, what is the actual input size?15 / 1NumberTheoryCSE235Sieve of EratosthenesEfficiency?This procedure, called the Sieve of Eratosthenes, is quite old,but works.In addition, it is very inefficient. At first glance, this may seemcounter intuitive.The outer for-loop runs for every prime p ≤√n.Assume that we get such a list for free. The loop stillexecutes about√nln√ntimes (see distribution of primes: next topic, also Theorem5, page 157).Assume also that division is our elementary operation.Then the algorithm is O(√n).However, what is the actual input size?16 / 1NumberTheoryCSE235Sieve of EratosthenesEfficiency?This procedure, called the Sieve of Eratosthenes, is quite old,but works.In addition, it is very inefficient. At first glance, this may seemcounter intuitive.The outer for-loop runs for every
View Full Document
Unlocking...