Legendre’s Formula (powers of p in n!) Explained with Worked Examples

The exponent of a prime in is

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Legendre’s formula (powers of p in n!) means

Among the numbers , exactly are multiples of and each contributes at least one factor ; then of them contribute a second factor, and so on. Adding these counts gives the formula. The floor function is described in Hermite's identity, and factorials are part of binomial coefficients.

The most common use is counting trailing zeros: the number of zeros at the end of is , since there are always more factors of 2 than 5. The formula also tells you the largest power of a prime dividing a binomial coefficient, and helps with prime factor form, the number of divisors and the sum of divisors of .

The sum stops as soon as . A related result describes where primes occur among the integers, see the prime number theorem, and the divisibility tests in the rule for 11 use similar remainder thinking.

What is it used for?

Legendre's formula counts how many times a prime divides a factorial. The most familiar use is counting the zeros at the end of n!.

How to use legendre’s formula (powers of p in n!)

  1. Choose the prime and the number .
  2. Compute , , until the quotient is 0.
  3. Add these numbers.
  4. The total is the exponent of in .

Graph

The exponent of 2 in 10! is 5 + 2 + 1 = 8⌊10/2⌋ = 5⌊10/4⌋ = 2⌊10/8⌋ = 100.511.522.533.540123456The exponent of 2 in 10! is 5 + 2 + 1 = 8xyGraph with x from 0 to 4 and y from 0 to 6. Shows bars (3); point ⌊10/2⌋ = 5 at (1, 5); point ⌊10/4⌋ = 2 at (2, 2); point ⌊10/8⌋ = 1 at (3, 1).

The three bars add to 8, the number of factors 2 in 10! = 3628800 = 2⁸ × 14175.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: power of 2 in 10!

Find the exponent of 2 in .

Worked example
Answer
88
  1. Quotients
  2. Add

Example 2: trailing zeros of 100!

How many zeros are at the end of ?

Worked example
Answer
2424
  1. Factors of 5
  2. Add

Example 3: power of 7 in 50!

Find the exponent of 7 in .

Worked example
Answer
88
  1. Quotients
  2. Add

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

v₂(10!)

⌊10/2⌋ + ⌊10/4⌋ + ⌊10/8⌋

5 + 2 + 1 = 8.

v₅(100!)

20 + 4

24.

v₃(20!)

6 + 2

8.

Trailing zeros of 50!

10 + 2

12.

Word problems

v_p(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …. Trailing zeros of n! equal v₅(n!).

2 in 10!

⌊10/2⌋ + ⌊10/4⌋ + ⌊10/8⌋.

  1. 5 + 2 + 1
  2. Check: ✓8

5 in 100!

⌊100/5⌋ + ⌊100/25⌋.

  1. 20 + 4
  2. Check: ✓24

3 in 20! Higher

⌊20/3⌋ + ⌊20/9⌋.

  1. 6 + 2
  2. Check: ✓8

Trailing zeros Higher

50!: ⌊50/5⌋ + ⌊50/25⌋.

  1. 10 + 2
  2. Check: ✓12

Common mistakes

Only ⌊n/p⌋

first term ✗

add higher powers ✓

p², p³.

Counting 2s for zeros

wrong prime ✗

count 5s ✓

Fewer 5s.

Rounding up

ceiling ✗

floor ✓

Integer part.

Using for composite p

formula ✗

prime p only ✓

Prime.

Exam tips

  1. Add ⌊n/pᵏ⌋.
  2. Stop when pᵏ > n.
  3. Zeros: count 5s.
  4. Prime p.
  5. Floor each term.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. v₂(8!) Foundation

7

2. v₃(10!) Foundation

4

3. v₅(25!) Foundation

6

4. Trailing zeros of 30! Higher

7

5. v₇(50!) Higher

8

6. Trailing zeros of 200! Higher

49

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Legendre’s formula
v_p(n!).
p-adic valuation
Exponent of p.
Trailing zeros
Factors of 10.
Floor
⌊x⌋.
Factorial
n!.
Prime power
pᵏ.

Frequently asked questions

What is Legendre’s formula?

v_p(n!) = Σ⌊n/pᵏ⌋.

How many trailing zeros has 100!?

24.

Why count 5s?

There are always more 2s than 5s.

When do I stop?

When pᵏ > n.

Which page covers circle theorems?

angle at the centre.

Which page covers divisibility by 11?

divisibility rule for 11.

More in Discrete maths and number theory and the formula sheets.