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