《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

Number Theory I Die Hard 5: Die of Old Age Bruce must save his assisted living facility from a criminal mastermind by forming 2 gallons with 899 and 1147 gallon jugs Die Hard 6: Die Once and For All Bruce has to make 4 gallons using 3 and 6-gallon jugs It would be nice if we could solve all these silly water jug questions at once. In particular, how can one form g gallons using jugs with capacities a and b? Thats where number theory comes in handy 3.1 Finding an Invariant Property Suppose that we have water jugs with capacities a and b. Let's carry out a few arbitrary operations and see what happens. The state of the system at each step is described below with a pair of numbers(a, y), where r is the amount of water in the jug with capacity a and y is the amount in the jug with capacity b fill first jug pour first into second fill first jug (2a-b,b) pour first into second →(2a-b,0) emt jug →(0,2a pour first into second b) fill first pour first into second Of course, were making some assumptions about the relative capacities of the two jugs here. But another point leaps out: at every step, the amount of water in each jug is of the s·a+t·b for some integers s and t. An expression of this form is called a linear combination of a and b. This sounds like an assertion that we might be able to prove by induction Lemma 3. Suppose that we have water jugs with capacities a and b. Then the amount of water in each jug is always a linear combination of a and b Proof. We use induction. Let P(n) be the proposition that after n steps, the amount of water in each jug is a linear combination of a and b Base case. P(O)is true, because both jugs are initially empty, and0.a+0-6=0 Inductive step. Now we must show that P(n) implies P(n +1) for n >0. So assume that after n steps the amount of water in each jug is a linear combination of a and b. There ar two cases

6 Number Theory I Die Hard 5: Die of Old Age Bruce must save his assisted living facility from a criminal mastermind by forming 2 gallons with 899 and 1147 gallon jugs. Die Hard 6: Die Once and For All Bruce has to make 4 gallons using 3 and 6­gallon jugs. It would be nice if we could solve all these silly water jug questions at once. In particular, how can one form g gallons using jugs with capacities a and b? That’s where number theory comes in handy. 3.1 Finding an Invariant Property Suppose that we have water jugs with capacities a and b. Let’s carry out a few arbitrary operations and see what happens. The state of the system at each step is described below with a pair of numbers (x, y), where x is the amount of water in the jug with capacity a and y is the amount in the jug with capacity b. (0, 0) → (a, 0) fill first jug → (0, a) pour first into second → (a, a) fill first jug → (2a − b, b) pour first into second → (2a − b, 0) empty second jug → (0, 2a − b) pour first into second → (a, 2a − b) fill first → (3a − 2b, b) pour first into second Of course, we’re making some assumptions about the relative capacities of the two jugs here. But another point leaps out: at every step, the amount of water in each jug is of the form s a · · + t b for some integers s and t. An expression of this form is called a linear combination of a and b. This sounds like an assertion that we might be able to prove by induction! Lemma 3. Suppose that we have water jugs with capacities a and b. Then the amount of water in each jug is always a linear combination of a and b. Proof. We use induction. Let P(n) be the proposition that after n steps, the amount of water in each jug is a linear combination of a and b. Base case. P(0) is true, because both jugs are initially empty, and 0 · · a + 0 b = 0. Inductive step. Now we must show that P(n) implies P(n + 1) for n ≥ 0. So assume that after n steps the amount of water in each jug is a linear combination of a and b. There are two cases:

Number Theory I If we fill a jug from the fountain or empty a jug into the fountain, then that jug is empty or full. The amount in the other jug remains a linear combination of a and b So P(n+1)holds Otherwise, we pour water from one jug to another until one is empty or the other is full. By our assumption, the amount in each jug is a linear combination of a and b before we begin pouring j=81·a+t1:b j2=s2·a+t2·b After pouring, one jug is either empty(contains 0 gallons)or full(contains a or b gallons). Thus, the other jug contains either j 1 +j2 gallons, j1 +j2-a, or j1+32-b gallons, all of which are linear combinations of a and b The claim follows by the principle of induction. This theorem has an important corollar Corollary 4. Bruce dies Proof. In Die Hard 6, Bruce has water jugs with capacities 3 and 6 and must form 4 gallons of water. However, the amount in each jug is always of the form 3s+6t by Lemma 3. This is always a multiple of 3 by part ( 3)of Lemma 1, so he can not measure out 4 gallons. D Lemma 3 isnt very satisfying. We've just managed to recast a pretty understand able question about water jugs into a complicated question about linear combinations This might not seem like progress. Fortunately, linear combinations are closely related to something more familiar and that will help us solve the water jug problem 4 The greatest Common divisor The greatest common divisor of a and b is exactly what you'd guess: the largest number that is a divisor of both a and b. It is denoted gcd(a, b). For example, ged(18, 24)=6 Probably some junior high math teacher made you compute greatest common divi- sors for no apparent reason until you were blue in the face. But, amazingly, the greatest common divisor actually turns out to be quite useful for reasoning about the integers Specifically, the quantity ged(a, b) is a valuable piece of information about the relation ship between the numbers a and b. So we'll make arguments about greatest commor divisors all the time

Number Theory I 7 • If we fill a jug from the fountain or empty a jug into the fountain, then that jug is empty or full. The amount in the other jug remains a linear combination of a and b. So P(n + 1) holds. • Otherwise, we pour water from one jug to another until one is empty or the other is full. By our assumption, the amount in each jug is a linear combination of a and b before we begin pouring: j1 = s1 · a + t1 · b j2 = s2 · a + t2 · b After pouring, one jug is either empty (contains 0 gallons) or full (contains a or b gallons). Thus, the other jug contains either j1 + j2 gallons, j1 + j2 − a, or j1 + j2 − b gallons, all of which are linear combinations of a and b. The claim follows by the principle of induction. This theorem has an important corollary. Corollary 4. Bruce dies. Proof. In Die Hard 6, Bruce has water jugs with capacities 3 and 6 and must form 4 gallons of water. However, the amount in each jug is always of the form 3s+ 6t by Lemma 3. This is always a multiple of 3 by part (3) of Lemma 1, so he can not measure out 4 gallons. Lemma 3 isn’t very satisfying. We’ve just managed to recast a pretty understand￾able question about water jugs into a complicated question about linear combinations. This might not seem like progress. Fortunately, linear combinations are closely related to something more familiar and that will help us solve the water jug problem. 4 The Greatest Common Divisor The greatest common divisor of a and b is exactly what you’d guess: the largest number that is a divisor of both a and b. It is denoted gcd(a, b). For example, gcd(18, 24) = 6. Probably some junior high math teacher made you compute greatest common divi￾sors for no apparent reason until you were blue in the face. But, amazingly, the greatest common divisor actually turns out to be quite useful for reasoning about the integers. Specifically, the quantity gcd(a, b) is a valuable piece of information about the relation￾ship between the numbers a and b. So we’ll make arguments about greatest common divisors all the time

Number Theory I 4.1 Linear Combinations and the gcd The theorem below relates the greatest common divisor to linear combinations. This the- orem is very useful; take the time to understand it and then remember it! Theorem 5. The greatest common divisor of a and b is equal to the smallest positive linear com- bination of a and b For example, the greatest common divisor of 52 and 44 is 4. And, sure enough, 4 is a linear combination of 52 and 44 6·52+(-7)44=4 Furthermore, no linear combination of 52 and 44 is equal to a smaller positive integer Proof. Let m be the smallest positive linear combination of a and b. We'll prove that m gcd(a, b) by showing both gcd(a, b) <m and m gcd(a, b) First, we show that gcd(a, b)< m. By the definition of common divisor, ged(a, b)I a and ged(a, b)I b. Therefore, for every pair of integers s and t gcd(a, b) sa+tb Thus, in particular, ged(a, b) divides m, and so gcd(a,b)<m Now, we show that m s gcd(a, b). We do this by showing that m I a. A symmetri argument shows that m b, which means that m is a common divisor of a and b. Thus, m must be less than or equal to the greatest common divisor of a and b All that remains is to show that m a. by the division algorithm there exists a quo- tient g and remainder r such that: a= q ( where0≤r<m) Recall that m= sa+ to for some integers s and t. Subtituting in for m and rearranging terms gives (sa+tb)+r (1-gsa+(qt ) b Weve just expressed r as a linear combination of a and b. However, m is the smallest positive linear combination and 0 r<m. The only possibility is that the remainderr not positive; that is, r=0. This implies m a The proof notes that every linear combination of a and b is a multiple of gcd(a, b) Conversely, since gcd(a, b) is a linear combination of a and b, every multiple of gcd(a, b) s well. This establishes a corollary

8 Number Theory I 4.1 Linear Combinations and the GCD The theorem below relates the greatest common divisor to linear combinations. This the￾orem is very useful; take the time to understand it and then remember it! Theorem 5. The greatest common divisor of a and b is equal to the smallest positive linear com￾bination of a and b. For example, the greatest common divisor of 52 and 44 is 4. And, sure enough, 4 is a linear combination of 52 and 44: 6 · 52 + (−7) 44 = 4 · Furthermore, no linear combination of 52 and 44 is equal to a smaller positive integer. Proof. Let m be the smallest positive linear combination of a and b. We’ll prove that m = gcd(a, b) by showing both gcd(a, b) ≤ m and m ≤ gcd(a, b). First, we show that gcd(a, b) ≤ m. By the definition of common divisor, gcd(a, b) | a and gcd(a, b) | b. Therefore, for every pair of integers s and t: gcd(a, b) | sa + tb Thus, in particular, gcd(a, b) divides m, and so gcd(a, b) ≤ m. Now, we show that m ≤ gcd(a, b). We do this by showing that m | a. A symmetric argument shows that m | b, which means that m is a common divisor of a and b. Thus, m must be less than or equal to the greatest common divisor of a and b. All that remains is to show that m | a. By the Division Algorithm, there exists a quo￾tient q and remainder r such that: a = q m · + r (where 0 ≤ r < m) Recall that m = sa + tb for some integers s and t. Subtituting in for m and rearranging terms gives: a = q · (sa + tb) + r r = (1 − qs)a + (−qt)b We’ve just expressed r as a linear combination of a and b. However, m is the smallest positive linear combination and 0 ≤ r < m. The only possibility is that the remainder r is not positive; that is, r = 0. This implies m | a. The proof notes that every linear combination of a and b is a multiple of gcd(a, b). Conversely, since gcd(a, b) is a linear combination of a and b, every multiple of gcd(a, b) is as well. This establishes a corollary:

Number Theory I Corollary 6. Every linear combination of a and b is a multiple of ged (a, b)and vice versa Now we can restate the water jugs lemma in terms of the greatest common divisor Corollary 7. Suppose that we have water jugs with capacities a and b. Then the amount of water in each jug is always a multiple of gcd(a, b) For example, there is no way to form 4 gallons using 3 and 6 gallon jugs, because 4 not a multiple of gcd(3, 6)=3 4.2 Properties of the greatest Common Divisor We claimed that greatest common divisors are powerful tools for reasoning about the integers. So we'll often make use of some basic gcd facts Lemma 8. The following statements about the greatest common divisor hold 1. Every common divisor of a and b divides gcd(a, b 2. gcd(ka, kb)=k gcd(a, b) for all k>0 3. If gcd(a, b)=1 and gcd(a, c)=l, then gcd(a, bc)=1 4. If a bc and ged(a, b)=l, then a c 5. gcd(a, b)=gcd(b, a rem b) Here's the trick to proving these statements: translate the gcd world to the linear com bination world using Theorem 5, argue about linear combinations, and then translate back using Theorem 5 again Proof. We prove only parts(3)and (4) Proof of(3): The assumptions together with Theorem 5 imply that there exist integers , t, u, and u such that: sa+to= 1 a+ UC Multiplying these two equations giv (sa+tb)(ua +vc)=1 The left side can be rewritten as a(asu+btu +csu)+b- c(tu). This is a linear combination of a and bc that is equal to 1, so gcd(a, bc)=l by Theorem 5 Proof of(4): Theorem 5 says that gcd(ac, bc)is equal to a linear combination of ac and uc trivially and a I bc by assumption. Therefore, a divides every linear combination of ac and bc. In particular, a divides ged(ac, bc)=c. gcd(a, b)=c. The first equality uses part (2 )of this lemma, and the second uses the assumption that ged(a, b)

Number Theory I 9 Corollary 6. Every linear combination of a and b is a multiple of gcd(a, b) and vice versa. Now we can restate the water jugs lemma in terms of the greatest common divisor: Corollary 7. Suppose that we have water jugs with capacities a and b. Then the amount of water in each jug is always a multiple of gcd(a, b). For example, there is no way to form 4 gallons using 3 and 6 gallon jugs, because 4 is not a multiple of gcd(3, 6) = 3. 4.2 Properties of the Greatest Common Divisor We claimed that greatest common divisors are powerful tools for reasoning about the integers. So we’ll often make use of some basic gcd facts: Lemma 8. The following statements about the greatest common divisor hold: 1. Every common divisor of a and b divides gcd(a, b). 2. gcd(ka, kb) = k · gcd(a, b) for all k > 0. 3. If gcd(a, b) = 1 and gcd(a, c) = 1, then gcd(a, bc) = 1. 4. If a | bc and gcd(a, b) = 1, then a c | . 5. gcd(a, b) = gcd(b, a rem b). Here’s the trick to proving these statements: translate the gcd world to the linear com￾bination world using Theorem 5, argue about linear combinations, and then translate back using Theorem 5 again. Proof. We prove only parts (3) and (4). Proof of (3): The assumptions together with Theorem 5 imply that there exist integers s, t, u, and v such that: sa + tb = 1 ua + vc = 1 Multiplying these two equations gives: (sa + tb)(ua + vc) = 1 The left side can be rewritten as a ·(asu + btu + csv) + b c· (tv). This is a linear combination of a and bc that is equal to 1, so gcd(a, bc) = 1 by Theorem 5. Proof of (4): Theorem 5 says that gcd(ac, bc) is equal to a linear combination of ac and bc. Now a | ac trivially and a | bc by assumption. Therefore, a divides every linear combination of ac and bc. In particular, a divides gcd(ac, bc) = c · gcd(a, b) = c. The first equality uses part (2) of this lemma, and the second uses the assumption that gcd(a, b) = 1

Number T I Part (5)of the lemma is useful for quickly computing the greatest common divisor of two numbers. For example, we could compute the greatest common divisor of 1147 and 899 by repeatedly applying part(5) gcd(1247,899)=gcd(8991247rem899 gcd(248,899rem248 =155 gcd(155,248rem155) gcd(93, 155 rem 93) d(62 gcd(31, 62 rem 31) gcd(31,0) This is called Euclids algorithm. The last equation might look wrong but 31 is a divisor of both 31 and o since every integer divides o This calculation, together with Corollary 7, implies that there is no way to measure out 2 gallons of water using jugs with capacities 1247 and 899; we can only obtain multiples of 31 gallons. This is good news- Bruce won't even survive Die Hard 5 Let's see if Bruce can possibly make 3 gallons using 21 and 26-gallon jugs. First, we compute the greatest common divisorof 2l and 26 using Euclids algorithm: ged(26,21)=gcd(21,5)=gcd(5,1)=1 Now 3 is a multiple of 1, so we can t rule out the possibility that bruce can form 3 gallons On the other hand we don ' t know he can do it either 4.3 One Solution for All Water Jug Problems Can Bruce form 3 gallons using 21 and 26-gallon jugs? This question is not so easy to answer without some number theor Corollary 6 says that 3 can be written as a linear combination of 21 and 26, since 3 is a multiple of gcd(21, 26)=1. In other words, there exist integers s and t such that We dont know what the coefficients s and t are, but we do know that they exist

� �� � � �� � � �� � � �� � � �� � � �� � 10 Number Theory I Part (5) of the lemma is useful for quickly computing the greatest common divisor of two numbers. For example, we could compute the greatest common divisor of 1147 and 899 by repeatedly applying part(5): gcd(1247, 899) = gcd(899, 1247 rem 899) =248 = gcd(248, 899 rem 248) =155 = gcd(155, 248 rem 155) =93 = gcd(93, 155 rem 93) =62 = gcd(62, 93 rem 62) =31 = gcd(31, 62 rem 31) =0 = gcd(31, 0) = 31 This is called Euclid’s algorithm. The last equation might look wrong, but 31 is a divisor of both 31 and 0 since every integer divides 0. This calculation, together with Corollary 7, implies that there is no way to measure out 2 gallons of water using jugs with capacities 1247 and 899; we can only obtain multiples of 31 gallons. This is good news– Bruce won’t even survive Die Hard 5! Let’s see if Bruce can possibly make 3 gallons using 21 and 26­gallon jugs. First, we compute the greatest common divisorof 21 and 26 using Euclid’s algorithm: gcd(26, 21) = gcd(21, 5) = gcd(5, 1) = 1 Now 3 is a multiple of 1, so we can’t rule out the possibility that Bruce can form 3 gallons. On the other hand, we don’t know he can do it either. 4.3 One Solution for All Water Jug Problems Can Bruce form 3 gallons using 21 and 26­gallon jugs? This question is not so easy to answer without some number theory. Corollary 6 says that 3 can be written as a linear combination of 21 and 26, since 3 is a multiple of gcd(21, 26) = 1. In other words, there exist integers s and t such that: 3 = s · · 21 + t 26 We don’t know what the coefficients s and t are, but we do know that they exist