Study Guides (248,485)
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

School
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
Me

OR

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.