Class Notes (835,600)
Canada (509,275)
Mathematics (1,919)
MATH 135 (334)
Lecture

Euclidean Algorithm and Proposition 2.21 It's Yu-Ru, Liu, the best prof's note!

3 Pages
182 Views
Unlock Document

Department
Mathematics
Course
MATH 135
Professor
Yu- Ru Liu
Semester
Winter

Description
2.2 The Euclidean Algorithm Definition: Let a,b,d If d|a and d|b, we say d is a common divider of a and b. Definition2: Let a, b , not both 0. If d is the largest positive integer dividing both a and b, we say d is the greatest common divider of a and b, denoted by d=gcd(a,b). Ex: The common dividers of 45 and 75 are ± 1, ± 3, ± 5 and ± 15. Thus, gcd(45,75) = 15 Ex2: Claim gcd(3.0) = 3 - Dividers of 3 are ± 1, ± 3 - All integers are dividers of 0, (since 0=0 x a, Thus their common dividers are ± 1, ±3, and gcd(3,0)=3 We also have gcd(-3,0)=3 In general, for with a≠0, gcd(a,0) = a| Remark: To keep the above, we define gcd(0,0)=0, although 0 is NOT the largest common divider of 0 and 0. Ex: Prove that gcd(a,b) = gcd(5a+4b, a+b) Soln: If a=b=0, then gcd(a,b) = 0 = gcd(5a+4b, a+b). Thus we can assume now that a,b are not both 0. Let d = gcd(5a+4b, a+b). Since d|(5a+4b) and d|(a+b), by Prop2.1 (ii) d|(5a+4b) – 4(a+b), i.e. d|a Since d|(a+b) and d|a, by Prop2.11 (ii) d|(a+b) – a, i.e. d|b Thus d is a common dividor of a and b. Let e be any common divider of a and b. Since e|a and e|b, by Prop2.11 (ii) e|(5a+4b) and e|(a+b) Since e|(5a+4b), e|(a+b) and d = gcd(5a+4b, a+b), we have e ≤ d. Since d|a, d|b and d ≥ e for any common divider, e of a and b, we have d = gcd(a,b). Thus, gcd(a,b) = gcd(5a+4b, a+b) Proposition 2.21 If a=qb+r, then gcd(a,b) = gcd(b,r) Proof: If a=b=
More Less

Related notes for MATH 135

Log In


OR

Join OneClass

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

Sign up

Join to view


OR

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.


Submit