5. Highest Power of a Prime p Dividing n!
Free study material · concepts, shortcuts & solved questions
Formula (General Legendre’s Formula): E_p(n!) = ⌊ (n)/(p) ⌋ + ⌊ (n)/(p^2) ⌋ + ⌊ (n)/(p^3) ⌋ + …
This is the exact same method as trailing zeros, generalized to any prime p (trailing zeros is just the special case p=5).
Example 1: Find the highest power of 3 that divides 100!. ⌊100/3⌋=33, ⌊100/9⌋=11, ⌊100/27⌋=3, ⌊100/81⌋=1, ⌊100/243⌋=0. Total = 33+11+3+1=48. So 3^(48) is the highest power of 3 dividing 100!.
Example 2: Find the highest power of 2 that divides 30!. ⌊30/2⌋=15, ⌊30/4⌋=7, ⌊30/8⌋=3, ⌊30/16⌋=1, ⌊30/32⌋=0. Total = 15+7+3+1=26. So 2^(26) divides 30! exactly.
Example 3: Find the highest power of 7 dividing 50!. ⌊50/7⌋=7, ⌊50/49⌋=1, ⌊50/343⌋=0. Total = 7+1=8. So 7^8 is the highest power of 7 dividing 50!.
Note for composite divisors: If asked for the highest power of a composite number (e.g., 12 or 6) dividing n!, break the composite into prime factors, compute each prime’s power, then use the limiting factor. E.g., highest power of 12=22×31 dividing n!: compute E_2(n!) and E_3(n!); the answer is ⌊ (E_2(n!))/(2) ⌋ compared with E_3(n!), and you take the smaller (limiting) value.
Example 4 (highest power of a composite number in a factorial): Find the highest power of 12 that divides 50!. 12 = 2^2 × 3. First find E_2(50!): ⌊50/2⌋=25, ⌊50/4⌋=12, ⌊50/8⌋=6, ⌊50/16⌋=3, ⌊50/32⌋=1. Total =25+12+6+3+1=47. Next find E_3(50!): ⌊50/3⌋=16, ⌊50/9⌋=5, ⌊50/27⌋=1, ⌊50/81⌋=0. Total =16+5+1=22. Each copy of 12=2^2×3 consumes two 2’s and one 3, so the number of complete “12”s available from the 2’s alone is ⌊ 47/2 ⌋ = 23, while only 22 threes are available. The limiting factor is the threes (22 < 23). Highest power of 12 dividing 50! = 12^(22).
Example 5 (highest power of a composite prime-squared-free number): Find the highest power of 6 that divides 100!. 6=2×3. From Example 1 (Section 5), E_3(100!)=48. Now find E_2(100!): ⌊100/2⌋=50, ⌊100/4⌋=25, ⌊100/8⌋=12, ⌊100/16⌋=6, ⌊100/32⌋=3, ⌊100/64⌋=1. Total =50+25+12+6+3+1=97. Since each “6” needs exactly one 2 and one 3, the limiting factor is whichever prime’s total count is smaller: (97,48)=48. Highest power of 6 dividing 100! = 6^(48).