MATH135 Lecture Notes - Lecture 4: One Direction, Euclidean Algorithm, And1

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: Gabrielde Morais Coutinho

Document Summary

University of waterloo - fall 2014 - math 135. Suppose a and b are integers, at least one di erent than 0. Compute gcd(24, 30), gcd( 15, 10), gcd(9, 16), gcd(0, 29), gcd(0, 0). The gcd of integers a and b exists and is unique. Let s be the set of all integers that divide both a and b. The set s is non-empty because it always contains 1. Also, if c s, then by bounds of divisibility, |c| |a| and |c| |b|. So s contains a nite number of integers. Let d be the largest element of s. then d | a, d | b, and if c divides both a and b, c d. therefore d = gcd(a, b). If a and b are non-zero integers, and a = qb + r, then gcd(a, b) = gcd(b, r). Suppose d s. then d | a and d | b. Note that r = a q b.