Question

Find the exponent of 3 in 100!

Answer 1

Use the fact that the exponent of a prime p in n! is given by $\sum\limits_{r=1}^{\infty }{\left[ \dfrac{n}{{{p}^{r}}} \right]}$, where [x] is the greatest integers less or equal to x. Use the fact that 3 is a prime number. Hence find the power of 3 in 100!.

Complete step-by-step answer:
Before solving the question, we need to understand what exponent of a number(p) in number q means.
The exponent of a number p in q is the largest number r such that ${{p}^{r}}$ divides q.
Hence, we have that if r is the exponent of p in q, then ${{p}^{x}}$ divides q $\forall 0\le x\le r$ and ${{p}^{x}}$ does not divide q $\forall x\ge r+1$.
Now consider the number q = n! and p such that p is prime.
We know that $n!=1\times 2\,\times 3\times \cdots \times \left( n-1 \right)\times n$
The only numbers in the product which are divisible by p are $p,2p,...$
There are $\left[ \dfrac{n}{p} \right]$ such numbers.
The numbers in the product which are divisible by ${{p}^{2}}$ are ${{p}^{2}},2{{p}^{2}},\cdots$
There are $\dfrac{n}{{{p}^{2}}}$ such numbers.
Continuing this way the number of numbers in the product which are divisible by ${{p}^{r}}$ is $\left[ \dfrac{n}{{{p}^{r}}} \right]$.
The numbers which are divisible by ${{p}^{2}}$ are also divisible by p.
Hence the exponent of these numbers is one counted in $\left[ \dfrac{n}{p} \right]$ and one in $\left[ \dfrac{n}{{{p}^{2}}} \right]$ which accounts for the total contribution in the exponent by these numbers.
Hence, we have the exponent of prime p in n! is $\left[ \dfrac{n}{p} \right]+\left[ \dfrac{n}{{{p}^{2}}} \right]+\cdots$
Note that this is not an infinite sum since after a particular value of r ${{p}^{r}}>n$ and hence $\left[ \dfrac{n}{{{p}^{r}}} \right]=0$
Hence the above summation is equal to $\sum\limits_{\begin{smallmatrix} r\ge 1 \\\ {{p}^{r}}\le n \end{smallmatrix}}{\left[ \dfrac{n}{{{p}^{r}}} \right]}$
Hence the exponent of 3 in 100! is
$\left[ \dfrac{100}{3} \right]+\left[ \dfrac{100}{{{3}^{2}}} \right]+\left[ \dfrac{100}{{{3}^{3}}} \right]+\left[ \dfrac{100}{{{3}^{4}}} \right]=33+11+3+1=48$
Hence the exponent of 3 in 100! is 48.

Note: [1] Calculation trick:
If $\left[ \dfrac{n}{{{p}^{r}}} \right]=x$ then $\left[ \dfrac{n}{{{p}^{r+1}}} \right]=\left[ \dfrac{x}{p} \right]$
Hence do not calculate the powers of p. But take the previous result and divide it by p and hence find the value.
In the above calculation, the result of the first division is 33.
We divide 33 by 3, and we get 11 which is the result of the second division.
We divide 11 by 3, and the result is 3 (after taking Greatest integer function) which is the result of the third division and so on.