4. Trailing Zeros in n! (Legendre’s Formula)
Free study material · concepts, shortcuts & solved questions
Figure: Applying Legendre’s Formula step by step to find trailing zeros in 100!.
Concept: A trailing zero is produced by a factor of 10 = 2×5 in the product n! = 1×2×3×…× n. Since factors of 2 always vastly outnumber factors of 5 among 1,2,…,n, the number of trailing zeros equals the number of times 5 divides into n! — i.e., count the powers of 5.
Formula (Legendre’s Formula for prime p=5): Number of trailing zeros in n! = ⌊ (n)/(5) ⌋ + ⌊ (n)/(25) ⌋ + ⌊ (n)/(125) ⌋ + … (keep dividing by increasing powers of 5 until the quotient is 0, taking the floor/integer part each time, and summing).
Example 1: Number of trailing zeros in 100!. ⌊100/5⌋=20, ⌊100/25⌋=4, ⌊100/125⌋=0. Total = 20+4=24 zeros.
Example 2: Number of trailing zeros in 50!. ⌊50/5⌋=10, ⌊50/25⌋=2, ⌊50/125⌋=0. Total = 10+2=12 zeros.
Example 3: Number of trailing zeros in 125!. ⌊125/5⌋=25, ⌊125/25⌋=5, ⌊125/125⌋=1, ⌊125/625⌋=0. Total = 25+5+1=31 zeros.
Reverse-type question: Find the smallest value of n such that n! ends with exactly 24 zeros. From Example 1, 100! has 24 zeros. Check 96! to 99!: these all have ⌊ n/5⌋+⌊ n/25⌋. For n=96,97,98,99: ⌊ n/5⌋=19, ⌊ n/25⌋=3, total =22 — not yet 24. So the count jumps from 22 (at n=99) directly to 24 at n=100 (since 100 contributes an extra factor of 5 AND is itself divisible by 25, contributing 2 extra fives at once: 100=4×25). Therefore no factorial ends in exactly 23 zeros, and the smallest n with 24 trailing zeros is n=100 (and n=101,102,103,104 also give 24 zeros, since 101–104 contribute no new factors of 5).
Example 4 (larger factorial): Find the number of trailing zeros in 250!. ⌊250/5⌋=50, ⌊250/25⌋=10, ⌊250/125⌋=2, ⌊250/625⌋=0. Total =50+10+2=62 zeros.
Example 5 (a value not ending in a “round” multiple of 25): Find the number of trailing zeros in 205!. ⌊205/5⌋=41, ⌊205/25⌋=8, ⌊205/125⌋=1, ⌊205/625⌋=0. Total =41+8+1=50 zeros. Notice that even though 205 is not a multiple of 25 or 125, each floor term is computed independently and simply summed — there is no need for 205 itself to be “special” for the formula to apply.