Study Guides (248,485)
Canada (121,584)
Mathematics (302)
MATH 135 (50)
Midterm

Math 135 Algebra Notes IV (Sept 30 - Oct 11): Greatest Common Divisor, Extended Euclidean Algorithm, Properties of GCD

6 Pages
164 Views
Unlock Document

Department
Mathematics
Course
MATH 135
Professor
Wentang Kuo
Semester
Fall

Description
MATH 135: Algebra for Honours Mathematics Notes IV Michael Brock Li Computational Mathematics IA October MXIII Concordia Cum Veritate I: Greatest Common Divisor Continued Certi▯cate of Correction: in this case to check d to be gcd(a;b) when d comes from Euclidean Algorithm, we can use GCD CT to check. Example I: Computer gcd(1386;322). Solution: By EA, we get d = 14 = gcd(1386;322) 1386 = 99(14) 322 = 23(14) Thus, 14 is a common divisor of 1386 and 322. By reversing EA, (back substitution), we have 14 = 10 ▯ 1386 + (▯43)(322). Thus 14 is an integral combination of 1386 and 322. By GCD CT, 14 is indeed the gcd of 1386 and 322. Example II: Prove that gcd(x;y) = gcd(3x + 2y;x + y) Proof. 3x + 2y = 2(x + y) + x x + y = 1x + y By GCD WR, gcd(3x + 2y;x + y) = gcd(x;y) ▯ 1 II: Extended Euclidean Algorithm If a > b > 0 are integers, then d = gcd(a;b) can be found. There is also exists x;y 2 Z such that ax + by = d The algorithm to compute is long, but quite simple. Let’s try this out. Solve gcd(231;660). We get, a = 660 b = 231 660x + 231y = d In this case, we’ll do 660x + 231y = r where r is the remainder Formulas: The formula to ▯nd the quotient is ▯ ▯ ri▯2 qi= ri▯1 Constructing the next new row, we use the formula, Ri= R i▯2▯ qiRi▯1 where i is like the row number. Compute Rows: The ▯rst two rows will look like this x y ax+by q -q 1 0 660 0 1 231 Finding the next quotient, we get i = 3 as being the third row ▯ ▯ ▯ ▯ r1 660 q3= = = 2 r2 231 Constructing a new row, we get, R 3 R ▯ 1 R 3 2 R 3 R ▯12R 2 Thus, the table will look like 2 x y ax+by q -q 1 0 660 0 1 231 1 -2 198 2 -2 The next number of rows will use the same procedure until you reach r = 0, the ▯nish line. x y ax+by q -q 1 0 660 0 1 231 1 -2 198 2 -2 -1 3 33 1 -1 7 -20 0 6 -6 The second last row provides the desired d as the GCD, referring to ax + by column. The integers x;y will be the integer solutions to ▯nding d. Using the Certi▯cation of Correctness, we get, 660(▯1) + 231(3) = 33 Example I: x y ax+by q -q 1 0 1950 0 1 770 1 -2 410 2 -2 -1 3 360 1 -1 2 -5 50 1 -1 -15 38 10 7 -7 ▯15(1950) + 38(770) = 10. By GCD CT, 10 = gcd(1950;770) III: Properties of GCD Proposition: (GCD One) Let a;b 2 Z. Then gcd(a;b) = 1 if and only if there exists x;y 2 Z, ax+by = 1. Proof. "(" By GCD CT, if gcd(a;b) = 1 = d, then there exists x;y 2 Z such that ax + by = d = 1. ")" Since 1ja, 1jb, then 1 is a common divisor of a and b. By GCD CT, 1 = gcd(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