Let's Find powers!

Number Theory Level 3

Find the highest power of 3 that divides 70 ! 70! .

Notation :
! ! denotes the factorial notation. For example, 10 ! = 1 × 2 × 3 × ⋯ × 10 10! = 1\times2\times3\times\cdots\times10 .

These type of questions have a direct formula. The challenge is to solve this question in an intuitive manner.


The answer is 32.

View wiki
Miraj Shah by Miraj Shah , 23, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Method 1 : Direct formula

Let p p be a prime number.
The highest power of p p that divides n ! n! is given by,
∑ i = 1 ∞ ⌊ n p i ⌋ \displaystyle \sum_{i=1}^{\infty} \left \lfloor \dfrac{n}{p^{i}} \right \rfloor which directly gives us 32 when we substitute n = 70 , p = 3 n =70, p = 3

Method 2 : Intuitive approach

The powers of 3 dividing 70! are contributed by multiples of 3.
There are 23 multiples of 3 lesser than 70.

These contribute 23 powers.
But, 7 of them are multiples of 9, which contribute 2 powers each, out which one has already been accounted for. So, we add 7 to the previous count which gives us 30.
Now, 2 of the multiples of 3, were also multiples of 27, ( 27 , 54 ) ( 27,54 ) and contribute 3 powers of 3 each, out which 2 have already been accounted for. So we add another 2. Final count : 32.
The intuitive approach is basically how the formula has been derived.

Sorry for the bad explanation .

14 Helpful 0 Interesting 0 Brilliant 0 Confused

We know 70 ! = 1 × 2 × 3 × 4....70 70! = 1\times 2\times 3\times 4....70

Now, since we need to find the power of 3 3 let us rearrange the above product by writing all the multiples of 3 3 together.

70 ! = ( 3 × 6 × 9 × 12....69 ) ( 1 × 2 × 4 × 5 × 7...70 ) 70! = (3\times6\times9\times12....69)(1\times2\times4\times5\times7...70)

Now write the multiples of 3 3 (That we have rearranged and wrote together above) in the form of 3 n 3n

70 ! = ( ( 3 × 1 ) ( 3 × 2 ) ( 3 × 4 ) . . . ( 3 × 23 ) ) ( 1 × 2 × 4...70 ) 70! = ((3\times1)(3\times2)(3\times4)...(3\times23))(1\times2\times4...70)

Now collect all the 3 ′ s 3's together..

70 ! = ( 3 23 ) ( 1 × 2 × 3 × 4 × 5...23 ) ( 1 × 2...70 ) 70! = (3^{23})(1\times2\times3\times4\times5...23)(1\times2...70)

Now again the 2 n d 2^{nd} bracket can be rearranged and all the multiples of 3 3 can be written together...

70 ! = ( 3 23 ) ( 3 × 6 × 9 × 12 × . . . 21 ) ( 1 × 2 × 3..23 ) ( 1 × 2 × 4...70 ) 70! = (3^{23})(3\times6\times9\times12\times...21)(1\times2\times3..23)(1\times2\times4...70)

Once again write the 2 n d 2^{nd} bracket in the form of 3 n 3n and collect all the 3 ′ s 3's together.

70 ! = ( 3 23 ) ( 3 7 ) ( 1 × 2 × 3 × 4...7 ) ( 1 × 2 × 4...23 ) ( 1 × 2 × 4...70 ) 70! = (3^{23})(3^{7})(1\times2\times3\times4...7)(1\times2\times4...23)(1\times2\times4...70)

70 ! = ( 3 30 ) ( 1 × 2 × 3 × 4...7 ) ( . . . . . . . . ) ( . . . . . . . . ) 70! = (3^{30})(1\times2\times3\times4...7)(........)(........)

Following the same method the 2 n d 2^{nd} bracket can be written as

70 ! = ( 3 30 ) ( 3 × 6 ) ( 1 × 2 × 4 × 5 × 7 ) ( . . . . . . . . ) ( . . . . . . . . ) 70! = (3^{30})(3\times6)(1\times2\times4\times5\times7)(........)(........)

70 ! = ( 3 32 ) ( 1 × 2 ) ( . . . . . . . ) ( . . . . . . . ) ( . . . . . . . ) 70! = (3^{32})(1\times2)(.......)(.......)(.......)

Hence the highest power of 3 in 70 ! 3 \text{ in } 70! is 32 \boxed{32}

I think this is what you meant!

Miraj Shah - 5 years, 3 months ago

Exactly. That is the intuitive approach behind the formula.

And the explanation is good too!(+1)

Harsh Khatri - 5 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...