Prime Factorization
Take a number such as 56. It is composite, as we saw that it can be written as 56* = 4 ×
In conclusion, we have written 56 as a product of prime numbers. This is called prime factorisation of 56. The individual factors are called prime factors. For example, the prime factors of 56 are 2 and 7.
Every number greater than 1 has a prime factorisation. The idea is the same: keep breaking the composite numbers into factors till only primes are left.
The number 1 does not have any prime factorisation. It is not divisible by any prime number.
What is the prime factorisation of a prime number like 7? It is just 7 (we cannot break it down any further).
Let us see a few more examples.
By going through different ways of breaking down the number, we wrote 63 as 3 × 3 × 7 and as 3 × 7 × 3. Are they different? Not really! The same prime numbers 3 and 7 occur in both cases. Further, 3 appears two times in both and 7 appears once.
Here, you see four different ways to get prime factorisation of 36. Observe that in all four cases, we get two 2s and two 3s.
Multiply back to see that you get 36 in all four cases.
For any number, it is a remarkable fact that there is only one prime factorisation, except that the prime factors may come in different orders. As we explain below, the order is not important. However, as we saw in these examples, there are many ways to arrive at the prime factorisation!
Using this diagram, can you explain why 30 = 2 × 3 × 5, no matter which way you multiply 2, 3, and 5?
When multiplying numbers, we can do so in any order. The end result is the same. That is why, when two 2s and two 3s are multiplied in any order, we get 36. In a later class, we shall study this under the names of commutativity and associativity of multiplication.
Thus, the order does not matter. Usually we write the prime numbers in increasing order. For example, 225 = 3 × 3 × 5 × 5 or 30 = 2 × 3 × 5.
When we find the prime factorisation of a number, we first write it as a product of two factors. For example, 72 = 12 ×
The prime factorisation of the original number is obtained by putting these together.
72 = 2 × 2 ×
We can also write this as 2 × 2 × 2 × 3 × 3. Multiply and check that you get 72 back! s Observe how many times each prime factor occurs in the factorisation of 72.
Compare it with how many times it occurs in the factorisations of 12 and 6 put together.
1. Find the prime factorisations of the following numbers: 64, 104, 105, 243, 320, 141, 1728, 729, 1024, 1331, 1000.
Answer: 64 = 2 × 32 = 2 × 2 × 16 = 2 × 2 × 2 × 8 = 2 × 2 × 2 × 2 × 4 = 2 × 2 × 2 × 2 × 2 × 2 = 2
104 = 8 × 13 = 2 × 2 × 2 × 13 = 2³ ×
105 = 3 × 35 = 3 × 5 × 7 = 3 × 5 ×
243 = 3 × 81 = 3 × 3 × 27 = 3 × 3 × 3 × 9 = 3 × 3 × 3 × 3 × 3 = 3
320 = 32 × 10 = 2⁵ × 2 × 5 = 2⁶ × 5 = 2⁶ ×
141 = 3 × 47 = 3 ×
1728 = 12³ = (4 × 3)³ = (2² × 3)³ = 2⁶ × 3³ = 2⁶ ×
729 = 9³ = (3²)³ = 3⁶ = 3
1024 = 2¹⁰ = 2
1331 = 11³ = 11
1000 = 10³ = (2 × 5)³ = 2³ × 5³ = 2³ × 5
2. The prime factorisation of a number has one 2, two 3s, and one 11. What is the number?
Answer: The number = 2 × 3² × 11 = 2 ×
= 2 × 9 × 11 =
3. Find three prime numbers, all less than 30, whose product is 1955.
Answer: First, let's find the prime factorisation of 1955: 1955 ÷ 5 =
391 ÷ 17 =
23 is prime, so 1955 = 5 × 17 × 23
The three prime numbers are
4. Find the prime factorisation of these numbers without multiplying first:
a. 56 × 25
Answer: First find prime factorisation of each:
56 = 8 ×
25 = 5
Therefore, 56 × 25 = 2³ × 7 × 5² = 2³ × 5² ×
b. 108 × 75
Answer: First find prime factorisation of each:
108 = 4 ×
75 = 25 ×
Therefore, 108 × 75 = 2² × 3³ × 5² × 3 = 2² × 3⁴ × 5² = 2² ×
c. 1000 × 81
Answer: First find prime factorisation of each:
1000 = 2
81 = 3
Therefore, 1000 × 81 = 2³ × 5³ × 3⁴ = 2³ × 3⁴ × 5³ =
5. What is the smallest number whose prime factorisation has:
a. three different prime numbers?
Answer: The three smallest prime numbers are 2,
The smallest number = 2 × 3 × 5 =
b. four different prime numbers?
Answer: The four smallest prime numbers are 2, 3, 5, and
The smallest number = 2 × 3 × 5 × 7 = 6 × 5 × 7 = 30 × 7 =
Prime factorisation is of fundamental importance in the study of numbers. Let us discuss two ways in which it can be useful.
Let us again take the numbers 56 and 63. How can we check if they are co-prime?
We can use the prime factorisation of both numbers—
56 = 2 × 2 × 2 × 7 and 63 = 3 × 3 × 7
Now, we see that 7 is a prime factor of 56 as well as 63. Therefore, 56 and 63 are not co-prime.
What about 80 and 63? Their prime factorisations are as follows:
80 = 2 × 2 × 2 × 2 × 5 and 63 = 3 × 3 × 7
There are no common prime factors. Can we conclude that they are co-prime? Suppose they have a common factor that is composite. Would the prime factors of this composite common factor appear in the prime factorisation of 80 and 63?
Therefore, we can say that if there are no common prime factors, then the two numbers are co-prime.
Let us see some examples.
Example: Consider 40 and 231. Their prime factorisations are as follows:
40 = 2 × 2 × 2 × 5 and 231 = 3 × 7 × 11
We see that there are no common primes that divide both 40 and 231. Indeed, the prime factors of 40 are 2 and 5 while, the prime factors of 231 are 3, 7, and 11. Therefore, 40 and 231 are co-prime!
Example: Consider 242 and 195. Their prime factorisations are as follows:
242 = 2 × 11 × 11 and 195 = 3 × 5 × 13
The prime factors of 242 are 2 and 11. The prime factors of 195 are 3, 5, and 13. There are no common prime factors. Therefore, 242 and 195 are co-prime.
We can say that if one number is divisible by another, the prime factorisation of the second number is included in the prime factorisation of the first number.
We say that 48 is divisible by 12 because when we divide 48 by 12, the remainder is zero. How can we check if one number is divisible by another without carrying out long division?
Example: Is 168 divisible by 12? Find the prime factorisations of both:
168 = 2 × 2 × 2 × 3 × 7 and 12 = 2 × 2 × 3
Since we can multiply in any order, now it is clear that,
168 = 2 × 2 × 3 × 2 × 7 = 12 × 14
Therefore, 168 is divisible by 12.
Example: Is 75 divisible by 21? Find the prime factorisations of both:
75 = 3 × 5 × 5 and 21 = 3 × 7
As we saw in the discussion above, if 75 was a multiple of 21, then all prime factors of 21 would also be prime factors of 75. However, 7 is a prime factor of 21 but not a prime factor of 75. Therefore, 75 is not divisible by 21.
Example: Is 42 divisible by 12? Find the prime factorisations of both:
42 = 2 × 3 × 7 and 12 = 2 × 2 × 3
All prime factors of 12 are also prime factors of 42. But the prime factorisation of 12 is not included in the prime factorisation of 42. This is because 2 occurs twice in the prime factorisation of 12 but only once in the prime factorisation of 42. This means that 42 is not divisible by 12.
We can say that if one number is divisible by another, then the prime factorisation of the second number is included in the prime factorisation of the first number.
1. Are the following pairs of numbers co-prime? Guess first and then use prime factorisation to verify your answer. a. 30 and 45 b. 57 and 85 c. 121 and 1331 d. 343 and 216
2. Is the first number divisible by the second? Use prime factorisation. a. 225 and 27 b. 96 and 24 c. 343 and 17 d. 999 and 99
3. The first number has prime factorisation 2 × 3 × 7 and the second number has prime factorisation 3 × 7 × 11. Are they co-prime? Does one of them divide the other?
4. Guna says, "Any two prime numbers are co-prime?". Is he right?