Transcript 9. Prime Factorization

Taking the Fear
out of Math
next
#5
Prime Numbers
and
Prime
Factorization
3×1
3
© Math As A Second Language
All Rights Reserved
next
Introduction to Prime Numbers
A convenient way to find the least common
multiple of two or more numbers is by
using what is called prime factorization.
To get a grasp of what prime numbers are,
let’s begin by looking at the multiples of 6.
6, 12, 18, 24, 30, 36, 42, 48...
© Math As A Second Language
All Rights Reserved
next
6, 12, 18, 24, 30, 36, 42, 48...
Notice that neither 4 nor 9 are on this list but
that their product (4 × 9 = 36) is on the list.
To see why this happened notice that 6 can
be factored as 3 × 2, and hence every
multiple of 6 has 2 and 3 as factors. Thus, a
number is a multiple of 6 if and only if it has
2 and 3 as factors. 4 has 2 as a factor
(that is, 4 = 2 × 2) but not 3, while 9 has 3
as a factor (that is, 9 = 3 × 3) but not 2.
© Math As A Second Language
All Rights Reserved
next
However, when we multiply 4 and 9, a
factor of 4 (that is, 2) combines with a factor
of 9 (that is, 3) to form 6 as a factor.
Using the properties of whole numbers…
4×9
= (2 × 2) × (3 ×
3)
=2×2×3×3
=2×3×2×3
= (2 × 3) × (2 ×
3)
=6×6
© Math As A Second Language
All Rights Reserved
next
However, quite a different thing happens
when we look at the multiples of either 5 or 7
(which simply happen to be the whole
numbers that 6 is between).
5, 10, 15, 20, 25, 30, 35, 40, 45. . .
7, 14, 21, 28, 35, 42, 49, 56, 63. . .
As before, neither 4 or 9 is a multiple of
either 5 or 7. However, this time
neither is their product.
© Math As A Second Language
All Rights Reserved
next
What happened here is that, unlike 6,
neither 5 nor 7 had factors other than 1
and itself.1
Therefore, the only way a number
can be a multiple of 5 is if it is itself
divisible by 5, and the only way a
number can be a multiple of 7 is if it is
itself divisible by 7.
note
1 Notice that every whole number greater than 1 has at least 2 factors
(divisors); namely, 1 and itself. However, while 6 also has 2 and 3 as
additional factors, 5 and 7 have no additional factors.
© Math As A Second Language
All Rights Reserved
next
Definitions
A whole number greater than 1 is called a prime
number if its only divisors are 1 and itself.
Examples of prime numbers are 2, 3, 5, 7, 11, and 13.
A whole number greater than 1 is called a composite
number if it is not a prime number. Examples of
composite numbers are 4, 6, 8, 9, 10,12, 14, and 15.
1 is called a unit. It is neither prime nor composite.
© Math As A Second Language
All Rights Reserved
next
An Introduction to Prime Factorization
Composite numbers can be factored in
several different ways.
For example, we may factor 12 as…
1 × 12
2×6
3×4
© Math As A Second Language
All Rights Reserved
and
2×2×3
next
However, if we insist on prime
factorization in which every factor is a
prime number, there is only one way that
this can be done (except for the order in
which we write the factors).
For example, starting with 12 = 2 × 6, we
may rewrite 6 as 2 × 3 and thus obtain…
12 = 2 × 6
= 2 × (2 × 3)
=2×2×3
© Math As A Second Language
All Rights Reserved
next
On the other hand, starting with
12 = 3 × 4, we may rewrite 4 as 2 × 2 and
thus obtain the prime factorization…
12 = 3 × 4
12 = 2 × 6
= 3 × (2 × 2)
= 2 × (2 × 3)
=3×2×2
=2×2×3
Notice while the factors appear in a
different order, the prime factorization
is the same.
© Math As A Second Language
All Rights Reserved
next
Key Point
In summary, the principle of prime
factorization tells us that a whole number
greater than 1 can be written in one and
only one way as a product of prime
numbers (except for the order in which the
factor are written),
for example,
12 = 2 × 2 × 3 = 2 × 3 × 2 = 3 × 2 × 22.
note
2 This is one reason why 1 is not considered to be a prime number. More
specifically, if 1 was a prime number the prime factorization property
would not apply because 12 could then be factored as
12 = 2 × 2 × 3 = 2 × 2 × 3 × 1 = 2 × 2 × 3 × 1 × 1, etc.
© Math As A Second Language
All Rights Reserved
next
Prime Factorization and
Least Common Multiples
Let’s return to the problem in our
previous presentation of the
hot dogs and hot dog buns. The buns
come in packages of 8, and the prime
factorization of 8 is 2 × 2 × 2.
Thus, any multiple of 8 must have the form
2 × 2 × 2 × N where N is any whole
note
number.3
3 Do not be confused by letting N stand for any whole number. It simply
means, for example, that if we choose N to be 7, 2 × 2 × 2 × 7 is the 7th
multiple of 8. And in a similar way, 2 × 2 × 2 × 13 is the 13th multiple of
8.
© Math As A Second Language
All Rights Reserved
next
On the other hand, since the hot
dogs come in packages of 10, and the
prime factorization of 10 is 2 × 5, we
see that any multiple of 10 must have
the form 2 × 5 × M where M is any
whole number.
© Math As A Second Language
All Rights Reserved
next
Thus, we see that to be a common
multiple of 8 and 10, it must have at least 3
factors of 2 (because 8 = 2 × 2 × 2) and at
least 1 factor of 5 (because 10 = 2 × 5).
8=2×2×2
10 = 2 × 5
= 40
Therefore, the least common multiple of
8 and 10 is 2 × 2 × 2 × 5 (= 40).
© Math As A Second Language
All Rights Reserved
next
Notice that nothing smaller can be a
multiple of both 8 and 10 (because if the 5
isn’t present, it won’t be a multiple of 10,
and if even one of the factors of 2 is
missing, it won’t be a multiple of 8.
© Math As A Second Language
All Rights Reserved
next
Thus, without specifically listing the
multiples of both 8 and 10, we have
determined that 40 is the least common
multiple of 8 and 10.
In this example, it wouldn’t be too tedious
to list the multiples of both 8 and 10
and see that 40 was the first number that
appeared on both lists of multiples.
8, 16, 24, 32, 40, 48…
10, 20, 30, 40, 50, 60…
© Math As A Second Language
All Rights Reserved
next
However, as we will discuss in more
detail in our presentation on fractions, this
is not always the case.
As a case in point, let’s use prime
factorization to find the least common
multiple of 2, 3, 4, 5, 6, 7, 8, 9 and 10.
Note
We can always find a common multiple of
any number of whole numbers simply by
multiplying all of the numbers.
© Math As A Second Language
All Rights Reserved
next
Note
Therefore,
2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 =
3,628,800 is a common multiple of 2, 3, 4,
5, 6, 7, 8, 9, and 10.
However, as we will now show, it isn’t
the least common multiple.
© Math As A Second Language
All Rights Reserved
next
To find the least common multiple, for
2, 3, 4, 5, 6, 7, 8, 9, and 10
we know that…
► To be a multiple of 2, the number we are
looking for must have the form
2 × ___ (i.e. 2 דany whole number”).
© Math As A Second Language
All Rights Reserved
next
2 × ___
► To be a multiple of 3, the number we
are looking for must have the form
3 × ___ .
And since 2 and 3 are both prime
numbers, to be a multiple of both 2 and 3,
the number we are looking or must have
the form 2 × 3 × ___.
And since 1 is the smallest non zero
whole number, the least common multiple
of 2 and 3 is 2 × 3 × 1 (or 6 ).
© Math As A Second Language
All Rights Reserved
next
2 × 3 × ___
► To be a multiple of 4, the number we
are looking for must have the form
4 × ___, or in terms of prime factorization,
2 × 2 × ___ .
The problem now is that 2 × 3 has only
one factor of 2, which means that to have
the least common multiple of 2, 3, and 4,
we need another factor of 2.
In other words, the least common
multiple of 2, 3, and 4 is 2 × 2 × 3 × 1 (or
12).
© Math As A Second Language
All Rights Reserved
next
2 × 3 × 2 × ___
► To be a multiple of 5, the number we
are looking for must have the form
5 × ___.
The problem now is that 2 × 3 × 2 does
not
contain 5 as a prime factor. Therefore, to
convert 2 × 2 × 3 into a common multiple
of 2, 3, 4, and 5, we need to multiply
2 × 3 × 2 by 5.
In other words, the least common multiple
of 2, 3, 4, and 5 is 2 × 3 × 2 × 5 (or 60) .
© Math As A Second Language
All Rights Reserved
next
2 × 3 × 2 × 5 × ___
► To be a multiple of 6, the number we are
looking for must have the form
6 × ___, or in terms of prime factorization,
2 × 3 × ___.
However, since 60 already contains 2 × 3
as a factor, it means that the least common
multiple of 2, 3, 4, 5, and 6 is still
4.
2
×
2
×
3
×
5
(or
60)
note
4 This might be a good reason for why the Babylonians liked to work with 60
as the base of their number system. Namely it is the smallest positive
whole number that is divisible by 2, 3, 4, 5, and 6.
© Math As A Second Language
All Rights Reserved
next
2 × 3 × 2 × 5 × ___
► To be a multiple of 7, the number we
are looking for must have the form
7 × ___.
The problem now is that while 7 is a
prime number, but 60 does not contain 7 as
a prime factor. Therefore, to convert 60 into
a common multiple of 2, 3, 4, 5, 6, and 7, we
need to multiply 2 × 3 × 2 × 5 by 7.
In other words, the least common multiple
of 2, 3, 4, 5, and 7 is 2 × 3 × 2 × 5 × 7
(or 420) .
© Math As A Second Language
All Rights Reserved
next
2 × 3 × 2 × 5 × 7 × ___
► To be a multiple of 8, the number we
are looking for must have the form
8 × ___, or in terms of prime factorization,
2 × 2 × 2 × ___.
However, since 420 contains 2 × 2 but not
2 × 2 × 2 as a factor, it means that the
least common multiple of 2, 3, 4, 5, 6, 7,
and 8 must contain an additional factor of
2. common multiple
In other words, the least
of 2, 3, 4, 5, 6, 7, and 8 is
2 × 3 × 2 × 5 × 7 × 2 (or 840).
© Math As A Second Language
All Rights Reserved
next
2 × 3 × 2 × 5 × 7 × 2 ___
► To be a multiple of 9, the number we
are looking for must have the form
9 × ___, or in terms of prime factorization,
3 × 3 × ___.
However, since 840 contains 3 but not
3 × 3 as a factor, it means that the least
common multiple of 2, 3, 4, 5, 6, 7, 8 and 9
must contain an additional factor of 3.
In other words, the least common multiple
of 2, 3, 4, 5, 6, 7, 8, and 9 is
2 × 3 × 2 × 5 × 7 × 2 × 3 (or 2,520).
© Math As A Second Language
All Rights Reserved
next
2 × 3 × 2 × 5 × 7 × 2 × 3 ___
► To be a multiple of 10, the number we
are looking for must have the form
10 × ___, or in terms of prime
factorization, 2 × 5 × ___.
Since 2 × 5 is already a factor,
the least common multiple of
2, 3, 4, 5, 6, 7, 8, 9, and 10 is also 2,520.
© Math As A Second Language
All Rights Reserved
next
2×
2×
3×
3×2 2×
×55×
× 77××2×
2×
3 =3 2,520
In prime factorization, it is traditional to
arrange the factors from least to greatest.
Notice that changing the order of the
factors does not change the product.
= 2,520
© Math As A Second Language
All Rights Reserved
next
Note
To see how tedious it would be to try to
find the least common multiple by listing
the multiples of 2, 3, 4, 5, 6, 7, 8, 9 and 10,
and then looking for the first number that
appeared on each of the lists, notice that
2,520 is the 1,260th multiple of 2, the 840th
multiple of 3, the 630th multiple of 4, the
504th multiple of 5, the 420th multiple of 6,
the 360th multiple of 7, the 315th multiple of
8, the 280th multiple of 9, and the 252nd
multiple of 10.
© Math As A Second Language
All Rights Reserved
next
Note
By writing 2,520 as a product of prime
numbers we can see immediately whether
a given number is a divisor of 2,520.
For example, if we write 2,520 in the form
2×2×2×3×3×5×7
We can see that since 35 = 5 × 7, it is a
divisor of 2,520.
© Math As A Second Language
All Rights Reserved
next
Note
Notice that we can rearrange the factors
of 2,520 to obtain…
(5 ×7) × (2 × 2 × 2 × 3 × 3) or 35 × 72.
In other words 2,520 is the 72nd multiple
of 35 (and the 35th multiple of 72).
On the other hand, 22 is not a divisor of
2,520 because 22 = 2 × 11 and the prime
number 11 is not a prime factor of 2,520.
© Math As A Second Language
All Rights Reserved
next
Prime Factors
© Math As A Second Language
In our next lessons, we
will show how
prime factors and
least common multiples
are related to the
arithmetic of fractions.
All Rights Reserved