MACM 101 Lecture Notes - Lecture 12: Euclidean Algorithm, Mathematical Induction
13 Aug 2016
School
Department
Course
Professor
Document Summary
Cameron has a lot of quarters and dimes with which to make change. How many different ways can he make change for (a) . 39 (b) . 45. Solution (a) since 5 doesn"t divide 139, its not possible for cameron to make change for . 39. (5|10 and 5|25 => 5|(10x + 25y) (b) Maybe use the most quarters: 5 quarters, 2 dimes. Now, 2 quarters = 5 dimes, so we can obtain 2 other solutions by swapping dimes for quarters. For a, b, d integers, if d|a and d|b then d is a common divisor. And if d satisfies: whenever c|a and c|b then c|d. If a, b are small, it is a fairly quick to find gcd(a,b) by trial and error/factor terms. Let a, b be intergers, a =/= 0. The gcd(a,b) equals the last nonzero remainder, r n, in the list of equations obtained from the division algorithm.
