What is the largest positive integer $n$ in that $3^n$ is a factor of $200!$?

949 Views Asked by At

I tried to solve this like this:

$200! = 1 * 2 * 3 ... * 199 * 200$

Of these numbers, only $1 (3^0), 3(3^1), 9(3^2), 27(3^3),$ and $81(3^4)$ are below $200$

So if I multiply them, I would get $3^{0+1+2+3+4}=3^{10}$

Does that mean that $10$ is the largest integer power of $3$ that would be a factor of $200!$

1

There are 1 best solutions below

0
On

To cumpute the largest $n$ such that $3^n|200!$, we have to count how many $3$ divide the product $$200\cdot199\cdot198\cdots3\cdot2\cdot1$$ So, let $N$ this number. We can define this number as: $$N=\sum_{i=1}^{\left \lfloor \log_3(200) \right \rfloor}\left \lfloor \frac{200}{3^i} \right \rfloor=\left \lfloor \frac{200}{3} \right \rfloor+\cdots+\left \lfloor \frac{200}{81} \right \rfloor=66+22+7+2=97$$ So, the number $3^{97}|200!$ and $n=97$.

This formula is known also as Legendre's formula.