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

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

3 Pages
Unlock Document

MATH 135
Yu- Ru Liu

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


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.