MTH 314 Lecture Notes - Lecture 6: Euclidean Algorithm, Linear Combination, Becquerel

• School: Ryerson University
• Department: Mathematics
• Course: MTH 314
• Professor: Konstantinos Georgiou

Document Summary

Joy of numbers tuesday, september 9: linear combinations. We recalled the euclidean algorithm from last class: let a and b be two integers (assume. Dividing b into a we get with 0 r1 < b. If r1 is not zero, we can divide r1 into b: a = bq1 + r1 with 0 r2 < r1. If r2 6= 0, we repeat the process: = r1q2 + r2 r1 = r2q3 + r3 with 0 r3 < r2. Eventually, we get down to a remainder of zero: rn 1 = rnqn+1 + 0. Megan explained that since the remainders are getting smaller and are always nonnegative, eventually we must reach a remainder of zero. In other words, since we have a sequence of nonnegative integers. The next homework problem was to explain why the last nonzero remainder in the eu- clidean algorithm is gcd(a, b). The answer is given by the theorem we proved on september.