Try the Free Math Solver or Scroll down to Resources!

 Depdendent Variable

 Number of equations to solve: 23456789
 Equ. #1:
 Equ. #2:

 Equ. #3:

 Equ. #4:

 Equ. #5:

 Equ. #6:

 Equ. #7:

 Equ. #8:

 Equ. #9:

 Solve for:

 Dependent Variable

 Number of inequalities to solve: 23456789
 Ineq. #1:
 Ineq. #2:

 Ineq. #3:

 Ineq. #4:

 Ineq. #5:

 Ineq. #6:

 Ineq. #7:

 Ineq. #8:

 Ineq. #9:

 Solve for:

 Please use this form if you would like to have this math solver on your website, free of charge. Name: Email: Your Website: Msg:

# 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.