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

# MATH135 lecture 4.docx

2 Pages
77 Views

School
University of Waterloo
Department
Mathematics
Course
MATH 135
Professor
Janelle Resch
Semester
Fall

Description
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

OR

Don't have an account?

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.