GCD,LCM,Division and Euclidean Algorithms
Definition 7.1. Let A,B ∈ N
LCM: The least common multiple of A and B,
LCM(A,B), is the smallest M such that A|M
GCD: The greatest common divisor of A and
B, GCD(A,B), is the largest D such that
D|A and D|B.
Examples (and finding LCM, GCD using Fund.
Thm. of Arith.)
Remember the Division Algorithm:
Lemma 7.1. Suppose a and d are positive integers;
then there are unique k, r ∈ N such that
a = kd + r and 0 ≤ r < d
Proof. ‘Sketch’ in class.
Lemma 7.2. Suppose a, k, d, r ∈ N and a =
kd + r. Then GCD(a, d)=GCD(d, r)
Proof. Every common divisor of a and d is also a
divisor of a−kd (why?), which is r. Every common
divisor of d and r is also a divisor of kd+r (why?),
which is a. Thus the largest common divisor of a
and d must be the largest common divisor of d and
This lemma has remarkable consequences if we
iterate the Division Algorithm. For example:
100 = (70)(1) + 30
70 = (30)(2) + 10
30 = (10)(3) + 0
At this point we have to stop, but see:
GCD(100, 70) = GCD(70, 30) = GCD(30, 10) = 10
This procedure for finding the GCD of two positive
integers is called the Euclidean Algorithm.