Return to 417 Menu,Home Page, Course Menu, Quarter Schedule, Grading Policy et. al.
Discussion
of the GCD and LCM
Excerpted from draft.
The
following discussion is made to supplement our class activities and
discussions, not supplant them. Remember that division is an operation, divides
is a relation and the division algorithm extends the operation of division to
allow for nonzero remainders.
Also, remember that the following definitions generalize in tact by
replacing the word "integers" with "real numbers."
Definitions: (Be
sure you can write-out the definitions of the following terms, explain the
relationships that hold among them and can prove the properties that hold for
each.)
|
Division: For
any two integers a and b≠0,
we define We say that “b is a
divisor of a" or that" a is divided by b." We call b the divisor, a the dividend and c the
quotient with a zero remainder. Division is a binary operation over the real
number system that is a function on |
|
Divides :
For two integers a and b≠0,
we say that "b divides a" and
write If b divides
a, then we say that b is a factor of a and that a is a multipe of b. If no
such integer c exists, we say that "b does not divide a" and write "Divides"
defines a relation. Distinct
from a function or operation, a relation is a Yes/No, True/False, etc.
statement. We say that b The Division Algorithm below defines the process by
which we divide b into a, for any pair of integers a and b≠0 if b cannot be
repeatedly subtracted from a an
integral number of times. |
|
Division
Algorithm: For any pair of integers a and b≠0, there are unique integers q and r
for which a=b*q+r and 0 ≤r< b. The nonzero integer b is called the divisor; a is called the dividend, q
the quotient and r the
remainder. Symbolically we
write: " integers a and b≠0, $ ! integers q and r, The Division
Algorithm is the extension of the division process (a binary operation)
that allows for a nonzero
remainder. The Division
Algorithm tells how many times c
the divisor b can be subtracted
from a number a with a remainder
r such that 0 ≤r< a. |
The
following definitions are necessary to prove the properties as listed below of
the Divides Relation.
GCD: ‑Given any two integers, a nonzero
integer c such that c|a and c|b
is called a common divisor
(common factor) of a and b. If d is
the largest positive common divisor (common factor) of the two integers
a and b, then d
is called the greatest common divisor of a and b and
is denoted by gcd(a,b)=d. The GCD
is used in reducing fractions to lowest terms.
LCM: An integer n is called a common multiple of any two integers a and b if
n|a and n|b. If an
integer m is the smallest
positive common divisor, then m is
called the least common multiple. The LCM is called
the Least Common Denominator when is used to add unlike fractions.
Prime Number: A natural
number p greater than one is said
to be prime if it is divisible only by one and itself.
Relatively prime:
If 1 is the only positive
common divisor of any two integers a and
b, that is gcd(a,b)=1,
then a and b are said to be relatively prime. For example, gcd(15,28)=1 because
15 and 28 are not both divisible by any integer other than 1.
Properties of the
“Divides” relation:
i) If
c is any common divisor of two
integers a and b, then c|gcd(a,b). And
if n is any common multiple of of
the two integers, then m|n. Clearly, this property proves that the gcd(a,b) and
lcm(a,b) are unique because it says that both the gcd and lcm divide
themselves.
ii.) If a nonzero
integer a divides an integer b, then a
also divides the additive inverse 
b.
That is, a|b 
a|(
b). Inverses of equals are equal, so (a*c)=b for some
integer c implies that 
(a*c)=
b. And we know that 
(a*c)=( 
a)*c=a*(
c) by the uniqueness property of additive inverses, so we
also get that a|
b and 
a|
b, etc.
We
should note that the proof of property ii) depends only on the definition of
divides and the closure property of multiplication.
iii) If a
nonzero integer a divides integers b and c, then
a also divides the sum or difference
of b and c.
That is, if a|b and a|c,
then a|(b±c).
The
proof of property iii) utilizes the distributive property of multiplication
over addition and the definition of divides. (That is, by the definition of divides, 
integer r, s 
ar=b and as=c
that by the distributive property satisfies the equations
a(r±s)=ar±as=b±c which in turn satisfies the definition
for a to divide b±c.)
iv) If a nonzero
integer a divides an integer b and c is
any other integer, then a also
divides the product b*c. That
is, if a|b then a|(b*c),
for all integers c.
v) If a
nonzero integer d divides an
integer a and divides the sum or
difference of a multiple of a and
some integer r, then a is also a
divisor of r. This property is just a corollary of
the divides properties iii and iv given above. Namely, if d≠0, c and r are integers such that d|a and d|(ac+r), then
by property iii) above, d|(ac+r)–ac which
says that d|r.
There are seven standard models for fining the GCD and
LCM of two or more numbers. All
seven are discussed in the draft write-up along with their advantages and
disadvantages of using them at various grade levels.
The REPEATED DIVISION Models to find the GCD and LCM of two integers, a and
b≠0.
i.) GCD Case: The
Repeated Division model is called the Euclidean Algorithm when it is used
to find the gcd of two integers.
The Euclidean Algorithm:
If a and b are any integers. W.O.L.G. assume a>b, then
gcd(a,b)=gcd(r,b), where r is the
remainder when a is divided by b.
The Euclidean
Algorithm is just a repeated application of the Division Algorithm and the
Divides Property iii given earlier in this discussion. For an example, we find
the gcd(24,42),.
We first divide
the small of the two numbers into the larger number.
Find the first
Division Algorithm expression 42=1*(24)+18 by
dividing 24 into 42. Then
Find
the Division Algorithm expression 24=1*(18)+6 by dividing the
remainder 18 into the
divisor 24 (24<42. Repeat
Divide the
remainder 6 into the divisor 18 to see that 18=3*6 + 0.
We have to stop
when we get a zero remainder because division by zero is undefined.
By
working backwards applying the properties of the divides relation at each step,
we see that the last divisor that results in a zero remainder is then our
gcd. That is,
6|6
and 6|18, so 6| (6+18) 
6|24
6|18
and 6|24, so 6|(18+24) 
6|42.
gcd(24, 42)=6.
[If we solve for 6 at the last step,
[6=42-2*18,18=42-1*24, and substitute this in for 18, we get
[6=42-2*(42-1*24)=42-2*42+2*24, so
[6=(-1)42+48 gives us one example
of how 6 as the gcd can be written as a linear combination of of 24 and 42.
We can check that
there is no greater common divisor of 24 and 42 by referencing their prime
factorizations. Repeating, the gcd of any two numbers is the last divisor of
the Euclidean Algorithm process that gives us a zero remainder.
Reviewing what we
did, we get:
42 = 1*(24)+18
42=(18+6)+18=2*18+6 substitute first for 24, 24=1*(18)+6, then for
18, 18=3*6 + 0.
42 = 2*18+6=2(3*6)+6= (by
distributivity) 6*(2*3+1) =6(6+1)=6*7=42
Therefore, gcd(24, 42)=6.
By solving for the gcd(24, 42)=6 and working backwards, the process
enables you to find a set of integers s and t such that 6=s*24+t*42. Working with a generalized proof, one
sees that for every pair of integers a and b, then there exist integers s and t
such that gcd(a,b)=as+bt. There is
no claim of uniqueness for s and t.
Once one set of integers s and t that satisfy the equation, then
infinitely many others can be found by adding and subtracting a*b*k for all
integers k.
A condensed way of writing out the Euclidean Algorithm is given below.
Refer to original draft discussion for an explanation of the condensed LCM case
if it is not immediately obvious to you.
Examples:
|
|
Example of another way of
keeping track of the Euclidean Algorithm steps to find the gcd(117,522). |
Condensed version of Repeated Div Model to find |
|||||||
|
|
|
|
4 |
|
|
LCM(2,3,5,15) |
|||
|
|
|
117 |
522 |
----------- |
522 = 4*117+54 |
|
|
||
|
|
|
|
468 |
|
|
|
2 |
2,
3, 5, 15 |
|
|
|
|
|
54 |
117 |
------- |
117
= 4*54 + 9 |
3 |
1,
3, 5, 15 |
|
|
|
|
|
|
108 |
|
|
|
5 |
1,
1, 5, 5 |
|
|
|
|
|
9 |
54 54 |
|
|
|
1, 1, 1, 1 |
|
|
|
|
|
|
0 |
|
GCD(117, 522)=9 |
LCM(2,3,5,15)= |
|
Condensed
Summary of the Integer Divisibility Tests (A
complete write up with proofs of the following divisibility tests is given
in the Integers Divisibility Tests
discussion.)
a. An integer is divisible by 2, 5, or 10
if and only if its unit's digit is divisible by 2, 5, or 10, respectively.
b. An integer is divisible by 4 if and
only if the last 2 digits of the integer represent a number divisible by 4.
c. An integer is divisible by 8 if and
only if the last 3 digits of the integer represent a number divisible by 8.
d. An integer is divisible by 3 or by 9 if
and only if the sum of its digits is divisible by 3 or 9, respectively.
e. An integer is divisibility by 7 or
seven divides an integer if and only it 7 divides the result after you
repeatedly double and subtract.
You double the most rhs digit and subtract it from the remaining number
until you get a number that is obviously divisible or not divisible by 7.
f. An integer is
divisible by 11 if and only if the sum of the digits in the odd place value
columns minus the sum of the digits in the even place value columns is
divisible by 11.
Symbolically,11
|[(sum odd place value digits) – (sum even place value digits)]. This is often abbreviated as 11|[(sum
even) - (sum odd)] because if d|a, then d|(-a).
Note: a|b ®a|(-b), so odd-even or even-odd place value s does not
matter.
g. m
| n An integer n is
divisible by an integer m if and
only if n is divisible by all of the relatively
prime factors of m.
For
example, 6 divides an integer if and only if the integer is divisible by both
of the relatively prime factors 2 and 3.