What is the greatest positive integer n such that 3^n is a factor of 200! ?

Printable View

- Dec 13th 2006, 04:42 PMceasar_19134What is the greates positive integer...
What is the greatest positive integer n such that 3^n is a factor of 200! ?

- Dec 13th 2006, 04:58 PMThePerfectHacker
What you actually want to know is how many times is 200! factorial divisible by 3.

Now, there is a theorem from number theory that says, (by a mathemation I respect, Legendre)

$\displaystyle

\boxed{n!=\prod_{p\leq n} p^{\sum _{k=1} ^{\infty} [n/p^k]}}$

I know, I know, one scary looking formula.

But what it is actually saying is that to find that value you need to compute,

$\displaystyle \sum_{k=1}^{\infty} \left[ \frac{n}{p^k} \right]$

Where $\displaystyle [ \, ]$ is the greatest integer function.

Now, here $\displaystyle n!=200!$ thus, $\displaystyle n=200$. And the prime is $\displaystyle p=3$.

Thus,

$\displaystyle \sum_{k=1}^{\infty} \left[ \frac{200}{3^k} \right]$

This sum is actually finite!

Because when the exponent gets large enough the greatest integer will be zero. Thus you will just be summing up zeros.

Thus,

$\displaystyle [200/3]+[200/9]+[200/27]+[200/81]+[200/243]+...$

The way you evaluate is by dividing and dropping the decimal part.

$\displaystyle 66+22+7+2+0+0+0+...$

Thus it is,

$\displaystyle 97$