MagicMath.com Logo
MagicMath Homepage
Middle School Homepage
To simpliey a fraction,
a/b, you compute
the gcf or gcd
gcd(a, b) = c
If c = 1
then a/b
is already in lowest terms. Otherwise, the simplified fraction is
then the simplified fraction is
(a/c) / (b/c)
The method taught in most middle schools for computing the gcd is
the tree of factors method. But a more systematic method
is the Eulidean Algorithm which computes remainders
repeatedly to obtain the gcd. For example,
gcd ( 2970, 1265 )
follows this sequence of remainder (r
)
computations:
step
a
b
r
1 2970 1265 440
2 1265 440 385
3 440 385 55
4 385 55 0
When the remainder becomes zero, the value in colum
b
is the gcd. This algorithm, or step by step procedure, is
credited to Euclid, a Greek mathematician (ca. 300 B.C.).
Even the fastest modern gcd algorithms used on digital computers are
based on the same principle.
Challenge:
Let a
and
b
be integers, not both zero.
Prove that if any integer
k
divides both
a
and
b
, then
k
must divide
gcd(a, b)
.
The lcm of a
and
b
, is easy to derive once
gcd(a, b) = c
is computed:
lcm(a, b) = a × (b/c)
Challenge: Figure out how to compute the lcm of several integers
by computing their gcd first.
Use the computation capabilities on the fractions page
to help you experiment with your ideas.
Copyright © MagicMath Inc., Ohio USA, 2000