Chapter 14 Number Theory Number theory is the study of the integers. Why anyone would want to study the integers is not immediately obvious. First of all, what’s to know? There’s 0, there’s 1, 2, 3, and so on, and, oh yeah, -1, -2, . . . . Which one don’t you understand? Sec-ond, what practical value is there in it? The mathematician G. H. Hardy expressed pleasure in its impracticality when he wrote: [Number theorists] may be justified in rejoicing that there is one sci-ence, at any rate, and that their own, whose very remoteness from or-dinary human activities should keep it gentle and clean. Hardy was specially concerned that number theory not be used in warfare; he was a pacifist. You may applaud his sentiments, but he got it wrong: Number Theory underlies modern cryptography, which is what makes secure online com-munication possible. Secure communication is of course crucial in war —which may leave poor Hardy spinning in his grave. It’s also central to online commerce. Every time you buy a book from Amazon, check your grades on WebSIS, or use a PayPal account, you are relying on number theoretic algorithms. 14.1 Divisibility Since we’ll be focussing on properties of the integers, we’ll adopt the default con-vention in this chapter that variables range over integers, Z. The nature of number theory emerges as soon as we consider the divides relation a divides b iff ak = b for some k. The notation, a | b, is an abbreviation for “a divides b.” If a | b, then we also say that b is a multiple of a. A consequence of this definition is that every number divides zero. This seems simple enough, but let’s play with this definition. The Pythagore-ans, an ancient sect of mathematical mystics, said that a number is perfect if it equals 273274 CHAPTER 14. NUMBER THEORY the sum of its positive integral divisors, excluding itself. For example, 6 = 1 +2 + 3 and 28 = 1 + 2 + 4 + 7 + 14 are perfect numbers. On the other hand, 10 is not perfect because 1 + 2 + 5 = 8, and 12 is not perfect because 1 + 2 + 3 + 4 + 6 = 16. Euclid characterized all the even perfect numbers around 300 BC. But is there an odd perfect number? More than two thousand years later, we still don’t know! All numbers up to about 10300 have been ruled out, but no one has proved that there isn’t an odd perfect number waiting just over the horizon. So a half-page into number theory, we’ve strayed past the outer limits of human knowledge! This is pretty typical; number theory is full of questions that are easy to pose, but incredibly difficult to answer. Interestingly, we’ll see that computer scientists have found ways to turn some of these difficulties to their advantage. Don’t Panic —we’re going to stick to some relatively benign parts of number theory. We rarely put any of these super-hard unsolved problems on exams :-) 14.1.1 Facts About Divisibility The lemma below states some basic facts about divisibility that are not difficult to prove: Lemma 14.1.1. The following statements about divisibility hold. 1. If a | b, then a | bc for all c. 2. If a | b and b | c, then a | c. 3. If a | b and a | c, then a | sb + tc for all s and t. 4. For all c = 0� , a | b if and only if ca | cb. Proof. We’ll prove only part 2.; the other proofs are similar. Proof of 2.: Since a | b, there exists an integer k1 such that ak1 = b. Since b | c, there exists an integer k2 such that bk2 = c. Substituting ak1 for b in the second equation gives (ak1)k2 = c. So a(k1k2) = c, which implies that a | c. � A number p > 1 with no positive divisors other than 1 and itself is called a prime. Every other number greater than 1 is called composite. For example, 2, 3, 5, 7, 11, and 13 are all prime, but 4, 6, 8, and 9 are composite. Because of its special properties, the number 1 is considered to be neither prime nor composite.275 14.1. DIVISIBILITY Famous Problems in Number Theory Fermat’s Last Theorem Do there exist positive integers x, y, and z such that x n + y n = z n for some integer n > 2? In a book he was reading around 1630, Fermat claimed to have a proof, but not enough space in the margin to write it down. Wiles finally gave a proof of the theorem in 1994, after seven years of working in secrecy and isolation in his attic. His proof did not fit in any margin. Goldbach Conjecture Is every even integer greater than two equal to the sum of two primes? For example, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, etc. The conjecture holds for all numbers up to 1016. In 1939 Schnirelman proved that every even number can be written as the sum of not more than 300,000 primes, which was a start. Today, we know that every even number is the sum of at most 6 primes. Twin Prime Conjecture Are there infinitely many primes p such that p + 2 is also a prime? In 1966 Chen showed that there are infinitely many primes p such that p + 2 is the product of at most two primes. So the conjecture is known to be almost true! Primality Testing Is there an efficient way to determine whether n is prime? A naive search for factors of n takes a number of steps proportional to √n, which is exponential in the size of n in decimal or binary notation. All known procedures for prime checking blew up like this on various inputs. Finally in 2002, an amazingly simple, new method was discovered by Agrawal, Kayal, and Saxena, which showed that prime testing only required a polynomial number of steps. Their paper began with a quote from Gauss emphasizing the importance and antiquity of the problem even in his time— two centuries ago. So prime testing is definitely not in the category of infeasible problems requiring an exponentially growing number of steps in bad cases. Factoring Given the product of two large primes n = pq, is there an efficient way to recover the primes p and q? The best known algorithm is the “number field sieve”, which runs in time proportional to: 1.9(ln n)1/3(ln ln n)2/3 e This is infeasible when n has 300 digits or more.276 CHAPTER 14. NUMBER THEORY 14.1.2 When Divisibility Goes Bad As you learned in elementary school, if one number does not evenly divide an-other, you get a “quotient” and a “remainder” left over. More precisely: Theorem 14.1.2 (Division Theorem). 1 Let n and d be integers such that d > 0. Then there exists a unique pair of integers q and r, such that n = q d + r AND 0 …
View Full Document
Unlocking...