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