Prime Factorization

Factor Trees

Factorial

Problem from Session 1. (Old Session 1)

Cary, Dana, and Pat are elected to be president, secretary, and treasurer of a club. How many different election results are possible?

We solved this problem by drawing all the possible 1-1 correspondences between the people and the offices. We were able to make six different 1-1 correspondences. Later, in Session 9 (Old Session 9), we had the Fundamental Counting Principle, which gave us a method for finding the number of possibilities by multiplication: 3 choices for president, then 2 choices for secretary, and finally only 1 choice for treasurer. So, the number of possibilities was 3 · 2 · 1 = 6.

Problems of this type where we multiply descending natural numbers turn up quite often in mathematics, especially in probability and statistics. This motivates a factorial, which is an operation for this type of multiplication.

Factorial: The symbol for factorial is an exclamation mark (!) where n!, read n factorial, is defined as the product n · (n – 1) · (n – 2) · … · 3 · 2 · 1.

To evaluate four factorial, we multiply 4 times each successively smaller natural number, all the way down to 1. So four factorial is 4! = 4 · 3 · 2 · 1 = 24.

 Example: 8! = 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 40,320.

Notice that the value becomes large quite quickly.

 

We can find the prime factorization of a factorial by finding the prime factorization of each of its factors.

Example:

We may use this prime factorization to determine whether 8! has certain numbers as factors. If we can form a number by multiplying only numbers from the prime factorization, and only in a quantity available in the prime factorization, then the product is a factor of the original number.

Example: 2⁷ = 128 must be a factor of 8! since 2⁷ is part of the prime factorization of 8!.

Example: 10 must be a factor of 8! since both 2 and 5 are prime factors of 8!.

Example: 100 is not a factor of 8! since 100 = 2² · 5², so we need two factors of 5 to get 100, and 8! only has one factor of 5.  

Example: 2² · 3² must be a factor of 8! since the prime factorization of 8! contains both two 2's and two 3's.

Self-Check Problems

Find the prime factorization for 6!.

Solution

Which of the following values are factors of 6!?

8	Solution
28	Solution
48	Solution
144	Solution

return to top | previous page | next page