Class Notes (808,089)
Canada (493,058)
Mathematics (1,874)
MATH 135 (334)
Lecture 4

MATH135 lecture 4.docx

2 Pages
Unlock Document

University of Waterloo
MATH 135
Janelle Resch

MATH135 week 4 GCD (ctd), EEA, Uniqueness, GCD-CT Sept. 30 - Oct. 4, 2013 Recall: GCD with R if a,b,r,qEZ, a,b≠0 a=qb+r then gcd(a,b)=gcd(b,r) *gcd(a,b)=d>0 d|a and d|b c|a and c|b then c ≤ d If we use this proposition (gcd with r) repeatedly we can compute large gcds. Ex: gcd(1386, 322) 1386=(4)(322)+98 gcd(1386, 322)=gcd(322, 98) 322=(3)(98)+28 gcd(322, 98)=gcd(98, 28) 98=(3)(28)+14 gcd(98)(28)=gcd(28, 14) 28=(2)(14)+0 gcd(28, 14)=gcd(14, 0)=14 This process is known as the Euclidean Algorithm. But for large numbers, there can be mistakes. We can see how accurate our solution is by the following proposition theorem: GCD Characterization Theorem (GCD-CT) ∃ If d is a positive common divisor of the integers a and b and integers x and y so that d=ax+by then gcd(a,b)=d Proof: We want to show that d satisfies the definition of gcd(a,b). So from our hypothesis, we know that d|a and d|b (This is the first prof of the gcd definition) Now, consider c|a and c|b (cEZ\{0}) By DIC, let x,yEZ and we can write c|(ax+by) c|d (from hypothesis) By BD, we can write c ≤ d (second part of definition) Thus, gcd(a,b)=d by definition Question: How do we find x and y? The Extended Euclidean Algorithm (EEA) EEA: given a,bEZ where a,b>0 (a>b>0) The EEA is an efficient way to compute t
More Less

Related notes for MATH 135

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.