Online Course Discussion Forum

Math Challenge II-A Number Theory 9.2

 
 
Picture of John Lensmire
Re: Math Challenge II-A Number Theory 9.2
by John Lensmire - Thursday, December 30, 2021, 3:53 PM
 

Let's look at a smaller version of part (b). Let's suppose we want to find the number of zeros at the end of $25!$.

First, let's start with the answer. If you calculated the full prime factorization, you would get $$25!= 2^{22}\cdot 3^{10}\cdot 5^6\cdot 7^3\cdot 11^2\cdot 13\cdot 17\cdot 19\cdot 23.$$ Focusing on powers of $2$ and powers of $5$, we have $22$ powers of $2$ and $6$ powers of $5$, so $25!$ ends in $6$ zeros.

The real question, however, is how to efficiently calculate that there are $22$ powers of $2$ and $6$ powers of $5$.

Starting with the powers of $5$, first note that only the multiples of $5$ matter. So instead of looking at the full $25!$ we can look at $5\cdot 10\cdot 15\cdot 20\cdot 25$. On first glance, there are $5$ multiples of $5$, but this is forgetting that we have $25 = 5^2$. The idea is that $25 = 5^2$ has an extra power of $5$. This is where the "one extra power" idea comes from. For the 5s, $5, 10, 15, 20, 25$ each give one power of $5$, with $25$ giving an "extra" power for a total of $5+1 = 6$.

The same type of idea can work for the powers of $2$. All the even numbers, $2, 4, 6, 8, \ldots, 24$ ($12$ which is $\lfloor \frac{25}{2}\rfloor$) each give a power of $2$ to the prime factorization. But, all the multiples of $4 = 2^2$, $4, 8, 12, 16, 20, 24$ ($6$ which is $\lfloor \frac{25}{4}\rfloor$) each have an "extra" power. Similarly the multiples of $8$, $8, 16, 24$ ($3$ which is $\lfloor \frac{25}{8}\rfloor$) give another, with $16$ ($1$ which is $\lfloor \frac{25}{16} \rfloor$) gives one final power of $2$. Hence there are $12 + 6 + 3 + 1 = 22$ powers of $2$ in the prime factorization as needed.

As you look at more examples of these, it becomes fairly clear that there are always more powers of $2$ (because $2$ is smaller than $5$), so that's why we typically focus on the powers of $5$.

Note I talked about the $25!$ example and this problem a little more in a Thursday Tidbit this year which is linked below: