Try the Free Math Solver or Scroll down to Resources!

Enter expression, e.g. (x^2-y^2)/(x-y)

Enter expression, e.g. x^2+5x+6

Enter expression, e.g. (x+1)^3

Enter a set of expressions, e.g. ab^2,a^2b

Enter equation to solve, e.g. 2x+3=4

Enter equation to graph, e.g. y=3x^2-1

Depdendent Variable

Number of equations to solve:

Equ. #1:

Equ. #2:

Equ. #3:

Equ. #4:

Equ. #5:

Equ. #6:

Equ. #7:

Equ. #8:

Equ. #9:

Solve for:

Enter inequality to solve, e.g. 2x+3>4

Enter inequality to graph, e.g. y<3x^2-1

Dependent Variable

Number of inequalities to solve:

Ineq. #1:

Ineq. #2:

Ineq. #3:

Ineq. #4:

Ineq. #5:

Ineq. #6:

Ineq. #7:

Ineq. #8:

Ineq. #9:

Solve for:

Math solver on your site

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.