Skip to content
Omnikalc

Legendre’s formula calculator

Enter n, a prime p and k to get the exponent of p in n!, in k!, in (n − k)! and in the binomial coefficient C(n, k), the number of carries when adding k and n − k in base p, and the trailing zeros of n!.

Updated on
Your inputs

Value out of range

Value out of range

Value out of range

Results

Exponent of p in n!

24

Exponent of p in C(n, k), also the carries when adding k and n − k in base p

1

Trailing zeros of n! in base 10

24

Exponent of p in k!
9
Exponent of p in (n − k)!
14
Digit sum bound: (n − exponent × (p − 1)) is the digit sum of n in base p
4

The Legendre’s formula calculator gives the exponent of a prime p in n! and in a binomial coefficient C(n, k), the number of carries in base p by Kummer’s theorem, the digit sum of n in base p and the trailing zeros of n! in base 10.

How the calculation works

  • Enter n and the prime p.
  • Enter k for the binomial coefficient C(n, k), with k at most n.
  • Read the exponents, the carries and the trailing zeros.

Example

For n = 100 and the prime p = 5, the exponent of p in n! is 24. In k! with k = 40 it is 9, in (n − k)! it is 14, so in C(n, k) it is 1. The digit sum of n in base p is 4. The factorial of n ends with 24 zeros in base 10.

Why it matters

The calculator helps students of number theory, competition mathematicians and programmers who work with factorials and binomial coefficients, and who need the power of a prime in them, the divisibility of a binomial coefficient or the trailing zeros of a factorial.

Good to know

The formula requires p to be prime: the calculator does not check this, and a composite value gives a number that has no standard meaning. For the trailing zeros it uses the exponents of 2 and 5. For k larger than n, the binomial coefficient is not defined and the result has no meaning. The exponent of p in C(n, k) is also the number of carries when adding k and n − k in base p, which gives a quick way to see if a binomial coefficient is divisible by p.

The factorial calculator gives the factorial and trailing zeros, the binomial calculator gives coefficients, the combinations calculator counts subsets and the prime number theorem calculator estimates how many primes there are.

Frequently asked questions

What is Legendre’s formula?

Legendre’s formula gives the exponent of a prime p in the prime factorization of n!: it is v_p(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …, a sum that stops when p^k exceeds n. For n = 100 and p = 5, it is 20 + 4 = 24, so 5²⁴ divides 100! and 5²⁵ does not.

How does it give the trailing zeros?

The trailing zeros of n! in base 10 are the number of factors of 10, each made of a 2 and a 5. There are always more factors 2 than 5, so the number of zeros is the exponent of 5 given by Legendre’s formula. For 100! it is 24. The calculator takes the minimum of the exponents of 2 and 5.

How is the binomial coefficient treated?

The exponent of p in C(n, k) = n! / (k! × (n − k)!) is v_p(n!) − v_p(k!) − v_p((n − k)!). By Kummer’s theorem, it is also the number of carries when adding k and n − k in base p. If the exponent is zero, p does not divide the binomial coefficient.

What is the digit sum identity?

Legendre’s exponent can be written as (n − s_p(n)) / (p − 1), where s_p(n) is the sum of the digits of n in base p. The calculator uses it to give the digit sum of n in base p. For n = 100 and p = 5, the digits are 4, 0, 0 and the sum is 4, so (100 − 4) / 4 = 24.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.