Introduction
Many problems in number theory and combinatorics ask: What is the largest power of a prime that divides n!? This is useful for finding trailing zeros, divisibility properties, and simplifying factorial-based expressions.
The tool used to solve such problems is Legendre’s Formula, which counts how many times a prime divides the factorial n!.
Pattern: Highest Power of a Prime in n!
Pattern
Legendre’s Formula gives the exponent of a prime p in n! as:
vₚ(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …
The sum continues until pᵏ > n. The result gives the highest power of p that divides n!. That is, p^vₚ(n!) divides n!, but p^(vₚ(n!)+1) does not.
- Use Cases: Finding trailing zeros (use p = 5), checking divisibility, simplifying factorial ratios.
- Intuition: Every multiple of p contributes one p, multiples of p² add another, and so on.
Step-by-Step Example
Question
Find the highest power of 2 that divides 100!.
Solution
-
Step 1: Apply Legendre’s Formula:
v₂(100!) = ⌊100/2⌋ + ⌊100/4⌋ + ⌊100/8⌋ + ⌊100/16⌋ + ⌊100/32⌋ + ⌊100/64⌋ + …
-
Step 2: Compute each term:
⌊100/2⌋ = 50
⌊100/4⌋ = 25
⌊100/8⌋ = 12
⌊100/16⌋ = 6
⌊100/32⌋ = 3
⌊100/64⌋ = 1
⌊100/128⌋ = 0 (stop here) -
Step 3: Add them up:
v₂(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97
-
Final Answer:
The highest power of 2 that divides 100! is 2⁹⁷ (exponent e = 97).
-
Quick Check:
For trailing zeros, we compare powers of 2 and 5. v₅(100!) = ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24. Since 2s are more than 5s, number of trailing zeros = 24 ✅
Quick Variations
1. Highest power of 5 in n!: Used for trailing zeros → v₅(n!) = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …
2. Highest power of p in (n choose r): Use vₚ(C(n, r)) = vₚ(n!) - vₚ(r!) - vₚ((n-r)!).
3. Stop when pᵏ > n, as higher powers contribute nothing.
Trick to Always Use
- Step 1: Apply Legendre’s Formula - keep dividing n by p, p², p³, etc., and sum integer results.
- Step 2: For trailing zeros, always use p = 5 since 2s are more frequent than 5s.
- Step 3: For combination problems, use differences of factorial exponents.
- Step 4: Stop when division result becomes 0 - further terms contribute nothing.
Summary
Summary
- Use Legendre’s Formula to find the exponent of a prime p in n! using repeated division by p, p², p³, etc.
- Stop when the division result becomes 0, since further terms add nothing.
- The computed exponent vₚ(n!) gives the highest power of p that divides n! exactly.
- This method is essential for trailing zeros (use p = 5), factorial divisibility, and combination exponent problems.
Example to remember:
v₂(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97 → highest power = 2⁹⁷.
Hint: Sum ⌊n/2⌋ + ⌊n/4⌋ + ⌊n/8⌋ … until terms are 0.
Common Mistakes: Forgetting to include higher powers like 16 and 32 which still contribute.