+0  
 
+2
72
1
avatar+775 

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
 #1
avatar+602 
+3

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

11 Online Users