Transcript a, b

Chapter
4
Number Theory
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
4-3 Greatest Common Divisor and
Least Common Multiple
Methods to Find the Greatest Common Divisor
Methods to Find the Least Common Multiple
Greatest Common Divisor
Two bands are to be combined to march in a
parade. A 24-member band will march behind a
30-member band. The combined bands must have
the same number of columns. Each column must
be the same size. What is the greatest number of
columns in which they can march?
Greatest Common Divisor
The bands could each march in 2 columns, and we
would have the same number of columns, but this
does not satisfy the condition of having the
greatest number of columns.
The number of columns must divide both 24 and 30.
Numbers that divide both 24 and 30 are 1, 2, 3,
and 6. The greatest of these numbers is 6.
Greatest Common Divisor
The first band would have 6 columns with 4
members in each column, and the second band
would have 6 columns with 5 members in each
column.
Definition
The greatest common divisor (GCD) or the
greatest common factor (GCF) of two whole
numbers a and b not both 0 is the greatest
whole number that divides both a and b.
Colored Rods Method
Find the GCD of 6 and 8 using the 6 rod and the
8 rod.
Colored Rods Method
Find the longest rod such that we can use multiples
of that rod to build both the 6 rod and the 8 rod.
The 2 rods can be used to build both the 6 and 8 rods.
Colored Rods Method
The 3 rods can be used to build the 6 rod but not
the 8 rod.
The 4 rods can be used to build the 8 rod but not the 6 rod.
The 5 rods can be used to build neither.
The 6 rods cannot be used to build the 8 rod.
Therefore, GCD(6, 8) = 2.
The Intersection-of-Sets Method
List all members of the set of whole number
divisors of the two numbers, then find the set of all
common divisors, and, finally, pick the greatest
element in that set.
The Intersection-of-Sets Method
To find the GCD of 20 and 32, denote the sets of
divisors of 20 and 32 by D20 and D32, respectively.
Because the greatest number in the set of common positive
divisors is 4, GCD(20, 32) = 4.
The Prime Factorization Method
To find the GCD of two or more non-zero whole
numbers, first find the prime factorizations of the
given numbers and then identify each common
prime factor of the given numbers. The GCD is the
product of the common factors, each raised to the
lowest power of that prime that occurs in any of the
prime factorizations.
Numbers, such as 4 and 9, whose GCD is 1 are
relatively prime.
Example 4-12
Find each of the following:
a. GCD(108, 72)
b. GCD(0, 13)
Because 13 | 0 and 13 | 13, GCD(0, 13) = 13.
Example 4-12
(continued)
c. GCD(x, y) if x = 23 · 72 · 11 · 13 and
y = 2 · 73 · 13 · 17
GCD(x, y) = 2 · 72 · 13 = 1274
d. GCD(x, y, z) if x = 23 · 72 · 11 · 13,
y = 2 · 73 · 13 · 17, and z = 22 · 7
GCD(x, y, z) = 2 · 7 = 14
e. GCD(x, y) if x = 54 · 1310 and y = 310 · 1120
Because x and y have no common prime factors,
GCD(x, y) = 1.
Calculator Method
Calculators with a Simp key can be used to find
the GCD of two numbers.
Find GCD(120, 180) by pressing the keys:
1
2
0
/
1
8
0
to obtain the display
N/D→n/d 60/90
Simp
=
Calculator Method
By pressing the x y key, we see 2 on the
display as a common divisor of 120 and 180.
By pressing the x
Simp
=
x
y
y key again and pressing
we see 2 again as a factor.
Repeat the process to see that 3 and 5 are other common
factors.
GCD(120, 180) is the product of the common prime factors
2 · 2 · 3 · 5, or 60.
Euclidean Algorithm Method
If a and b are any whole numbers greater than 0
and a ≥ b, then GCD(a, b) = GCD(r, b), where r is
the remainder when a is divided by b.
Finding the GCD of two numbers by repeatedly
using the theorem above until the remainder is 0 is
called the Euclidean algorithm.
Euclidean Algorithm Method
Example 4-13
Use the Euclidean algorithm to find
GCD(10764, 2300).
GCD(10764, 2300) = GCD(2300, 1564)
GCD(2300, 1564) = GCD(1564, 736)
Example 4-13
(continued)
GCD(2300, 1564) = GCD(1564, 736)
GCD(1564, 736) = GCD(736, 92)
GCD(736, 92) = GCD(92, 0) = 92
GCD(10764,2300) = GCD(92, 0) = 92
Euclidean Algorithm Method
A calculator with the integer division feature can
also be used to perform the Euclidean algorithm.
To find GCD(10764, 2300), proceed as follows:
The last number we divided by when we obtained the 0
remainder is 92, so GCD(10764, 2300) = 92.
Example 4-14a
Find GCD(134791, 6341, 6339).
Any common divisor of three numbers is also a common
divisor of any two of them.
The GCD of three numbers cannot be greater than the
GCD of any two of the numbers.
GCD(6341, 6339) = GCD(6341 − 6339, 6339)
= GCD(2, 6339) = 1
GCD(134791, 6341, 6339) cannot be greater than 1, so it
must equal 1.
Example 4-14b
Find the GCD of any two consecutive whole
numbers.
GCD(n, n + 1) = GCD(n + 1, n)
= GCD(n + 1 − n, n)
= GCD(1, n) = 1
The GCD of any two consecutive whole numbers is 1.
Least Common Multiple
Hot dogs are usually sold 10 to a package, while
hot dog buns are usually sold 8 to a package.
What is the least number of packages of each you
must buy so that there is an equal number of hot
dogs and buns?
The number of hot dogs is a multiple of 10, while the
number of buns is a multiple of 8.
The number of hot dogs matches the number of buns
whenever 10 and 8 have multiples in common.
Least Common Multiple
This occurs at 40, 80, 120…
The least of these multiples is 40.
So we will have the same number of hot dogs and buns by
buying 4 packages of hot dogs and 5 packages of buns.
Definition
Least Common Multiple (LCM)
The least common multiple (LCM) of two non-zero
whole numbers a and b is the least non-zero whole
number that is simultaneously a multiple of a and a
multiple of b.
Number-Line Method
Find LCM(3, 4).
Beginning at 0, the arrows do not coincide until the point 12
on the number line. Thus, 12 is LCM(3, 4).
Colored Rods Method
Find LCM(3, 4) using the 3 rod and the 4 rod.
Colored Rods Method
Build trains of 3 rods and 4 rods until they are the same
length. The LCM is the common length of the train.
LCM(3, 4) = 12
The Intersection-of-Sets Method
List all members of the set of positive multiples of
the two integers, then find the set of all common
multiples, and, finally, pick the least element in that
set.
The Intersection-of-Sets Method
To find the LCM of 8 and 12, denote the sets of
positive multiple of 8 and 12 by M8 and M12,
respectively.
Because the least number in the set of common positive
multiples is 24, LCM(8, 12) = 24.
The Prime Factorization Method
To find the LCM of two non-zero whole numbers,
first find the prime factorization of each number.
Then take each of the primes that are factors of
either of the given numbers. The LCM is the
product of these primes, each raised to the
greatest power of the prime that occurs in either of
the prime factorizations.
Example 4-15
Find LCM(2520, 10530).
GCD-LCM Product Method
For any two natural numbers a and b,
GCD(a, b) · LCM(a, b) = ab.
Example 4-16
Find LCM(731, 952).
Applying the Euclidean Algorithm, we can determine that
GCD(731, 952) = 17.
17 · LCM(731, 952) = 731 · 952
LCM(731, 952) =
= 40,936
Division-by-Primes Method
To find LCM(12, 75, 120), start with the least prime
that divides at least one of the given numbers.
Divide as follows:
Because 2 does not divide 75, simply bring down the 75. To
obtain the LCM using this procedure, continue the division
process until the row of answers consists of relatively prime
numbers as shown next.
Division-by-Primes Method