《Mathematics for Computer》Lecture 16 numtheory 1

6.042/18.] Mathematics for Computer Science February 17, 2005 Srini devadas and Eric Lehman Lecture notes Number Theory I Number theory is the study of the integers. Number theory is right at the core of math ematics; even Ug the Caveman surely had some grasp of the integers- at least the posi tive ones. In fact, the integers are so elementary that one might ask, What's to study? There's O, there's 1, 2,3 and so on, and there's the negatives. Which one dont you un derstand? Doesnt math become easy when we dont have to worry about nasty numbers like v7, 1/, and i? We can even forget about fractions All the variables in these notes represent integers 1 Divisibility The true nature of number theory emerges from the first definition. We say that a divides b if there is an integer k such that ak=b. This is denoted a b. For example 7|63 because7·9=63 A consequence of this definition is that every number divides zero since a0=0 for every integer a. If a divides b, then b is a multiple of a. For example, 63 is a multiple of 7 This seems simple enough, but let's play with this definition. The Pythagoreans,an ancient sect of mathemtical mystics, said that a number is perfect if it equals the sum positive integeral 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 10500 have been ruled out, but no one has proved that there isnt an odd perfect number waiting just over the horizon So a half-page into number theory, weve strayed past the outer limits of human knowl- edge. This is pretty typical; number theory is full of questions that are easy to pose, but incredibly difficult to answer. Interestingly, computer scientists have found ways to turn these difficulties to their advantage. 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 DONT PANIC-we're going to stick to some relatively benign parts of number theory We won't put any of these super-hard unsolved problems on exams

6.042/18.062J Mathematics for Computer Science February 17, 2005 Srini Devadas and Eric Lehman Lecture Notes Number Theory I Number theory is the study of the integers. Number theory is right at the core of math￾ematics; even Ug the Caveman surely had some grasp of the integers— at least the posi￾tive ones. In fact, the integers are so elementary that one might ask, “What’s to study?” There’s 0, there’s 1, 2, 3 and so on, and there’s the negatives. Which one don’t you un￾derstand? Doesn’t math become easy when we don’t have to worry about nasty numbers like √7, 1/π, and i? We can even forget about fractions! All the variables in these notes represent integers. 1 Divisibility The true nature of number theory emerges from the first definition. We say that a divides b if there is an integer k such that ak = b. This is denoted a | b. For example: 7 | 63 because 7 · 9 = 63 A consequence of this definition is that every number divides zero since a·0 = 0 for every integer a. If a divides b, then b is a multiple of a. For example, 63 is a multiple of 7. This seems simple enough, but let’s play with this definition. The Pythagoreans, an ancient sect of mathemtical mystics, said that a number is perfect if it equals the sum of its positive integeral 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 numbertheory, we’ve strayed past the outerlimits of human knowl￾edge. This is pretty typical; number theory is full of questions that are easy to pose, but incredibly difficult to answer. Interestingly, computer scientists have found ways to turn these difficulties to their advantage. 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. DON’T PANIC— we’re going to stick to some relatively benign parts of number theory. We won’t put any of these super­hard unsolved problems on exams!

2 Number Theory I 1.1 Facts about Divisibility The lemma below states some basic facts about divisibility that are not difficult to prove Lemma 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. Ifa b and a c, then a sb tc for all s and t For all+0, a b if and only if ca cb Proof. Well only prove parts(2 )and(4); the other proofs are similar Proof of (2): Since a b, there exists an integer ki such that ak1= b. Since b c, there exists an integer k2 such that bk2=c. Substituting aki for b in the second equation gives ckik2=c, which implies that a c. Proof of (4): We must show that a b implies ca cb and vice-versa First, suppose a b. This means ak b for some k Multiplying both sides by c gives cak= cb for some k. This implies ca cb c is nonzero, so ak b for some k. This means a/a can divide both sides by c since Now, suppose ca cb. Then cak= cb for some k. We A number p> l 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. The number 1 is considered neither prime nor composite. This is just a matter of definition but reflects the fact that 1 does not behave like a prime in many contexts such as the Fundamental Theorem of Arithmetic which we ll come to shortly 1.2 When Divisibility Goes Bad As you learned in elementary school, if one number does not evenly divide another, then there is a"remainder" left over. More precisely, if you divide n by d, then you get quotient q and a remainder r. This basic fact is the subject of a useful theorem Theorem 2 (Division Theorem). Let n and d be integers such that d >0. Then there exists a unique pair of integers q and r such that n= gd +r<r<d

� | 2 Number Theory I 1.1 Facts About Divisibility The lemma below states some basic facts about divisibility that are not difficult to prove: Lemma 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 only prove parts (2) and (4); 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 ak1k2 = c, which implies that a | c. Proof of (4): We must show that a | b implies ca cb | and vice­versa. • First, suppose a | b. This means ak = b for some k. Multiplying both sides by c gives cak = cb for some k. This implies ca | cb. • Now, suppose ca | cb. Then cak = cb for some k. We can divide both sides by c since c is nonzero, so ak = b for some k. This means a | b. 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. The number 1 is considered neither prime nor composite. This is just a matter of definition, but reflects the fact that 1 does not behave like a prime in many contexts, such as the Fundamental Theorem of Arithmetic, which we’ll come to shortly. 1.2 When Divisibility Goes Bad As you learned in elementary school, if one number does not evenly divide another, then there is a “remainder” left over. More precisely, if you divide n by d, then you get a quotient q and a remainder r. This basic fact is the subject of a useful theorem: Theorem 2 (Division Theorem). Let n and d be integers such that d > 0. Then there exists a unique pair of integers q and r such that n = qd + r and 0 ≤ r < d

Number Theory I Famous Problems in Number Theory Fermats Last Theorem Do there exist positive integers I, y, and z such that a"+y 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 solved the problem in 1994, after seven years of working in secrecy and isolation in his attic Goldbach Conjecture Is every even integer greater than or equal to 4 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 10. 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 ?An amazingly simple, yet efficient method was finally discovered in 2002 by graal, Kayal, and Saxena. Their paper began with a quote from Gauss em phasizing the importance and antiquity of the problem even in his time-two centuries ago 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 seive", which runs in time proportional to This is infeasible when n has a couple hundred digits or more

Number Theory I 3 Famous Problems in Number Theory Fermat’s Last Theorem Do there exist positive integers x, y, and z such that n n x + y n = z 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 solved the problem in 1994, after seven years of working in secrecy and isolation in his attic. Goldbach Conjecture Is every even integer greater than or equal to 4 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? An amazingly simple, yet efficient method was finally discovered in 2002 by Agrawal, Kayal, and Saxena. Their paper began with a quote from Gauss em￾phasizing the importance and antiquity of the problem even in his time— two centuries ago. 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 seive”, which runs in time proportional to: 1.9(ln n)1/3(ln ln n)2/3 e This is infeasible when n has a couple hundred digits or more

Number Theory I As an example, suppose that a= 10 and b= 2716. Then the quotient is q=271 and the emainder is r=6, since 2716=271.10+6 The remainder r in the division theorem is denoted n rem d. In other words, n rem d is the remainder when n is divided by d. For example, 32 rem 5 is the remainder when 32 is divided by 5, which is 2. Similarly, -ll rem 7=3, since-ll=(-2)7+3.There is a rem operator built into many programming languages. For example, the expression %5"evaluates to 2 in Java, C, and C++. However, all these languages treat negative numbers strangely There are a couple naming problems related to the Division Theorem. First, the the- orem is often called the"Division Algorithm", even though it is not an algorithm in the modern sense. Second, some people use the notation"mod"(which is short for"modulo") instead of"rem". This is unfortunate because" mod"has been used by mathematicians for centuries in a confusingly similar context, which we'll come to shortly. So we'll stick to rem here Were not going to prove the Division Theorem, but there is an important feature that you should notice. The theorem asserts that the quotient g and remainder r exist and also that these values are unique. Thus, the Division Theorem is one example of an"existence and uniqueness"theorem; there are many others. Not surprisingly, the proof of such a A proof that something exists, such as the quotient q and remainder a proof that nothing else fits the bill; that is, there is no other quotient q and re- mainy We'll prove a famous"existence and uniqueness "theor this way shortl

4 Number Theory I As an example, suppose that a = 10 and b = 2716. Then the quotient is q = 271 and the remainder is r = 6, since 2716 = 271 · 10 + 6. The remainder r in the Division Theorem is denoted n rem d. In other words, n rem d is the remainder when n is divided by d. For example, 32 rem 5 is the remainder when 32 is divided by 5, which is 2. Similarly, −11 rem 7 = 3, since −11 = (−2) 7 + 3 · . There is a rem operator built into many programming languages. For example, the expression “32 % 5” evaluates to 2 in Java, C, and C++. However, all these languages treat negative numbers strangely. There are a couple naming problems related to the Division Theorem. First, the the￾orem is often called the “Division Algorithm”, even though it is not an algorithm in the modern sense. Second, some people use the notation “mod” (which is short for “modulo”) instead of “rem”. This is unfortunate, because “mod” has been used by mathematicians for centuries in a confusingly similar context, which we’ll come to shortly. So we’ll stick to rem here. We’re not going to prove the Division Theorem, but there is an important feature that you should notice. The theorem asserts that the quotient q and remainder r exist and also that these values are unique. Thus, the Division Theorem is one example of an “existence and uniqueness” theorem; there are many others. Not surprisingly, the proof of such a theorem always has two parts: • A proof that something exists, such as the quotient q and remainder r. • A proof that nothing else fits the bill; that is, there is no other quotient q� and re￾mainder r� . We’ll prove a famous “existence and uniqueness” theorem in this way shortly

Number Theory I 2 Die hard Simon: On the fountain, there should be 2 jugs, do you see them? A 5-gallon and a 3-gallon. Fill one of the jugs with exactly 4 gallons of water and place it on the scale and the timer will stop. You must be precise; one ounce more or less will result in detonation. If you're still alive in 5 minutes, we'll speak Bruce: Wait, wait a second. I don' t get it. Do you get it? Samuel: No Bruce: Get the jugs. Obviously, we cant fill the 3-gallon jug with 4 gallons of rate Samuel: Obviously Bruce: All right. I know, here we go. We fill the 3-gallon jug exactly to the top, ght? Samuel: Uh-huh Bruce: Okay, now we pour this 3 gallons into the 5-gallon jug, giving us exactly lions in the 5-gallon jug, right? Samuel: Right, then what? Bruce: All right. We take the 3-gallon jug and fill it a third of the way. Samuel: No! He said, " Be precise. "Exactly 4 gallons Bruce: Shit. Every cop within 50 miles is running his ass off and I'm out here playing kids games in the park Samuel: Hey, you want to focus on the problem at hand? This is from the movie Die Hard 3: With a Vengeance. Samuel L Jackson and Bruce Willis have to disarm a bomb planted by the diabolical Simon Gruber. Fortunately, they find a solution in the nick of time.(No doubt reading the script helped ) On the surface, Die hard 3 is just a B-grade action movie; however, I think the inner message of the film is that everyone should learn at least a little number theory 3 Die once and for all Unfortunately, Hollywood never lets go of a gimmick. Theyre planning to keep the die Hard series going with Die Hard 4 Die Hardest Bruce goes on vacation and-shockingly--happens into a ter- rorist plot. To save the day, he must make 3 gallons using 21 and 26 gallon jugs

Number Theory I 5 2 Die Hard Simon: On the fountain, there should be 2 jugs, do you see them? A 5­gallon and a 3­gallon. Fill one of the jugs with exactly 4 gallons of water and place it on the scale and the timer will stop. You must be precise; one ounce more or less will result in detonation. If you’re still alive in 5 minutes, we’ll speak. Bruce: Wait, wait a second. I don’t get it. Do you get it? Samuel: No. Bruce: Get the jugs. Obviously, we can’t fill the 3­gallon jug with 4 gallons of water. Samuel: Obviously. Bruce: All right. I know, here we go. We fill the 3­gallon jug exactly to the top, right? Samuel: Uh­huh. Bruce: Okay, now we pour this 3 gallons into the 5­gallon jug, giving us exactly 3 gallons in the 5­gallon jug, right? Samuel: Right, then what? Bruce: All right. We take the 3­gallon jug and fill it a third of the way... Samuel: No! He said, “Be precise.” Exactly 4 gallons. Bruce: Shit. Every cop within 50 miles is running his ass off and I’m out here playing kids games in the park. Samuel: Hey, you want to focus on the problem at hand? This is from the movie Die Hard 3: With a Vengeance. Samuel L. Jackson and Bruce Willis have to disarm a bomb planted by the diabolical Simon Gruber. Fortunately, they find a solution in the nick of time. (No doubt reading the script helped.) On the surface, Die Hard 3 is just a B­grade action movie; however, I think the inner message of the film is that everyone should learn at least a little number theory. 3 Die Once and For All Unfortunately, Hollywood never lets go of a gimmick. They’re planning to keep the Die Hard series going with: Die Hard 4: Die Hardest Bruce goes on vacation and— shockingly— happens into a ter￾rorist plot. To save the day, he must make 3 gallons using 21 and 26 gallon jugs