Prime Factorization

Download Report

Transcript Prime Factorization

Factors, Prime Numbers
& Prime Factorization
The Factors of a Whole Number are:
All the whole numbers that divide evenly into it.
Example: Factors of 12 are 1, 2, 3, 4, 6, and 12
Prime Numbers are any Whole Number greater
than 1 whose ONLY factors are 1 and itself.
Example: 7 is a Prime Number
because 7’s only factors are 1 and 7
How can you check
to see if a number is Prime?
Click to Advance
Suggestion:
Work with
scratch paper
and pencil as you
go through this
presentation.
All About Primes
1
Tricks for recognizing when a number
must have a factor of 2 or 5 or 3

ANY even number can always be divided by 2
◦ Divides evenly: 3418,
◦
Doesn’t:
37,

Numbers ending in 5 or 0 can always be divided by 5
◦ Divides evenly: 2345,
◦
Doesn’t:
37,

70, 122
120,001
70,
41,415
120,001
If the sum of a number’s digits divides evenly by 3, then
the number always divides by 3
◦ Divides evenly:
◦
Doesn’t:
39,
186, 5670
43, 56,204
Click to Advance
All About Primes
2
Can You divide any even number by 2
using Shorthand Division?


Let’s try an easy one. Divide 620,854 by 2:
Start from the left,
do one digit at a time
◦
◦
◦
◦
◦
◦
◦


14
What’s ½ of 6?
What’s ½ of 2?
What’s ½ of 0?
What’s ½ of 8?
What’s ½ of 5?
(It’s 2 with 1 left over; carry 1 to the 4, making it 14)
What’s ½ of 14?
div 2 in to 6 2 0, 8 5 4
3 1 0, 4 2 7
You try: Divide 42,684 by 2.
It’s 21,342
12
Divide 102,072 by 2.
It’s 51,036
Click to Advance
All About Primes
3
Finding all factors of 2 in any number:
The “Factor Tree” Method


Write down the even number
Break it into a pair of factors
40
(use 2 and ½ of 40)
As long as the righthand
number is even, break out
another pair of factors
 Repeat until the righthand
number is odd (no more 2’s)
 Collect the “dangling” numbers
as a product;
You can also use exponents

Click to Advance
2
20
2
10
2
5
40= 2∙2∙2∙5 = 23∙5
All About Primes
4
Can You divide any number by 3
using Shorthand Division?
Will it divide evenly?
6+1+2+5+4=18, 18/3=6 yes
Let’s try an easy one. Divide 61,254 by 3:
 Start from the left,
do one digit at a time

◦ Divide 3 into 6
12
 Goes 2 w/ no remainder
◦ Divide 3 into 1
24
div 3 in to 6 1, 2 5 4
 Goes 0 w/ 1 rem; carry it to the 2
2 0, 4 18
◦ Divide 3 into 12
 Goes 4 w/ no rem
◦ Divide 3 into 5
 Goes 1 w/ 2 rem; carry it to the 4
◦ Divide 3 into 24
 Goes 8 w/ 0 rem
12
24
You try: Divide 42,684 by 3.

It’s 14,228

12
12
Divide 102,072 by 3.
It’s 34,024
Click to Advance
All About Primes
5
Finding all factors of 2 and 3 in any number:
The “Factor Tree” Method
Write down the number
 Break 36 into a pair of
factors (start with 2 and 18)
 Break 18 into a pair of
factors (2 and 9)
 9 has two factors of 3
 Collect the “dangling”
numbers as a product,
optionally using exponents

Click to Advance
36
2
18
2
9
3
3
36= 2∙2∙3∙3 = 22∙32
All About Primes
6
Finding all factors of 2, 3 and 5 in a number:
The “Factor Tree” Method
Write down the number
 Break 150 into a pair of
factors (start with 2 and 75)
 Break 75 into a pair of
factors (3 and 25)
 25 has two factors of 5
 Collect the “dangling”
numbers as a product

Click to Advance
150
2
75
3
25
5
5
150 = 2∙3∙5∙5
All About Primes
7
What is a Prime Number?

A Whole Number is prime if it is greater than one, and
the only possible factors are one and the Whole Number itself.
0 and 1 are not considered prime numbers
 2 is the only even prime number

◦ For example, 18 = 2∙9 so 18 isn’t prime
3, 5, 7 are primes
 9 = 3∙3, so 9 is not prime
 11, 13, 17, and 19 are prime
 There are infinitely many primes above 20.

 How
can you tell if a large number is prime?
Click to Advance
All About Primes
8
Is a large number prime? You can find out!
What smaller primes do you have to check?
Here is a useful table of the squares of some small primes:
22=4 32=9 52=25 72=49 112=121
121 132=169
169 172=289 192=361
See where the number fits in the table above

Let’s use 151 as an example:
 151 is between the squares of 11 and 13
 Check all primes before 13: 2, 3, 5, 7, 11

◦
◦
◦
◦
◦

2 won’t work … 151 is not an even number
3 won’t work … 151’s digits sum to 7, which isn’t divisible by 3
5 won’t work … 151 does not end in 5 or 0
13
21
11 151
7 won’t work … 151/7 has a remainder
7 151
11
14
11 won’t work … 151/11 has a remainder
41
11
r8
r4
So … 151 must be prime
Click to Advance
All About Primes
9
33
4
8
9
What is Prime Factorization?
 It’s
a Critical Skill!

(A big name for a simple process …)

Writing a number as the product of it’s prime
factors.

Examples:
6=2∙3
 70 = 2 ∙ 5 ∙ 7
 24 = 2 ∙ 2 ∙ 2 ∙ 3 = 23 ∙ 3
 17= 17 because 17 is prime

Click to Advance
All About Primes
10
Finding all prime factors:
The “Factor Tree” Method
Write down a number
 Break it into a pair of factors

198
(use the smallest prime)
Try to break each new factor
into pairs
 Repeat until every dangling
number is prime
 Collect the “dangling” primes
into a product

2
99
3
33
3
11
198= 2·3·3·11
Click to Advance
All About Primes
11
The mechanics of
The “Factor Tree” Method
First, find the easiest prime number
 To get the other factor, divide it
into the original number
 2 can’t be a factor, but 5 must be
(because 165 ends with 5)
 Divide 5 into 165 to get 33
 33’s digits add up to 6,
so 3 must be a factor
 Divide 3 into 33 to get 11
 All the “dangling” numbers are
prime, so we are almost done
 Collect the dangling primes into a
product (smallest-to-largest order)

Click to Advance
165
5
33
3
11
165=3·5·11
All About Primes
12
Thank You

For Learning about Prime Factorization
Press the ESC key to exit this Show
All About Primes
13
You can also use a linear approach
Suggestion:
84=2· 42

=2· 2· 21

=2· 2· 3· 7

=22· 3· 7 (simplest form)







If you are unable to do
divisions in your head,
do your divisions in a
work area to the right
of the linear
factorization steps.
216=2· 108
108
=2· 2· 54
2 216
=2· 2· 2· 27
9
=2· 2· 2· 3· 9
3 27
=2· 2· 2· 3· 3· 3
=23·33
(simplest form)
Click to Advance
54
2 108
All About Primes
27
2 54
3
39
14