Class Notes
(808,089)

Canada
(493,058)

University of Waterloo
(18,178)

Mathematics
(1,874)

MATH 135
(334)

Janelle Resch
(5)

Lecture 4

# MATH135 lecture 4.docx

Unlock Document

University of Waterloo

Mathematics

MATH 135

Janelle Resch

Fall

Description

MATH135 week 4 GCD (ctd), EEA, Uniqueness, GCD-CT Sept. 30 - Oct. 4, 2013
Recall: GCD with R if a,b,r,qEZ, a,b≠0
a=qb+r then gcd(a,b)=gcd(b,r)
*gcd(a,b)=d>0
d|a and d|b
c|a and c|b then c ≤ d
If we use this proposition (gcd with r) repeatedly we can compute large gcds.
Ex: gcd(1386, 322)
1386=(4)(322)+98
gcd(1386, 322)=gcd(322, 98)
322=(3)(98)+28
gcd(322, 98)=gcd(98, 28)
98=(3)(28)+14
gcd(98)(28)=gcd(28, 14)
28=(2)(14)+0
gcd(28, 14)=gcd(14, 0)=14
This process is known as the Euclidean Algorithm. But for large numbers, there can be
mistakes. We can see how accurate our solution is by the following proposition theorem:
GCD Characterization Theorem (GCD-CT)
∃
If d is a positive common divisor of the integers a and b and integers x and y so that
d=ax+by then gcd(a,b)=d
Proof: We want to show that d satisfies the definition of gcd(a,b). So from our hypothesis, we
know that
d|a and d|b (This is the first prof of the gcd definition)
Now, consider c|a and c|b (cEZ\{0})
By DIC, let x,yEZ and we can write c|(ax+by)
c|d (from hypothesis)
By BD, we can write c ≤ d (second part of definition)
Thus, gcd(a,b)=d by definition
Question: How do we find x and y?
The Extended Euclidean Algorithm (EEA)
EEA: given a,bEZ where a,b>0 (a>b>0)
The EEA is an efficient way to compute t

More
Less
Related notes for MATH 135