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 () 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 ?
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 threes.
-
But wait! Numbers like 9, 18, 27 have another 3 hidden inside them because they are multiples of . So every 9th number drops a second '3' into the bucket. That's threes.
-
Numbers like 27, 54, 81 have a third 3! Every 27th number drops a third '3'. That's threes.
-
And 81 drops a fourth 3. That's three.
Count the bucket: .
There are exactly 48 threes hiding in . 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 " (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 " (12 is a composite number . 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 that perfectly divides is:
(Stop when ).
B. Highest Power of a Composite Number
If is a composite number, say :
-
Use Legendre's formula to find the highest powers of and in . Let them be and .
-
The number of times can be formed is limited by the bottleneck: .
Example: Highest power of () in . 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 , which is . In any factorial, there are always way more s than s. The s are the bottleneck.
Therefore, the number of trailing zeros in is exactly equal to the highest power of in .
D. Product of Consecutive Integers
The product of any consecutive integers is ALWAYS perfectly divisible by .
Example: (4 integers) is perfectly divisible by (24).
4. Common Pitfalls & Speed Shortcuts
-
Pitfall: Applying Legendre's formula directly to a composite number. You CANNOT do . 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: . Then . Then sum them: . No need to manually calculate , , etc.
Formulas
| Legendre's Formula | |
|---|---|
| Trailing Zeros | |
| Consecutive Products |
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 .
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 and .
Using the continuous quotient shortcut:
(Stop here).
Now sum the quotients: .
There are 62 fives in , 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 ?
Show solution
12 is a composite number. Do NOT apply Legendre's to 12 directly.
Factorize 12: .
We need to find the highest powers of 2 and 3 in .
Power of 3 in :
Sum = .
So, has .
Power of 2 in :
Sum = .
So, has .
We need to form 12s ().
How many blocks can we make from ?
blocks of .
So we have 48 blocks of , and 48 blocks of .
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: .
Show solution
This is NOT . 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.
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 ().
Number of 5s in .
Total 5s = .
Number of 2s:
We only get 2s from .
Total 2s = .
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 ?
Show solution
Since 6 = , 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 :
Sum = . So has .
Power of 3 in :
Sum = . So has .
When we multiply and , we add the exponents:
.
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 , find the highest value of such that perfectly divides .
Show solution
Count the number of terms in the sequence.
From 34 to 42 inclusive, there are consecutive integers.
There is a fundamental theorem: The product of any consecutive integers is always divisible by .
Since there are 9 consecutive integers, their product is guaranteed to be divisible by .
So works.
Could it be divisible by ? Not guaranteed, and often false. (In this specific case, . We could check if it divides , 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, 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 .
Show solution
A classic algebraic manipulation trap. Do NOT subtract the trailing zeros of 99! from 100!.
Instead, factorize the expression.
So,
.
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 is exactly the same as the number of trailing zeros in .
Find zeros in :
.
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 is it impossible for any factorial to terminate in exactly trailing zeros?
Show answer and explanation
Answer: (C) 9
The number of trailing zeros in is given by .
As increases by , increases by the exponent of in .
Whenever is a multiple of , jumps by at least , skipping at least one integer value:
: jumps from to (skips ); : from to (skips );
: from to (skips ); : from to (skips );
: jumps from to (skips both and );
: from to (skips ); : from to (skips ); : from to (skips ).
At , the jump skips , giving the skipped values: .
Question 2 · CAT Level
What is the maximum positive integer such that completely divides ?
Show answer and explanation
Answer: (A) 24
Prime factorise .
We use Legendre’s formula to find the exponents of and in :
.
The number of factors available is .
.
The number of factors available is .
The maximum value of is limited by the bottleneck: .
Question 3 · CAT Level
How many trailing zeros are in the decimal representation of the product
Show answer and explanation
Answer: (C) 87
The number of trailing zeros in is determined by the exponent of in , which is .
We group the factorials according to their number of factors of :
For , ( terms contribute ).
For , ( terms contribute ), and for , ().
For , (), and for , ().
For , ( terms contribute ).
For , ( term contributes ).
Total trailing zeros .
Question 4 · CAT Level
What is the exponent of the highest power of that divides the combination ?
Show answer and explanation
Answer: (C) 4
We express the combination as .
The exponent of in is given by .
Using Legendre’s formula for :
.
Using Legendre’s formula for :
.
Substituting these values gives .
Question 5 · CAT Level
Find the sum of all positive integers such that terminates in exactly trailing zeros.
Show answer and explanation
Answer: (B) 510
The number of trailing zeros is .
We test values near :
For : .
For : .
Since no multiple of occurs between and , for all .
For : .
Thus, exactly positive integers satisfy the condition: , with sum .
Study this concept with interactive practice in PrepSoc.
Open the concept library