Procedure
Highest power of a prime in
Algebra • Permutations and Combinations
Statement
For a prime , the highest power of that divides is with , where is the greatest integer. The sum stops when .
How to use it
- 1Why it works: counts the multiples of up to , each giving one factor . Multiples of hold a second factor, counted by , and so on.
- 2For a power of a prime, such as : find for the prime , then the highest power of is .
Worked example
What is the highest power of that divides ?
Step-by-step
- 1
Why: Multiples of :
. - 2
Why: and each hold a second .
- 3, so
Answer
Watch out
Stopping after misses the extra factors in multiples of . For a power such as , rounding up instead of down is the other slip.
Builds on
Also known as
Legendre's formula, exponent of prime in n factorial, highest power of 2 dividing n!