Breathtaking Exponent

Number Theory Level 3

Find the sum of all positive values of $n$ such that ${ 3 }^{ n }$ divides $100!$ completely.

The answer is 1176.

2 solutions

Vighnesh Raut
Jun 2, 2014

We know that the maximum value of n such that ${3}^{n}$ completely divides 100! is

$\left\lfloor \frac { 100 }{ 3 } \right\rfloor +\left\lfloor \frac { 100 }{ 9 } \right\rfloor +\left\lfloor \frac { 100 }{ 27 } \right\rfloor +\left\lfloor \frac { 100 }{ 81 } \right\rfloor$

= 33 + 11 + 3 + 1 = 48.

So, n can vary from 1 to 48.

Therefore, sum of all values of n is $\cfrac { 48(48+1) }{ 2 }$ = 1176

Please explain to me the theory about this :)

Firstson Sihombing - 6 years, 10 months ago

It is Legendrè's theorem to find the largest power of a prime $p$ that divides $n !$ . It is given by $k(n!) = \sum ^{\infty }_{i=1}\left[ \dfrac {n}{p_{i}} \right]$ . Here, $[ ]$ denotes the floor or greatest integer function, defined as $[n] =$ the greatest integer not exceeding $x$ . Don't get scared about the infinite sum ( Even I got scared unnecessarily when I was new to this !), as at some point $p_{j}, 1 \leq p_{j} < \infty$ , the sum becomes zero for every next term. So you gotta identify that point and calculate the sum till there only.

Venkata Karthik Bandaru - 6 years, 2 months ago

Look here . The idea is the same, except $3$ is used here instead of $5$ .

mathh mathh - 6 years, 10 months ago

Curtis Clement
Feb 16, 2015

Highest power that can divide 100! $= \displaystyle\sum_{k=1}^{\infty} \lfloor \frac{100}{3^k} \rfloor = \lfloor \frac{100}{3} \rfloor + \lfloor \frac{100}{9} \rfloor + \lfloor \frac{100}{27} \rfloor + \lfloor \frac{100}{81} \rfloor = 33 + 11 + 3 +1 = 48$ So now all we have to do is calculate the sum of all integers from 1 to 48 as follows $1+2+3+...+48 = \frac{48\times\ 49}{2} = \boxed{1176}$

Breathtaking Exponent

The answer is 1176.

2 solutions

0 pending reports