The largest natural number n such that 3ⁿ divides 66 ! is ___________.

Solution

Maths sir · 3 steps

Count the 3s factor by factor: multiples of 3, then 9, then 27, and add them up.

1. Legendre's formula. Every multiple of 3 up to 66 gives one factor of 3. Every multiple of 9 gives one extra, and every multiple of 27 one more. Adding these counts gives the power of 3 in 66!.

   ⌊ 66/3 ⌋ + ⌊ 66/9 ⌋ + ⌊ 66/27 ⌋ + ⌊ 66/81 ⌋

2. Put in numbers. ⌊ 66/3 ⌋ = 22, ⌊ 66/9 ⌋ = 7, ⌊ 66/27 ⌋ = 2, and ⌊ 66/81 ⌋ = 0, so you stop there.
3. So. The power of 3 in 66! is 22 + 7 + 2 = 31, so the largest n is 31.

The common slip: 22. Counting only the multiples of 3 gives 22, not 31. Numbers like 9, 18 and 27 carry more than one factor of 3, so the ⌊ 66/9 ⌋ and ⌊ 66/27 ⌋ terms must be added too.

The idea to keep. For the power of a prime p in N!, add ⌊ N/p ⌋ + ⌊ N/p² ⌋ + … until the power of p exceeds N. Numbers like 9 and 27 hide extra factors of 3.

Answer from the NTA final answer key. Solution by PrepWiser.