The product of the first seven positive integers is equal to \[7 \times 6\times 5\times 4\times 3\times 2\times 1= 5040\] Mathematicians will write this product as \(7!\). This is read as “\(7\) factorial”. So, \(7! = 7 \times 6\times 5\times 4\times 3\times 2\times 1= 5040\).
This factorial notation can be used with any positive integer. For example, \(11! = 11 \times 10 \times 9 \times \cdots \times 3 \times 2 \times 1 = 39\,916\,800\). The three dots “\(\cdots\)” represent the product of the integers between \(9\) and \(3\).
Suppose \(N = 1000!\). That is, \[N = 1000! = 1000 \times 999 \times 998\times 997 \times \cdots \times 3\times 2\times 1\]
Note that \(N\) is divisible by \(5\), \(25\), \(125\), and \(625\). Each of these factors is a power of \(5\). That is, \(5=5^1\), \(25 = 5^2\), \(125= 5^3\), and \(625 = 5^4\).
Determine the largest power of \(5\) that divides \(N\).
Solution 1
In order to determine the largest power of \(5\) that divides \(N\), we need to count the number of times the factor \(5\) appears in the prime factorization of \(N\).
Since \(N\) is equal to the product of the integers from \(1\) to \(1000\), let’s first look at which of these integers are divisible by \(5\). The integers from \(1\) to \(1000\) that are divisible by \(5\) are \(5, 10, 15, 20, \ldots, 990, 995, 1000\). That is, a total of \(\frac{1000}{5} = 200\) integers from \(1\) to \(1000\) are divisible by \(5\).
Each integer that is a multiple of \(25\) will add an additional factor of \(5\), since \(25 = 5\times 5\). There are \(\frac{1000}{25} = 40\) integers from \(1\) to \(1000\) that are multiples of \(25\). These integers give another \(40\) factors of \(5\) bringing the total to \(200+40 = 240\).
Each integer that is a multiple of \(125\) will add an additional factor of \(5\). This is because \(125 = 5\times 5\times 5\), and two of the factors have already been counted when we looked at \(5\) and \(25\). There are \(\frac{1000}{125} = 8\) integers from \(1\) to \(1000\) that are multiples of \(125\). These integers give another \(8\) factors of \(5\) bringing the total to \(240+8 = 248\).
Each integer that is a multiple of \(625\) will add an additional factor of \(5\). This is because \(625 = 5\times 5\times 5\times 5\), and three of the factors have already been counted when we looked at \(5\), \(25\) and \(125\). There is \(1\) integer from \(1\) to \(1000\) that is a multiple of \(625\), namely, \(625\). This integer gives another factor of \(5\) bringing the total to \(248 + 1 = 249\).
The next power of \(5\) is \(5^5= 3125 >1000\), so we have counted all factors of \(5\) in \(1000!\).
Thus, the prime factorization of \(N\) contains exactly \(249\) factors of \(5\). Therefore, the largest power of \(5\) that divides \(N\) is \(5^{249}\).
Solution 2
There are many similarities between Solution 1 and the following solution. In this solution we will divide out factors of \(5\) until there are none left.
In the integers from \(1\) to \(1000\), there are \(\frac{1000}{5}=200\) integers that are divisible by \(5\), namely, \(5,10,15,\ldots,990,995,1000\). If we divide each of these integers by \(5\), we obtain the second list \(1,2,3,\ldots,198,199,200\).
This second list contains \(\frac{200}{5}=40\) integers that are divisible by \(5\), namely, \(5,10,15,\ldots,190,195,200\). If we divide each of these integers by \(5\), we obtain the third list \(1,2,3,\ldots,38,39,40\).
This third list contains \(\frac{40}{5}=8\) integers that are divisible by \(5\), namely, \(5,10,15,20,25,30,35,40\). If we divide each of these integers by \(5\), we obtain the fourth list \(1,2,3,4,5,6,7,8\).
This fourth list contains \(1\) integer that is divisible by \(5\), namely the integer \(5\).
In total, there are \(200+40+8+1=249\) factors of 5 in \(1000!\). Therefore, the largest power of 5 that divides \(N\) is \(5^{249}\).
An interpretation of what has happened is in order. When we created the first list of multiples of \(5\), we discovered that there were \(200\) integers from \(1\) to \(1000\) that are divisible by \(5\). When we created the second list of multiples of \(5\), we were actually counting the \(40\) integers from \(1\) to \(1000\) that are divisible by \(25\). When we created the third list of multiples of \(5\), we were actually counting the \(8\) integers from \(1\) to \(1000\) that are divisible by \(125\). And finally, when we created the fourth list of multiples of \(5\), we were actually counting the \(1\) integer from \(1\) to \(1000\) that is divisible by \(625\).