determining the greatest $n$ for which $3^n$ divides $30!$

Question

Determine the greatest integer $n$ such that $3^n\mid 30!$

I have no idea of how to approach this problem. I would first calculate $30!$ but obviously that number is way too large. Any help?

Answer 1

How many factors of $3$ go into $30!$?

To answer this consider how many multiples of $3$s go into $30$, and then how many multiples of $9$s go into $30$, then $27$ etc.

The process above can be expressed as the sum:

\begin{align} \sum\limits^\infty_{n = 1} \left\lfloor\dfrac{30}{3^n}\right\rfloor & = \left\lfloor\dfrac{30}{3}\right\rfloor + \left\lfloor\dfrac{30}{9}\right\rfloor + \left\lfloor\dfrac{30}{27}\right\rfloor + \left\lfloor\dfrac{30}{81}\right\rfloor + \cdots \\ & = 10 + 3 + 1 + 0 + 0 + \cdots \\ & = 14. \end{align}

Answer 2

Consider the multiples of $3$ less than or equal to $30$.

$30=3\times5\times2\\ 27=3^3\\ 24=3\times2^3\\ 21=3\times7\\ 18=3^2\times2\\ 15=3\times5\\ 12=3\times2^2\\ 9=3^2\\ 6=3\times2\\ 3 = 3\times1$

You should count $14$ three's. So $n=14$.

Answer 3

Imagine that a number of the form $3^k b$, where $b$ is not divisible by $3$, has to pay a $k$ dollar tax.

So for example $6$ has to pay a $1$ dollar tax, while $18$ has to pay $2$ dollars. And $810$ has to pay $4$ dollars.

We want the total tax paid by the numbers $1$ to $30$ inclusive.

The Taxwoman collects the tax in a funny way. First she collects $1$ dollar from all the people who owe tax. So she collects $1$ dollar from all the multiples of $3$ from $1$ to $30$. There are $10=\lfloor 30/3\rfloor$ such numbers. Now she has $\$10$.

Note that $9,18,27$ still owe tax. She goes around and collects $1$ dollar from the $\lfloor 30/3^2\rfloor$ people who still owe tax. She collects $\$3$.

But $27$ still owes tax. She goes around and collects $1$ dollar from the $\lfloor 30/3^3\rfloor$ people who still owe. She gets $\$1$.

Total take: $10+3+1$.

The idea generalizes. Instead of $30$, we can use any positive integer. Instead of $3$, we can use any prime.