ECE103 Study Guide - Midterm Guide: Coprime Integers, Asteroid Family, Extended Euclidean Algorithm

• School: University of Waterloo
• Department: Electrical and Computer Engineering
• Course: ECE103
• Professor: Martin Pei

Document Summary

The algorithm terminates when a remainder of zero is obtained. The output from the algorithm is the last nonzero remainder rn and rn, is the gcd(r1, r2). The good characterization theorem: let a and b be integers, not both zero. Let e be any common divisor of a and b. Since e|a and e|b, e|(ax + by) by. Since g is positive, proposition 2. 1. 2(iii) implies e g. Since g is a common divisor of a and b, and no common divisor exceeds it, g = gcd( b). Note: 1) to use gct in proofs where g is given find any x and y that satisfies integer combination and divides a and b. Example: prove that gcd(b, b + 1) = 1. By observation, x=-1 and y=1 satisfies the integer combination of xb + y(b+1) = 1. Since 1|b and 1|b+1, by good characterization gcd(b, b+1) = 1.