Free CAT library

Factorials, Legendre’s Formula & Trailing Zeros

Unpack massive factorials to count trailing zeros, identify the highest powers of primes hidden within, and evaluate consecutive product divisibility.

1. The Story & Mental Model

A factorial like 100!100! (100×99×98⋯×1100 \times 99 \times 98 \dots \times 1) is a mathematical black hole. It contains an astronomical number of prime factors. But how many of a specific prime, say 3, are hiding inside 100!100!?

Imagine the numbers from 1 to 100 lined up.

  • First, every 3rd number (3, 6, 9...) steps forward and drops one '3' into a bucket. That's ⌊100/3⌋=33\lfloor 100/3 \rfloor = 33 threes.

  • But wait! Numbers like 9, 18, 27 have another 3 hidden inside them because they are multiples of 323^2. So every 9th number drops a second '3' into the bucket. That's ⌊100/9⌋=11\lfloor 100/9 \rfloor = 11 threes.

  • Numbers like 27, 54, 81 have a third 3! Every 27th number drops a third '3'. That's ⌊100/27⌋=3\lfloor 100/27 \rfloor = 3 threes.

  • And 81 drops a fourth 3. That's ⌊100/81⌋=1\lfloor 100/81 \rfloor = 1 three.

Count the bucket: 33+11+3+1=4833 + 11 + 3 + 1 = 48.

There are exactly 48 threes hiding in 100!100!. This elegant accounting system is Legendre’s Formula.

2. The CAT Question Blueprint

The CAT examiner will test Legendre's Formula by masking it as:

  • "Find the number of trailing zeros in 1000!1000!" (Which means finding the highest power of 10. Since 10 = 2 x 5, and 5s are rarer than 2s, just find the highest power of 5).

  • "Find the highest power of 12 that perfectly divides 50!50!" (12 is a composite number 22×32^2 \times 3. You must find the power of 2, divide by 2, find the power of 3, and take the bottleneck).

  • Combinatorics masquerading as Number Theory: "Is the product of any 10 consecutive integers always divisible by 10!?" (Yes).

3. Core Concepts, Formulae & Derivations

A. Legendre's Formula (Highest Power of a Prime)

The highest power of a prime pp that perfectly divides n!n! is:

Ep(n!)=⌊np⌋+⌊np2⌋+⌊np3⌋+…E_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots

(Stop when pk>np^k > n).

B. Highest Power of a Composite Number

If CC is a composite number, say C=pa×qbC = p^a \times q^b:

  1. Use Legendre's formula to find the highest powers of pp and qq in n!n!. Let them be XX and YY.

  2. The number of times CC can be formed is limited by the bottleneck: min⁡(⌊X/a⌋,⌊Y/b⌋)\min\left(\lfloor X/a \rfloor, \lfloor Y/b \rfloor\right).

Example: Highest power of 1212 (22×32^2 \times 3) in 100!100!. Find powers of 2 and 3. You need TWO 2s and ONE 3 to make a 12.

C. Trailing Zeros in n!

A trailing zero is created by a 1010, which is 2×52 \times 5. In any factorial, there are always way more 22s than 55s. The 55s are the bottleneck.

Therefore, the number of trailing zeros in n!n! is exactly equal to the highest power of 55 in n!n!.

Zeros=⌊n5⌋+⌊n25⌋+⌊n125⌋+…\text{Zeros} = \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{25} \right\rfloor + \left\lfloor \frac{n}{125} \right\rfloor + \dots

D. Product of Consecutive Integers

The product of any kk consecutive integers is ALWAYS perfectly divisible by k!k!.

Example: 17×18×19×2017 \times 18 \times 19 \times 20 (4 integers) is perfectly divisible by 4!4! (24).

4. Common Pitfalls & Speed Shortcuts

  • Pitfall: Applying Legendre's formula directly to a composite number. You CANNOT do ⌊100/12⌋+⌊100/144⌋\lfloor 100/12 \rfloor + \lfloor 100/144 \rfloor. It mathematically breaks because multiples of 4 and 3 combine to form 12s outside of just multiples of 12! Always break composite targets into primes.

  • Shortcut: When doing successive division for Legendre's (e.g., finding 5s in 100!), just divide the quotient by 5 iteratively: 100/5=20100/5 = 20. Then 20/5=420/5 = 4. Then sum them: 20+4=2420+4 = 24. No need to manually calculate 125125, 625625, etc.

Formulas

Legendre's Formula

∑k=1∞⌊npk⌋\sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor

Finds the exponent of prime p in the prime factorization of n!.
Trailing Zeros

∑⌊n5k⌋\sum \left\lfloor \frac{n}{5^k} \right\rfloor

Shortcut for trailing zeros, as 5 is always the limiting factor for 10s in factorials.
Consecutive Products

∏i=1k(n+i)≡0(modk!)\prod_{i=1}^{k} (n+i) \equiv 0 \pmod{k!}

k consecutive integers are divisible by k!.

Traps and tips

  • NEVER apply Legendre's formula directly to composite numbers. Break them down into prime components first.
  • For trailing zeros, just continuously divide the quotient by 5 and sum the integers.
  • If asked for trailing zeros in 100! * 200!, ADD the number of zeros. (Exponent rules: x^A * x^B = x^{A+B}).

Solved examples

The Classic Trailing Zeros

Find the number of trailing zeros in 250!250!.

Show solution

Trailing zeros are determined by the number of 10s, which is limited by the number of 5s in the prime factorization.

We apply Legendre's formula for p=5p=5 and n=250n=250.

Using the continuous quotient shortcut:

250÷5=50250 \div 5 = 50

50÷5=1050 \div 5 = 10

10÷5=210 \div 5 = 2

2÷5=02 \div 5 = 0 (Stop here).

Now sum the quotients: 50+10+2=6250 + 10 + 2 = 62.

There are 62 fives in 250!250!, which combine with the abundant twos to make 62 tens.

So, there are 62 trailing zeros.

Takeaway: Continuously divide by 5 and sum the integer quotients to find trailing zeros in any factorial instantly.

The Composite Bottleneck

What is the highest power of 12 that exactly divides 100!100!?

Show solution

12 is a composite number. Do NOT apply Legendre's to 12 directly.

Factorize 12: 12=22×3112 = 2^2 \times 3^1.

We need to find the highest powers of 2 and 3 in 100!100!.

Power of 3 in 100!100!:

100÷3=33100 \div 3 = 33

33÷3=1133 \div 3 = 11

11÷3=311 \div 3 = 3

3÷3=13 \div 3 = 1

Sum = 33+11+3+1=4833 + 11 + 3 + 1 = 48.

So, 100!100! has 3483^{48}.

Power of 2 in 100!100!:

100÷2=50100 \div 2 = 50

50÷2=2550 \div 2 = 25

25÷2=1225 \div 2 = 12

12÷2=612 \div 2 = 6

6÷2=36 \div 2 = 3

3÷2=13 \div 2 = 1

Sum = 50+25+12+6+3+1=9750 + 25 + 12 + 6 + 3 + 1 = 97.

So, 100!100! has 2972^{97}.

We need to form 12s (22×32^2 \times 3).

How many (22)(2^2) blocks can we make from 2972^{97}?

⌊97/2⌋=48\lfloor 97 / 2 \rfloor = 48 blocks of 44.

So we have 48 blocks of 222^2, and 48 blocks of 313^1.

We can perfectly pair them to form 48 twelves.

The highest power of 12 is 48.

Takeaway: For composite divisors like p^a q^b, find powers of p and q, divide them by a and b respectively, and take the minimum (the bottleneck).

Zeros in Non-Standard Products

Find the number of trailing zeros in the product: 5×10×15×⋯×1005 \times 10 \times 15 \times \dots \times 100.

Show solution

This is NOT 100!100!. It is a product of the first 20 multiples of 5.

Let's rewrite the series by factoring out a 5 from EACH of the 20 terms.

5×10×15⋯×1005 \times 10 \times 15 \dots \times 100

=(5×1)×(5×2)×(5×3)⋯×(5×20)= (5 \times 1) \times (5 \times 2) \times (5 \times 3) \dots \times (5 \times 20)

=520×(1×2×3⋯×20)= 5^{20} \times (1 \times 2 \times 3 \dots \times 20)

=520×20!= 5^{20} \times 20!

To find trailing zeros, we need to find the number of 5s and 2s in this expression and find the bottleneck.

Normally, 5 is the bottleneck. But here, we artificially injected twenty 5s! So 2 might be the bottleneck.

Number of 5s:

We have twenty 5s outside (5205^{20}).

Number of 5s in 20!=(20/5)=420! = (20/5) = 4.

Total 5s = 20+4=2420 + 4 = 24.

Number of 2s:

We only get 2s from 20!20!.

20/2=1020/2 = 10

10/2=510/2 = 5

5/2=25/2 = 2

2/2=12/2 = 1

Total 2s = 10+5+2+1=1810 + 5 + 2 + 1 = 18.

Since 18 is less than 24, the 2s are the bottleneck!

We can only form 18 tens.

The number of trailing zeros is 18.

Takeaway: In custom sequences stripped of regular integers, verify whether 2 or 5 is the limiting factor. Do not blindly assume 5.

Factorial Exponents Trick

What is the highest power of 6 that divides 10!×20!10! \times 20!?

Show solution

Since 6 = 2×32 \times 3, and in any factorial sequence 2s are more abundant than 3s, the power of 3 will be the bottleneck. We only need to find the power of 3.

Power of 3 in 10!10!:

10/3=310/3 = 3

3/3=13/3 = 1

Sum = 44. So 10!10! has 343^4.

Power of 3 in 20!20!:

20/3=620/3 = 6

6/3=26/3 = 2

Sum = 88. So 20!20! has 383^8.

When we multiply 10!10! and 20!20!, we add the exponents:

34×38=3123^4 \times 3^8 = 3^{12}.

The power of 3 is 12.

(The power of 2 will definitely be much higher, so 3 is the limit).

The highest power of 6 is 12.

Takeaway: When multiplying factorials, find the prime exponents for each factorial separately and then add them.

Consecutive Chunk Divisibility

If N=34×35×36×⋯×42N = 34 \times 35 \times 36 \times \dots \times 42, find the highest value of kk such that k!k! perfectly divides NN.

Show solution

Count the number of terms in the sequence.

From 34 to 42 inclusive, there are (42−34)+1=9(42 - 34) + 1 = 9 consecutive integers.

There is a fundamental theorem: The product of any kk consecutive integers is always divisible by k!k!.

Since there are 9 consecutive integers, their product is guaranteed to be divisible by 9!9!.

So k=9k=9 works.

Could it be divisible by 10!10!? Not guaranteed, and often false. (In this specific case, N=42!/33!N = 42! / 33!. We could check if it divides 10!10!, but the fundamental rule provides the most mathematically guaranteed bound for ANY such sequence).

For CAT purposes, when asked this generically based on sequence length, kk is the length of the sequence.

The answer is 9.

Takeaway: The product of 'k' consecutive integers is always perfectly divisible by k!. This is a lightning fast shortcut for division problems.

The Zero Difference

Find the number of trailing zeros in 100!−99!100! - 99!.

Show solution

A classic algebraic manipulation trap. Do NOT subtract the trailing zeros of 99! from 100!.

Instead, factorize the expression.

100!=100×99!100! = 100 \times 99!

So, 100!−99!=(100×99!)−(1×99!)100! - 99! = (100 \times 99!) - (1 \times 99!)

=99!(100−1)= 99!(100 - 1)

=99!×99= 99! \times 99.

The number of trailing zeros is determined entirely by the number of 5s and 2s.

The term '99' has no 5s or 2s, so it contributes exactly zero trailing zeros to the product.

Thus, the number of trailing zeros in (99!×99)(99! \times 99) is exactly the same as the number of trailing zeros in 99!99!.

Find zeros in 99!99!:

99/5=1999/5 = 19

19/5=319/5 = 3

19+3=2219 + 3 = 22.

There are 22 trailing zeros.

Takeaway: When adding or subtracting factorials, factor out the smaller factorial first. N! - (N-1)! = (N-1)!(N - 1).

Practice questions

Question 1 · CAT Level

For how many integers k∈{1,2,3,…,50}k \in \{1, 2, 3, \dots, 50\} is it impossible for any factorial n!n! to terminate in exactly kk trailing zeros?

  1. A

    7

  2. B

    8

  3. C

    9

  4. D

    10

Show answer and explanation

Answer: (C) 9

The number of trailing zeros in n!n! is given by Z(n)=∑j=1∞⌊n/5j⌋Z(n) = \sum_{j=1}^\infty \lfloor n/5^j \rfloor.

As nn increases by 11, Z(n)Z(n) increases by the exponent of 55 in nn.

Whenever nn is a multiple of 52=255^2 = 25, Z(n)Z(n) jumps by at least 22, skipping at least one integer value:

n=25n=25: jumps from 44 to 66 (skips 55); n=50n=50: from 1010 to 1212 (skips 1111);

n=75n=75: from 1616 to 1818 (skips 1717); n=100n=100: from 2222 to 2424 (skips 2323);

n=125=53n=125 = 5^3: jumps from 2828 to 3131 (skips both 2929 and 3030);

n=150n=150: from 3535 to 3737 (skips 3636); n=175n=175: from 4141 to 4343 (skips 4242); n=200n=200: from 4747 to 4949 (skips 4848).

At n=225n=225, the jump skips 54>5054 > 50, giving the 99 skipped values: {5,11,17,23,29,30,36,42,48}\{5, 11, 17, 23, 29, 30, 36, 42, 48\}.

Question 2 · CAT Level

What is the maximum positive integer kk such that 72k72^k completely divides 100!100!?

  1. A

    24

  2. B

    32

  3. C

    48

  4. D

    97

Show answer and explanation

Answer: (A) 24

Prime factorise 72=23×3272 = 2^3 \times 3^2.

We use Legendre’s formula to find the exponents of 22 and 33 in 100!100!:

E2(100!)=⌊100/2⌋+⌊100/4⌋+⌊100/8⌋+⌊100/16⌋+⌊100/32⌋+⌊100/64⌋=50+25+12+6+3+1=97E_2(100!) = \lfloor 100/2 \rfloor + \lfloor 100/4 \rfloor + \lfloor 100/8 \rfloor + \lfloor 100/16 \rfloor + \lfloor 100/32 \rfloor + \lfloor 100/64 \rfloor = 50 + 25 + 12 + 6 + 3 + 1 = 97.

The number of 232^3 factors available is ⌊97/3⌋=32\lfloor 97 / 3 \rfloor = 32.

E3(100!)=⌊100/3⌋+⌊100/9⌋+⌊100/27⌋+⌊100/81⌋=33+11+3+1=48E_3(100!) = \lfloor 100/3 \rfloor + \lfloor 100/9 \rfloor + \lfloor 100/27 \rfloor + \lfloor 100/81 \rfloor = 33 + 11 + 3 + 1 = 48.

The number of 323^2 factors available is ⌊48/2⌋=24\lfloor 48 / 2 \rfloor = 24.

The maximum value of kk is limited by the bottleneck: k=min⁡(32,24)=24k = \min(32, 24) = 24.

Question 3 · CAT Level

How many trailing zeros are in the decimal representation of the product

P=1!×2!×3!×⋯×30! ?P = 1! \times 2! \times 3! \times \dots \times 30! \text{ ?}

  1. A

    77

  2. B

    82

  3. C

    87

  4. D

    92

Show answer and explanation

Answer: (C) 87

The number of trailing zeros in PP is determined by the exponent of 55 in PP, which is ∑n=130E5(n!)\sum_{n=1}^{30} E_5(n!).

We group the factorials according to their number of factors of 55:

For n∈[1,4]n \in [1, 4], E5(n!)=0E_5(n!) = 0 (44 terms contribute 00).

For n∈[5,9]n \in [5, 9], E5(n!)=1E_5(n!) = 1 (55 terms contribute 5×1=55 \times 1 = 5), and for n∈[10,14]n \in [10, 14], E5(n!)=2E_5(n!) = 2 (5×2=105 \times 2 = 10).

For n∈[15,19]n \in [15, 19], E5(n!)=3E_5(n!) = 3 (5×3=155 \times 3 = 15), and for n∈[20,24]n \in [20, 24], E5(n!)=4E_5(n!) = 4 (5×4=205 \times 4 = 20).

For n∈[25,29]n \in [25, 29], E5(n!)=5+1=6E_5(n!) = 5 + 1 = 6 (55 terms contribute 5×6=305 \times 6 = 30).

For n=30n = 30, E5(30!)=6+1=7E_5(30!) = 6 + 1 = 7 (11 term contributes 77).

Total trailing zeros =0+5+10+15+20+30+7=87= 0 + 5 + 10 + 15 + 20 + 30 + 7 = 87.

Question 4 · CAT Level

What is the exponent of the highest power of 33 that divides the combination (10050)\binom{100}{50}?

  1. A

    2

  2. B

    3

  3. C

    4

  4. D

    5

Show answer and explanation

Answer: (C) 4

We express the combination as (10050)=100!(50!)2\binom{100}{50} = \frac{100!}{(50!)^2}.

The exponent of 33 in (10050)\binom{100}{50} is given by E3((10050))=E3(100!)−2E3(50!)E_3\left(\binom{100}{50}\right) = E_3(100!) - 2 E_3(50!).

Using Legendre’s formula for 100!100!:

E3(100!)=⌊100/3⌋+⌊100/9⌋+⌊100/27⌋+⌊100/81⌋=33+11+3+1=48E_3(100!) = \lfloor 100/3 \rfloor + \lfloor 100/9 \rfloor + \lfloor 100/27 \rfloor + \lfloor 100/81 \rfloor = 33 + 11 + 3 + 1 = 48.

Using Legendre’s formula for 50!50!:

E3(50!)=⌊50/3⌋+⌊50/9⌋+⌊50/27⌋=16+5+1=22E_3(50!) = \lfloor 50/3 \rfloor + \lfloor 50/9 \rfloor + \lfloor 50/27 \rfloor = 16 + 5 + 1 = 22.

Substituting these values gives E3((10050))=48−2(22)=48−44=4E_3\left(\binom{100}{50}\right) = 48 - 2(22) = 48 - 44 = 4.

Question 5 · CAT Level

Find the sum of all positive integers nn such that n!n! terminates in exactly 2424 trailing zeros.

  1. A

    500

  2. B

    510

  3. C

    515

  4. D

    525

Show answer and explanation

Answer: (B) 510

The number of trailing zeros is Z(n)=⌊n/5⌋+⌊n/25⌋+⌊n/125⌋+…Z(n) = \lfloor n/5 \rfloor + \lfloor n/25 \rfloor + \lfloor n/125 \rfloor + \dots.

We test values near 100100:

For n=99n = 99: Z(99)=⌊99/5⌋+⌊99/25⌋=19+3=22Z(99) = \lfloor 99/5 \rfloor + \lfloor 99/25 \rfloor = 19 + 3 = 22.

For n=100n = 100: Z(100)=⌊100/5⌋+⌊100/25⌋=20+4=24Z(100) = \lfloor 100/5 \rfloor + \lfloor 100/25 \rfloor = 20 + 4 = 24.

Since no multiple of 55 occurs between 100100 and 104104, Z(n)=24Z(n) = 24 for all n∈{100,101,102,103,104}n \in \{100, 101, 102, 103, 104\}.

For n=105n = 105: Z(105)=⌊105/5⌋+⌊105/25⌋=21+4=25Z(105) = \lfloor 105/5 \rfloor + \lfloor 105/25 \rfloor = 21 + 4 = 25.

Thus, exactly 55 positive integers satisfy the condition: n∈{100,101,102,103,104}n \in \{100, 101, 102, 103, 104\}, with sum 100+101+102+103+104=510100 + 101 + 102 + 103 + 104 = 510.

Study this concept with interactive practice in PrepSoc.

Open the concept library