Applications of Prime Factorization

Go back to  'Arithmetic-Integers'

The number 36 is a perfect square. Its prime-factored form is \({2^2} \times {3^2}\). The powers of the both the prime factors are even. Consider 324. This is again a perfect square – its prime factored form is \({2^2} \times {3^4}\) – again,  the powers of the prime factors are even.

It is easy to see that in any perfect square, the powers of all the prime-factors must be even, because when we take the square-root, we have to halve the power of each prime factor. If the power of a prime factor is not even, then it cannot be halved into an integer, and thus the corresponding number will not be a perfect square.

Similarly, if a number p is a perfect kth power, then the power of each prime factor must be a multiple of k, otherwise taking the kth root of p will not give an integer.

Example 1: Find the smallest positive integer n such that n/2 is a perfect square, n/3 is a perfect cube and n/5 is a perfect fifth power.

Solution: Clearly, n should have 2, 3 and 5 as prime factors. Let

\[n = {2^p}{3^q}{5^r}\]

Thus,

\[\begin{align}&\frac{n}{2} = {2^{p - 1}}{3^q}{5^r}\\&\frac{n}{3} = {2^p}{3^{q - 1}}{5^r}\\&\frac{n}{5} = {2^p}{3^q}{5^{r - 1}}\end{align}\]

Now, we note the following:

  • p must be a multiple of 3 and 5, and \(p - 1\) should be even. The minimum such p is 15.

  • q must be even and a multiple of 5, and \(q - 1\) must be a multiple of 3. The minimum such q is 10.

  • r must be even and a multiple of 3, and \(r - 1\) must be a multiple of 5. The minimum such r is 6.

Thus, \(n = {2^{15}}{3^{10}}{5^6}\) is the required number.

Consider the number n = 72. Can we somehow count the number of factors of this number, without listing them out explicitly?

The prime factored form of n is:

\[n = {2^3} \times {3^2}\]

Now, any factor of 72 can be formed by selecting a certain number of 2’s and a certain number of 3’s. For example:

  • If we select two 2’s and one 3, we get the factor \({2^2} \times 3\) or 12

  • If we select zero 2’s and two 3’s, we get the factor \({2^0} \times {3^2}\) or 9

  • If we select three 2’s and zero 3’s, we get the factor \({2^3} \times {3^0}\) or 8

  • …and so on

Note that we cannot take more than three 2’s, and more than two 3’s.

We see that any factor of 72 can be created by selecting a certain number of 2’s and a certain number of 3’s (subject to the constraint that the number of 2’s is from the set {0, 1, 2, 3}, while the number of 3’s is from the set is {0, 1, 2}). In how many ways can we do this?

This has essentially boiled down to a combinatorics problem. The number of ways of selecting 2’s is 4: we select either zero 2’s, one 2, two 2’s or three 2’s. The number of ways of selecting 3’s is 3: we select either zero 3’s, one three or two 3’s.

Using the FPC, the number of ways of selecting a certain number of 2’s and 3’s must be \(4 \times 3 = 12\). Thus, 72 should have 12 factors. Let us verify this explicitly:

\[1,2,3,4,6,8,9,12,18,24,36,72\]

What we’ve just discussed is significant in its elegance, so take a moment to understand it carefully.

Let us count the number of factors of 360, which can be prime-factored as:

\[360 = {2^3} \times {3^2} \times {5^1}\]

To form a factor of 360, we need:

  • a certain number of 2’s (from a minimum of 0 to a maximum of 3) – thus, the number of ways of selecting 2’s is 3 + 1 or 4

  • a certain number of 3’s (from a minimum of 0 to a maximum of 2) – this means that the number of ways of selecting 3’s is 2 + 1 or 3

  • a certain number of 5’s (either 0 or 1) – which means that the number of ways of selecting 5’s is 2

Thus, the number of ways to form a factor of 360 is \(4 \times 3 \times 2\) or 24. In other words, 360 has 24 factors. You can verify this explicitly if you want to.

Example 2: How many factors does 1000 have?

Solution:. We note that \(1000 = {2^3} \times {5^3}\), and so the number of factors of 1000 is \(\left( {3 + 1} \right)\left( {3 + 1} \right) = 16\).

Example 3: Find the number of factors of 16200.

Solution: We prime-factorize the given number:

\[16200 = {2^3} \times {3^4} \times {5^2}\]

Thus, the number of factors of 16200 is:

\[\left( {3 + 1} \right)\left( {4 + 1} \right)\left( {2 + 1} \right) = 60\]

In general, we note that for a number n whose prime-factored form is:

\[n = {p_1}^{{k_1}} \times {p_2}^{{k_2}} \times ... \times {p_m}^{{k_m}}\],

the number of factors of n is

\[\left( {{k_1} + 1} \right)\left( {{k_2} + 1} \right)...\left( {{k_m} + 1} \right)\]

Example 4: The 100-switches problem: In a long corridor, there are 100 switches in a row, numbered 1 to 100. Initially, all of them are in the off mode. Let us label one end of the corridor as A, and the other end as B. Flipping a switch is changing its state: if the switch is off, flipping it is changing it to on, and vice-versa. Now, the following sequence of events takes place:

  • Manan walks from A to B, flipping all the switches

  • Now, Aanan walks from A to B, flipping all the switches at intervals of 2 (that is, switches numbered 2, 4, 6, …, 100).

  • Next, Manan walks from A to B, flipping all the switches at intervals of 3 (switches numbered 3, 6, 9, …, 99).

  • Next, Aanan walks from A to B, flipping all the switches at intervals of 4…

  • …and so on, till the final pass, where Aanan flips all the switches at intervals of 100 (there is only one such switch, numbered 100).

Which switches will be left in the on mode now?

Solution:This is a beautiful problem involving basic number properties. Note that:

  • a switch will be in the on mode if it has been flipped an odd number of times

  • the number of times a switch is flipped is the number of the factors of the switch number. For example, switch number 8 will be flipped 4 times, at Pass-1, Pass-2, Pass-4 and Pass-8.

Clearly, a switch will be in the on mode if the switch number has an odd number of factors. The question now reduces to: which numbers from 1 to 100 have an odd number of factors?

We noted above that a number n with the prime-factored form

\[n = {p_1}^{{k_1}} \times {p_2}^{{k_2}} \times ... \times {p_m}^{{k_m}}\]

will have a number of factors equal to

\[\left( {{k_1} + 1} \right)\left( {{k_2} + 1} \right)...\left( {{k_m} + 1} \right)\]

When is this number odd? Clearly, when all the \({k_i}'{\rm{s}}\) are even, which would imply n being a perfect square (as discussed earlier).

Thus, all the perfect-square numbered switches will be in the on mode: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Now, we consider another problem on factors. Can you find the sum of all the factors of 72, without explicit addition of all the factors?

We saw a technique of counting the number of factors of any number using its prime-factored form, without explicit counting. Can we do something similar for the sum of the factors?

The prime-factored form of 72 is \({2^3} \times {3^2}\). Any factor of 72 is of the form \({2^i} \times {3^j}\), where i is from the set {0, 1, 2, 3}, and j is from the set {0, 1, 2}. We need to find the sum of all such numbers of the form \({2^i} \times {3^j}\), give the specified constraints.

Consider the following expression:

\[S = \left( {{2^0} + {2^1} + {2^2} + {2^3}} \right)\left( {{3^0} + {3^1} + {3^2}} \right)\]

When we expand this product, any term will be of the form \({2^i} \times {3^j}\) satisfying the desired constraints for i and j, and S will be the sum of all such terms! Thus, S is the required sum of all the factors:

\[S = 15 \times 13 = 195\]

Take another example: \(n = 450\). Let us calculate the sum of all the factors of n. The prime-factored form of n is:

\[n = {2^1} \times {3^2} \times {5^2}\]

We need to find the sum of all terms of the form \({2^i}{3^j}{5^k}\), where i is in {0, 1}, j is in {0, 1, 2}, and k is in {0, 1, 2}. We consider the following expression:

\[S = \left( {{2^0} + {2^1}} \right)\left( {{3^0} + {3^1} + {3^2}} \right)\left( {{5^0} + {5^1} + {5^2}} \right)\]

Clearly, any term in the expanded expression for S will be a factor of 450, and all the factors will be included. Thus,

\[S = 3 \times 13 \times 31 = 1209\]

In general, for a number n whose prime-factored form is:

\[n = {p_1}^{{k_1}} \times {p_2}^{{k_2}} \times ... \times {p_m}^{{k_m}},\]

the sum of all the factors of n is

\[\begin{array}{l}\left( {{p_1}^0 + {p_1}^1 + {p_1}^2... + {p_1}^{{k_1}}} \right)\\ \times \left( {{p_2}^0 + {p_2}^1 + {p_2}^2... + {p_2}^{{k_2}}} \right)\\...\\ \times \left( {{p_m}^0 + {p_m}^1 + {p_m}^2... + {p_m}^{{k_m}}} \right)\end{array}\]

Example 5: Find the sum of all the factors of 3000.

Solution: We have:

\[n = 3000 = {2^3} \times {3^1} \times {5^3}\]

Thus, the sum S of the factors is given by:

\[\begin{align}&S = \left( {1 + 2 + {2^2} + {2^3}} \right)\\&\,\,\,\,\;\; \times \left( {1 + 3} \right) \times \left( {1 + 5 + {5^2} + {5^3}} \right)\\&\,\,\,\, = 15 \times 4 \times 156 = 9360\end{align}\]

Before closing this section, we consider another problem. In a previous chapter, we have encountered the factorial notation:

\[n! = n \times \left( {n - 1} \right) \times \left( {n - 2} \right) \times ... \times 1\]

Now, consider the following problem: in the prime-factored form of 50!, what will be the power of 2? We count this as follows:

  • First, we note that all the even numbers from 1 to 50, namely, 2, 4, 6, …, 50, will each contribute a 2.

  • Next, we note that the multiples of 4, namely, 4, 8, 12, …, 48, will each contribute an additional 2.

  • Next, the multiples of 8, namely, 8, 16, 24, …, 48, will contribute yet another 2 each.

  • The multiples of 16, namely, 16, 32, 48, will contribute one more 2 each

  • Finally, the multiples of 32 (only 32 in this case) will contribute another 2.

 

Recall the greatest integer notation. For an integer x, the greatest integer less than or equal to x is denoted by [x]. The total number of 2’s contributed above can now be written as:

\[\begin{align}&\left[ {\frac{{50}}{2}} \right] + \left[ {\frac{{50}}{4}} \right] + \left[ {\frac{{50}}{8}} \right] + \left[ {\frac{{50}}{{16}}} \right] + \left[ {\frac{{50}}{{32}}} \right]\\& = 25 + 12 + 6 + 3 + 1 = 47\end{align}\]

Similarly, the power of 3 in 50! can be written as:

\[\begin{align}&\left[ {\frac{{50}}{3}} \right] + \left[ {\frac{{50}}{{{3^2}}}} \right] + \left[ {\frac{{50}}{{{3^3}}}} \right]\\& = 16 + 5 + 1 = 22\end{align}\]

The power of 5 in 50! would be:

\[\begin{align}&\left[ {\frac{{50}}{5}} \right] + \left[ {\frac{{50}}{{{5^2}}}} \right]\\ &= 10 + 2 = 12\end{align}\]

You are now asked this question: at the end of the number 50!, how many 0’s are there? We note that 50! has 47 2’s and 12 5’s. A pair of 2 and 5 will form a 10, and contribute a 0. Since there are only 12 5’s, the number of 0’s contributed will 12. Thus, there will be 12 0’s at the end of 50!.

Example 6: How many 0’s are there at the end of 100!?

Solution: First, we count the number of 2’s in 100!:

\[\begin{align}&\left[ {\frac{{100}}{2}} \right] + \left[ {\frac{{100}}{{{2^2}}}} \right]+ \left[ {\frac{{100}}{{{2^3}}}} \right]\\& \qquad\qquad  + \left[ {\frac{{100}}{{{2^4}}}} \right] + \left[ {\frac{{100}}{{{2^5}}}} \right] + \left[ {\frac{{100}}{{{2^6}}}} \right]\\& = 50 + 25 + 12 + 6 + 3 + 1 = 97\end{align}\]

The number of 5’s will be:

\[\begin{align}&\left[ {\frac{{100}}{5}} \right] + \left[ {\frac{{100}}{{{5^2}}}} \right]\\ &= 20 + 4 = 24\end{align}\]

Thus, the number of 0’s generated will be 24.

Learn math from the experts and clarify doubts instantly

  • Instant doubt clearing (live one on one)
  • Learn from India’s best math teachers
  • Completely personalized curriculum