Hi, I was doing problems in my book when I came across this one:

How many trailing zeros are in $100!$ when written in base 12?

Of course, you need to first count the exponents of $2$ and $3$ in $100!$ first:

$\lfloor \frac{100}{2} \rfloor + \lfloor \frac{100}{2^2} \rfloor + \lfloor \frac{100}{2^3} \rfloor + \lfloor \frac{100}{2^4} \rfloor + \lfloor \frac{100}{2^5} \rfloor + \lfloor \frac{100}{2^6} \rfloor = 50 + 25 + 12 + 6 + 3 + 1 = 87$

$\lfloor \frac{100}{3} \rfloor + \lfloor \frac{100}{3^2} \rfloor + \lfloor \frac{100}{3^3} \rfloor + \lfloor \frac{100}{3^4} \rfloor = 33 + 11 + 3 + 1 = 48$

The number of terms that is in both sets is $48.$ So $48$ trailing zeros.

Then I wonder and think backwards, if there are $48$ trailing zeros for $k!$ when written in base 12, then what is $k?$

Even more generic: if there are $a$ trailing zeros for $b!$ when written in base $c$, then what are possible values for $(a,b,c)?$

 Jul 27, 2021

Good questions! I'll first talk about the first question, then the second. 


1. Notice that the value that is always less is 3. Hence we want the largest power of $3$ dividing $k!$ to be $48$, i.e. $3^{48}|k$ but $3^{49}\nmid k$. In terms of p-adics (look it up), $\nu_3(k!)=48$. Think about what happens when we make $100$ higher or lower. If we go below $99$, we lose a power of $3$, which we don't want! If we go above $102$, we gain another power of $2$, which we also don't want. So $k=99,100,101,102$. Try this with other cases. Note the number of possible answers.


2. In terms of p-adics, it's the following: Let $p$ be the largest prime factor of $c$. We want $\nu_p(b!)=a$. Again, try finding a $b$ that works, then adjusting (this brings up a new technique, very useful in inequalities -- smoothing).


What you are brushing up on leads to very hard problems, and very useful problems at that, specifically in cryptography. I encourage you to try your best to understand this: https://en.wikipedia.org/wiki/P-adic_number.

 Jul 27, 2021
edited by thedudemanguyperson  Jul 27, 2021

23 Online Users