Transcript Prime Factorization

Chapter
4
Number Theory
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
4-2 Prime and Composite Numbers
Prime and Composite Numbers
Prime Factorization
Number of Divisors
Determining if a Number is Prime
More About Primes
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Prime and Composite Numbers
The following rectangles represent the number 18.
1
18
6
9
2
3
The number 18 has 6 positive divisors: 1, 2, 3,
6, 9 and 18.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Prime and Composite Numbers
Below each
number listed
across the top,
we identify
numbers less
than or equal to
37 that have that
number of
positive divisors.
Number of Positive Divisors
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Prime Numbers
Number of Positive Divisors
These numbers
have exactly 2
positive divisors,
1 and
themselves.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Composite Numbers
Number of Positive Divisors
These numbers
have at least
one factor
other than 1
and
themselves.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Prime and Composite Numbers
Number of Positive Divisors
The number 1
has only one
positive factor –
it is neither
prime nor
composite.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Definition
Prime number
Any positive integer with exactly two distinct, positive
divisors
Composite number
Any whole number greater than 1 that has a positive
factor other than 1 and itself
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Example 4-9
Show that the following numbers are composite.
a. 1564
Since 2 | 4, 1564 is divisible by 2 and is composite.
b. 2781
Since 3 | (2 + 7 + 8 + 1), 2781 is divisible by 3 and is
composite.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Example 4-9
(continued)
c. 1001
Since 11 | [(1 + 0) − (0 + 1)], 1001 is divisible by 11 and
is composite.
d. 3 · 5 · 7 · 11 · 13 + 1
The product of odd numbers is odd, so 3 · 5 · 7 · 11 · 13
is odd. When 1 is added to an odd number, the sum is
even. All even numbers are divisible by 2 and all even
numbers, except 2, are composite.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Prime Factorization
Students continue to develop their understanding
of multiplication and division and the structure of
numbers by determining if a counting number
greater than 1 is a prime, and if it is not, by
factoring it into a product of primes.
NCTM grade 7 Curriculum Focal Points, p. 19
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Prime Factorization
Composite numbers can be expressed as products
of two or more whole numbers greater than 1.
Each expression of a number as a product of factors is a
factorization.
A factorization containing only prime numbers is a prime
factorization.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Fundamental Theorem of Arithmetic
(Unique Factorization Theorem)
Each composite number can be written as a
product of primes in one and only one way except
for the order of the prime factors in the product.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Prime Factorization
To find the prime factorization of a composite
number, rewrite the number as a product of two
smaller natural numbers. If these smaller numbers
are both prime, you are finished. If either is not
prime, then rewrite it as the product of smaller
natural numbers. Continue until all the factors are
prime.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Prime Factorization
84
495
4
2
21
2
3
5
7
99
11
9
3
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
3
Prime Factorization
The two trees produce the same prime factorization,
except for the order in which the primes appear in
the products.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Prime Factorization
We can also determine the prime factorization by
dividing with the least prime, 2, if possible. If not,
we try the next larger prime as a divisor. Once we
find a prime that divides the number, we continue
by finding smallest prime that divides that quotient,
etc.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Prime Factorization
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Number of Divisors
How many positive divisors does 24 have? We are
not asking how many prime divisors, just the
number of divisors – any divisors.
1, 2, 3, 4, 6, 8, 12, 24
Since 1 is a divisor of 24, then 24/1 = 24 is a divisor of 24.
Since 2 is a divisor of 24, then 24/2 = 12 is a divisor of 24.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Number of Divisors
1, 2, 3, 4, 6, 8, 12, 24
Since 3 is a divisor of 24, then 24/3 = 8 is a divisor of 24.
Since 4 is a divisor of 24, then 24/4 = 6 is a divisor of 24.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Number of Divisors
Another way to think of the number of positive
divisors of 24 is to consider the prime factorization
23 = 8 has four divisors. 3 has two divisors.
Using the Fundamental Counting Principle, there are 4 × 2
= 8 divisors of 24.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Number of Divisors
If p and q are different primes, m and n are whole
number then pnqm has (n + 1)(m + 1) positive
divisors.
In general, if p1, p2, …, pk are primes, and n1, n2, …, nk
are whole numbers, then
has
positive divisors.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Example 4-10a
Find the number of positive divisors of 1,000,000.
The prime factorization of 1,000,000 is
26 has 6 + 1 = 7 divisors, and 56 has 6 + 1 = 7 divisors.
has (7)(7) = 49 divisors.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Example 4-10b
Find the number of positive divisors of 21010.
The prime factorization of 21010 is
210 has 10 + 1 = 11 divisors, 310 has 10 + 1 = 11 divisors,
510 has 10 + 1 = 11 divisors, and 710 has 10 + 1 = 11
divisors.
has 114 = 14,641 divisors.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Determining if a Number is Prime
To determine if a number is prime, you must check
only divisibility by prime numbers less than the
given number.
For example, to determine if 97 is prime, we must try
dividing 97 by the prime numbers: 2, 3, 5, and so on as
long as the prime is less than 97.
If none of these prime numbers divide 97, then 97 is prime.
Upon checking, we determine that 2, 3, 5, 7 do not divide
97.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Determining if a Number is Prime
Assume that p is a prime greater than 7 and p | 97.
Then 97/p also divides 97. Because p ≥ 11, then
97/p must be less than 10 and hence cannot divide
97.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Determining if a Number is Prime
If d is a divisor of n, then
is also a divisor of n.
If n is composite, then n has a prime factor p such that
p2 ≤ n.
If n is a whole number greater than 1 and not divisible by
any prime p, such that p2 ≤ n, then n is prime.
Note: Because p2 ≤ n implies that
check if any prime less than or equal to
is a divisor of n.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
it is enough to
Example 4-11a
Is 397 composite or prime?
The possible primes p such that p2 ≤ 397 are 2, 3, 5, 7,
11, 13, 17, and 19.
Because none of the primes 2, 3, 5, 7, 11, 13, 17, and
19 divide 397,397 is prime.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Example 4-11b
Is 91 composite or prime?
The possible primes p such that p2 ≤ 91 are 2, 3, 5,
and 7.
Because 91 is divisible by 7, it is composite.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Sieve of Eratosthenes
One way to find all the primes less than a given
number is to use the Sieve of Eratosthenes.
If all the natural numbers greater than 1 are
considered (or placed in the sieve), the numbers
that are not prime are methodically crossed out (or
drop through the holes of the sieve). The
remaining numbers are prime.
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.
Sieve of Eratosthenes
Copyright © 2013, 2010, and 2007, Pearson Education, Inc.