Prime Powers in Factorials

In the previous post in the series on Counting Principles, we looked at the technique of partitions. I concluded with the promise to deal with the exponent of prime p in the number n!. And you may be wondering what in the world that means. First, let us remind ourselves what n! denotes. Read ‘n factorial’, it is defined as the product of all natural numbers up to and including n. Hence, 2! = 1 × 2, 5! = 1 × 2 × 3 × 4 × 5, etc.

Now suppose we divide 5! by 2. How many times can we do it before we get a remainder? Now, 5! = 120. Dividing this by 2 gives us 60. Dividing this by 2 gives us 30. Dividing this by 2 gives us 15. Since 15 is an odd number, we cannot divide it by 2 without getting a remainder. Hence, 120 could be divided by 2 three times. Hence, the exponent of 2 in 5! is 3, which is to say that the largest possible power of 2 that can divide 5! is 2³.

In a similar way, 7! = 5040. Let us try to divide by 3. 5040 divided by 3 gives us 1680. Dividing this by 3 gives 560. Now, it is clear that 560 is not divisible by 3. Hence, the exponent of 3 in 7! is 2, which means that the largest power of 3 that can divide 7! is 3².

Our purpose here is to obtain a generalized method of obtaining this exponent without actually performing the division. Let us look closer at the division of 7! by 3. 7! can be expanded as

It is clear that only the numbers in red allow a division by 3. And there are two such numbers. Since we are dividing by 3, we can realize that every third number will be a multiple of 3. Hence, since we are dealing with 7!, and 7 ÷ 3 = 2 ⅓, we can conclude that there will be two multiples of 3 from 1 to 7. Hence, the exponent of 3 in 7! is 2.

If, on the other hand, we wanted to find the exponent of 3 in 20!, we would proceed as follows.

Once again, the numbers in red allow a division by 3. However, the numbers is purple allow for a division by 9, that is 3². Here we can see that every third number is a multiple of 3 and every ninth number is a multiple of 9. This is obvious. Since 20 ÷ 3 = 6 ⅔, there will be 6 multiples of 3 from 1 to 20. And since 20 ÷ 9 = 2 ²⁄₉, there will be 2 multiples of 9 from 1 to 20. Since each multiple of 9 contributes another factor of 3, this means that the exponent of 3 in 20! will be 6 + 2 = 8. We can check this an perform

which is clearly not divisible by 3. Let us proceed to generalize this result for any number n! and any prime p.

First let us define the floor function. Given a real number x, the floor function is defined as follows

In plain English, the floor of x, denoted by ⌊x⌋ is the greatest integer that is less than or equal to x. Hence, if x = 2.1, ⌊x⌋ = 2. If x = 3.78, ⌊x⌋ = 3. Care must be taken with negative numbers. If x = -2.93, ⌊x⌋ = -3. If x = -5.41, ⌊x⌋ = -6. Of course, if x = 7, ⌊x⌋ = 7 and if x = -7, ⌊x⌋ = -7.

Consider the earlier calculations, 7 ÷ 3 = 2 ⅓, 20 ÷ 3 = 6 ⅔, and 20 ÷ 9 = 2 ²⁄₉, giving us 2 multiples of 3, 6 multiples of 3, and 2 multiples of 9 respectively. It is clear that these numbers represent the floors ⌊2 ⅓⌋ = 2, ⌊6 ⅔⌋ = 6, and ⌊2 ²⁄₉⌋ = 2.

In other words, when determining the exponent of 3 in 7!, we obtained ⌊7 ÷ 3⌋ = 2, to give the result of 2. Similarly, when determining the exponent of 3 in 20!, we obtained ⌊20 ÷ 3⌋ = 6 and ⌊20 ÷ 3²⌋ = 2, to give the result of 8.

We are now in a position to generalize the result. In general, every p^th number will be a multiple of p. Even more generally, every (p^k)^th number will be a multiple of p^k. Hence, there will be ⌊n ÷p⌋ multiples of p from 1 to n, ⌊n ÷p²⌋ multiples of p from 1 to n, ⌊n ÷p³⌋ multiples of p³ from 1 to n, etc.

Hence, the exponent of p in n! is given by

Let us use this result to determine the exponent of 3 in 100!. Since 3⁴ ≤ 100 ≤ 3⁵, r = 4. Hence,

If we perform the calculation we will realize that

which is not divisible by 3.

So, how many zeroes are there at the end of 100!? Now, a zero at the end of a number indicates a multiple of 10. So we are trying to determine the exponent of 10 in 100!. However, 10 = 2 × 5. Moreover, for every multiple of 5, we have at least 2 multiples of 2. See the figure below, where numbers in red are multiples of 2 but not 5, numbers in purple are multiples of 5 but not 2, and numbers in green are multiples of 2 and 5.

There are at least 2 red or green numbers for each purple or green number. Hence, to find the exponent of 10 in 100!, we need only to find the exponent of 5 in 100!. Per the earlier formula, this is

This means that there are 24 zeroes at the end of 100!. Indeed, we can use a computational engine and determine that

100! = 93, 326, 215, 443, 944, 152, 681, 699, 238, 856, 266, 700, 490, 715, 968, 264, 381, 621, 468, 592, 963, 895, 217, 599, 993, 229, 915, 608, 941, 463, 976, 156, 518, 286, 253, 697, 920, 827, 223, 758, 251, 185, 210, 916, 864, 000, 000, 000, 000, 000, 000, 000, 000. It is clear that there are 24 zeroes at the end of the number.

In this post we dealt with the exponent of a prime p in the number n!. We obtained a relatively easy to apply formula to determine this. In the next post, we will tackle what are known as derangements. Till then, stay sane!