Try the Free Math Solver or Scroll down to Resources!

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


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
and B|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
r

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.