What is the smallest positive integer n such that n! is divisible by 10^{10}? — GMAT

What is the smallest positive integer $n$ such that $n!$ is divisible by $10^{10}$ ?

Answer: 45

The smallest positive integer

n

such that

n!

is divisible by

10^{10}

is 45.

To find the smallest integer

n

such that

n!

is divisible by

10^{10}

, we need

n!

to contain at least 10 prime factors of 5 (since 2s are abundant). Using Legendre's formula,

E_5(40!) = \lfloor 40/5 \rfloor + \lfloor 40/25 \rfloor = 8 + 1 = 9

, which is insufficient. For

n = 45

E_5(45!) = \lfloor 45/5 \rfloor + \lfloor 45/25 \rfloor = 9 + 1 = 10

, satisfying the requirement. Thus, 45 is the smallest positive integer.

Determine the prime factorization requirement for divisibility by

10^{10}

10^{10} = 2^{10} \times 5^{10}

. Thus,

n!

must contain at least 10 factors of 5.

The power of 2 in any factorial

n!

(where

n \ge 5

) is always strictly greater than the power of 5, making 5 the limiting prime factor.

Apply Legendre's formula for the exponent of prime

p = 5

n!

E_5(n!) = \lfloor \frac{n}{5} \rfloor + \lfloor \frac{n}{25} \rfloor + \dots \ge 10

Legendre's formula accounts for single multiples of 5, double multiples of 5 (25), etc.

Evaluate candidate values for

n

For

n = 40

E_5(40!) = 8 + 1 = 9

factors. For

n = 45

E_5(45!) = 9 + 1 = 10

factors.

Testing multiples of 5 systematically pinpoints the exact boundary where the total count of prime factor 5 reaches 10.

Finding the exponent of a prime factor in a factorial using Legendre's formula

Estimated Time:2m 0s

Question