What is the maximum value of $n$ for which $3^n$ divides 1000!?

Question

What is the maximum value of $n$ for which $3^n$ divides 1000!

Am I supposed to look at it as a congruence... or apply euclid's algorithm somewhere? I'm lost

I can't use simple arithmetics... Someone help.

Answer 1

$3$ divides every $3^{rd}$ factor of $1000!$

$3^2$ divides every $9^{th}$ factor.

$3^3$ divides every $27^{th}$ factor.

etc.

$n = \lfloor \frac {1000}{3}\rfloor + \lfloor \frac {1000}{9}\rfloor + \lfloor \frac {1000}{27}\rfloor + \lfloor \frac {1000}{81}\rfloor\cdots\\ 333+111+37+12+4+1$

Answer 2

The number of $3$ in the prime factorization of $1000!$ is given by:

$$n = \left[\frac{1000}{3}\right]+\left[\frac{1000}{3^2}\right]+\left[\frac{1000}{3^3}\right]+\left[\frac{1000}{3^4}\right]+\left[\frac{1000}{3^5}\right] + \left[\frac{1000}{3^6}\right]$$ $$ = 333 + 111 + 37 + 12 + 4 + 1 = 498$$

To see why this formula is true, not that the first terms counts the number from $1$ to $1000$ divisible by $3$. The second one counts the number from $1$ to $1000$ divisible by $9$ and so on.

Answer 3

Well, as the neither the headline nor the text does indicate some missed faculty symbol, the answer is just: 0.

1000 has no divisor 3. Nor does it have a divisor $3^n$ for any $n>0$. But $3^0=1$ surely does divide 1000.

--- rk