Return to Mat 417 Menu ,Home Page, Course Menu, Quarter Schedule, Grading Policy et. al.
Discussion
of the GCD and LCM Excerpted from draft of the full discussion.
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. |
COMMENTS:
Note: Division is a binary operation
over the real number system (function on
). Division is the rule of correspondence
that gives us instructions as to how to assign to each given ordered pairs
of numbers (a, b≠0)
a unique number c such that b*c=a. In the case of
, then a=b=q=1. The only restriction is that the divisor b cannot be zero as is proved in the Theorem 1 given below.
The Division
Algorithm is an extension of the division process that allows for a possible nonzero remainder. The Division Algorithm tells how many times c the divisor a can be subtracted from a number
b allowing the possibility of
there being a remainder r such that 0 ≤r< a.
Divides is a relation. A
relation is a Yes/No, True/False, etc. statement. We say that a
b is a true
statement whenever the division process of an integer b divided by a nonzero whole number a has a remainder of zero. If the remainder is not zero, then a does not divide b, we say that a and b are not related
and write 
. The end result is that a and b are
either related ( r=0) or they are not related (r≠0). There is no in between situation.
Example: We
say that 2|6 is
a true statement because the operation 6
2=3 has an integral solution.
We
say that 2|7 is not a true statement because
the operation 7
2 does not have an integral solution. In this case, we write 2
7. However, the Division Algorithm
says that 7=2*3 + 1 where b=2 is the divisor, a=7
the dividend, c=3 the quotient and r=1 is the remainder.
As
promised above, we now give the proof that is based solely on the definition of
division; namely, division by zero is undefined. It is not the case that division by zero is impossible by
the meaning of that term today. In
the early 1900's it was impossible for man to go to the moon, but it became
possible in 1968. It is not now
possible, nor will it ever be possible to divide by zero in the real number
system, because it cannot be defined in that system. There are number systems where there are zero divisors, i.e.
nonzero numbers whose product is zero, e.g. 2*3=9mod(6). Do not confuse the existence of zero
divisors with division by zero. They are two separate entities.
Theorem 1: Division by zero is undefined.
Proof:
Case i) b=0:
The expression
is not defined because there
is no unique number c
for which 0*c=0. It is the case
that 0*c=0 for all real numbers c by the zero property of
multiplication. So there is no
unique number c satisfying 0*c=0 because, (0*5)=(0*76)=(0*
)=(0*158)=0.
The expression
is undefined because there is no existence of a real number c for which c*0=b for any nonzero number b. By the same zero property of multiplication
as referenced above, 0*c=0 for all real numbers c.
So the division equation
is undefined because there is
no number c for which 0*c
is not zero.
Repeat: 0 is not
(cannot) be a divisor of any real number.
We need
the following definitions in order to discuss some very powerful properties of
the "divides" relation.
Definition: GCD(HCF)
‑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. (We define a common multiple and the LCM
below.)
Some
books refer to our greatest common divisor as the highest common factor. We
write gcd(a,b)=d and they write
hcf(a,b)=d. (A rose by any
other name would still smell as sweet so what does it matter what we call the
property?)
Examples: 5|35 and 5|75, because 5*7=35 and 3*52=75. We can use are tests for "divides" to see that no
smaller integer divides both numbers, so gcd(35,75)=5
gcd(4,6)= gcd(2 * 2, 2 x 3)= 2
gcd(36,45)= gcd(22 *
32, 32 * 52)=
9
gcd(18,21,33)= gcd(2 * 32 , 3 * 7, 3 * 11)=
3
Property of common
divisors and the gcd:
i) If d is any common divisor of two nonzero integers a and b, then
d|gcd(a,b).
Remark: The
gcd is used in reducing fractions to their lowest terms; eg.
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).
For example, 2|24 and 2|36, therefore, 2| 6 because the gcd(24,36)=6.
(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, that is negative b,
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.
The following is an alternate write-up of this same proof. Namely, whenever one integer divides
another integer, then it also divides the inverse of that integer.
|
|
·
·
·
·
·
|
We
should note that the proof of property ii) depends only on the closure property
of multiplication and the definition of divides.
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.
