# What is the greates positive integer...

• Dec 13th 2006, 04:42 PM
ceasar_19134
What 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 PM
ThePerfectHacker
Quote:

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

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$