Transcript Example: Finding the Greatest Common Divisor

CHAPTER 5
Number Theory and the
Real Number System
© 2010 Pearson Prentice Hall. All rights reserved.
§5.1, Number Theory: Prime &
Composite Numbers
© 2010 Pearson Prentice Hall. All rights reserved.
2
Learning Targets
I will determine divisibility.
I will write the prime factorization of a composite
number.
I will find the greatest common divisor of two
numbers.
I will solve problems using the greatest common
divisor.
I will find the least common multiple of two
numbers.
I will solve problems using the least common multiple.
© 2010 Pearson Prentice Hall. All rights reserved.
3
Number Theory and Divisibility
• Number theory is primarily concerned with the
properties of numbers used for counting, namely 1, 2,
3, 4, 5, and so on.
• The set of natural numbers is given by
N  1,2,3,4,5,6,7,8,9,10,11,...
• Natural numbers that are multiplied together are
called the factors of the resulting product.
© 2010 Pearson Prentice Hall. All rights reserved.
4
Divisibility
• If a and b are natural numbers, a is divisible by b if the
operation of dividing a by b leaves a remainder of 0.
• This is the same as saying that b is a divisor of a, or b
divides a.
• This is symbolized by writing b|a.
Example: We write 12|24 because 12 divides 24 or 24
divided by 12 leaves a remainder of 0. Thus, 24 is
divisible by 12.
Example: If we write 13|24, this means 13 divides 24 or
24 divided by 13 leaves a remainder of 0. But this is
not true, thus, 13|24.
© 2010 Pearson Prentice Hall. All rights reserved.
5
Prime Factorization
• A prime number is a natural number greater than 1
that has only itself and 1 as factors.
• A composite number is a natural number greater than
1 that is divisible by a number other than itself and 1.
• The Fundamental Theorem of Arithmetic
Every composite number can be expressed as a
product of prime numbers in one and only one
way.
• One method used to find the prime factorization of a
composite number is called a factor tree.
© 2010 Pearson Prentice Hall. All rights reserved.
6
Example: Prime Factorization using a
Factor Tree
Example: Find the prime factorization of 700.
Solution: Start with any two numbers whose product is
700, such as 7 and 100.
Continue factoring the
composite number, branching
until the end of each branch
contains a prime number.
© 2010 Pearson Prentice Hall. All rights reserved.
7
Example (continued)
Thus, the prime factorization of 700 is
700 = 7  2  2  5  5
= 7  22  52
2
2
 2 5 7
Notice, we rewrite the prime factorization using a dot to
indicate multiplication, and arranging the factors from
least to greatest.
© 2010 Pearson Prentice Hall. All rights reserved.
8
Greatest Common Divisor
To find the greatest common divisor of two or more numbers;
1. Write the prime factorization of each number.
2. Select each prime factor with the smallest exponent that is
common to each of the prime factorizations.
3. Form the product of the numbers from step 2. The greatest
common divisor is the product of these factors.
• Pairs of numbers that have 1 as their greatest common divisor
are called relatively prime.
For example, the greatest common divisor of 5 and 26 is 1.
Thus, 5 and 26 are relatively prime.
© 2010 Pearson Prentice Hall. All rights reserved.
9
Example: Finding the Greatest Common
Divisor
Example: Find the greatest common divisor of 216 and
234.
Solution: Step 1. Write the prime factorization of each
number.
© 2010 Pearson Prentice Hall. All rights reserved.
10
Example (continued)
216 = 23  33
234 = 2  32  13
Step 2. Select each prime factor with the smallest
exponent that is common to each of the prime
factorizations.
Which exponent is appropriate for 2 and 3? We choose
the smallest exponent; for 2 we take 21, for 3 we take
32.
© 2010 Pearson Prentice Hall. All rights reserved.
11
Example (continued)
Step 3. Form the product of the numbers from step 2.
The greatest common divisor is the product of these
factors. Greatest common divisor = 2  32 = 2  9 =
18. Thus, the greatest common factor for 216 and 234
is 18.
© 2010 Pearson Prentice Hall. All rights reserved.
12
Least Common Multiple
•
The least common multiple of two or more natural numbers
is the smallest natural number that is divisible by all of the
numbers.
To find the least common multiple using prime factorization of
two or more numbers:
1. Write the prime factorization of each number.
2. Select every prime factor that occurs, raised to the greatest
power to which it occurs, in these factorizations.
3. Form the product of the numbers from step 2. The least
common multiple is the product of these factors.
© 2010 Pearson Prentice Hall. All rights reserved.
13
Example: Finding the Least Common
Multiple
Example: Find the least common multiple of 144 and
300.
Solution: Step 1. Write the prime factorization of each
number.
144 = 24  32
300 = 22  3  52
Step 2. Select every prime factor that occurs, raised to
the greatest power to which it occurs, in these
factorizations. 144 = 24  32
300 = 22  3  52
© 2010 Pearson Prentice Hall. All rights reserved.
14
Example: continued
Step 3. Form the product of the numbers from step 2.
The least common multiple is the product of these
factors.
LCM = 24  32  52 = 16  9  25 = 3600
Hence, the LCM of 144 and 300 is 3600. Thus, the
smallest natural number divisible by 144 and 300 is
3600.
© 2010 Pearson Prentice Hall. All rights reserved.
15
Critical Thinking:
You and your brother both work the 4:00 p.m. to
midnight shift at the movie theater. You have every
sixth night off, while your brother has every tenth
night off. Both of you were off on June 1. Your
brother would like to see a movie with you. When
will the two of you have the same night off again?
© 2010 Pearson Prentice Hall. All rights reserved.
Homework:
Page 236, #30 – 42 (e), 46 – 56 (e), 57 – 65.
© 2010 Pearson Prentice Hall. All rights reserved.