How many multiples of 3 are in $100!$

Question

I know that $100!$ is $100\times99\times98\times...2\times1$ but I don't get how to get all the factors of three from this. Help!

Answer 1

Hints:

• Every multiple of 3 introduces a factor 3 (like 30, 96), how many of those numbers are there in 100!
• Every multiple of 9 introduces an additional factor 3 (like 36, 99), how many?
• Every multiple of 27 yet another one, and every factor 81 even one more.

Answer 2

You are looking for the 3-adic valuation of 100!, which is given by the Legendre formula $$ \lfloor \frac{100}{3} \rfloor + \lfloor \frac{100}{3^2} \rfloor+....\\ =33+11+3+1=48 $$

Answer 3

The only thing you have to do here is to calculate the highest power of $3$ contained in $100!$. It can be easily calculated using de polignac's formula.

For your question it looks like $[\frac{100}{3}]+[\frac{100}{9}]+[\frac{100}{27}]+[\frac{100}{81}]=48$

Answer 4

$$\color\red{\sum\limits_{n=1}^{\lfloor\log_{3}{100}\rfloor}\left\lfloor\frac{100}{3^n}\right\rfloor}=\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor=33+11+3+1=48$$

Answer 5

Here's a not conventional way to think of it but... it might help:

$100! = \prod_{k=1}^{100}k$

$=100*\prod_{k=1}^{99}k$

$=100*\prod_{k=1}^{33}3k*\prod_{j=1}^{33}(3j-1)*\prod_{l=1}^{33}(3l-2)$

$3\not \mid 100*\prod_{j=1}^{33}(3j+-1)\prod_{l=1}^{33}(3l-2)$

so $100!$ and $\prod_{k=1}^{33}3k$ have the same power of $3$ factors.

$\prod_{k=1}^{33}3k=3^{33}\prod_{k=1}k$

$= 3^{33}*\prod_{k=1}^{11}3k*\prod_{j=1}^{11}(3j-1)\prod_{l=1}^{11}(3l-2)$

$3\not \mid \prod_{j=1}^{11}(3j-1)\prod_{l=1}^{11}(3l-2)$

so $100!$ and $3^{33}\prod_{k=1}^{10}3k$ have the same power of $3$ factors.

$3^{33}\prod_{k=1}^{11}3k = 3^{33}3^{11}\prod_{k=1}^{11}k$

$=3^{33}3^{11}*11*10*\prod_{k=1}^33k*\prod_{j=1}^3(3j-1)*\prod_{l=1}^3(3j-2)$

And again $3 \not \mid 10*11*\prod_{j=1}^3(3j-1)*\prod_{l=1}^3(3j-2)$ so

$100!$ has same power of $3$ factor of $3^{33}3^{11}\prod_{k=1}^33k$

$3^{33}3^{11}\prod_{k=1}^33k= 3^{33}3^{11}3^{3}\prod_{k=1}^3 k$

$3^{33}3^{11}3^{3}*1*2*3$ and $3 \not \mid 2$ so

$3^{33}3^{11}3^{3}*3 = 3^{33+11+3+1} = 3^{48}$ is the highest power of $3$ that divide $100!$.

In other words $\lfloor 100/3 \rfloor=33$ of the integer terms of $1*2*3....*98*99*100$ are multiples of $3$ so $3^{33}|100!$. Of those $33$ multiples of $3$ one third of them are multiples of $9$ and so on.