Lemma › Guides › Legendre's formula for the power of a prime in n!
Guide

Legendre's formula for the power of a prime in n!

Problems about factorials rarely ask you to compute one. They ask how many zeros 100!100! ends in, or whether (2n)!(2n)! divided by something is an integer, or what the largest kk is with 12k12^k dividing 50!50!. Every one of those is a question about how often a prime divides n!n!, and Legendre's formula answers it in one line.

The formula

Write vp(x)v_p(x) for the exponent of the prime pp in xx. So v3(54)=3v_3(54) = 3, because 54=2⋅3354 = 2 \cdot 3^3. Legendre's formula says

vp(n!)=⌊np⌋+⌊np2⌋+⌊np3⌋+⋯v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots

The sum stops by itself. Once pk>np^k > n every term is 00.

There is a second form that you should keep next to it. If sp(n)s_p(n) is the sum of the digits of nn written in base pp, then

vp(n!)=n−sp(n)p−1.v_p(n!) = \frac{n - s_p(n)}{p - 1}.

For p=2p = 2 this reads v2(n!)=n−s2(n)v_2(n!) = n - s_2(n), the number nn minus the number of ones in its binary form. Use the sum of floors when you want to compute. Use the digit form when you want to bound, because it shows at once that v2(n!)<nv_2(n!) < n for every n≥1n \ge 1.

Why it is true

Count the factors of pp in 1⋅2⋯n1 \cdot 2 \cdots n one layer at a time. Every multiple of pp gives at least one factor, and there are ⌊n/p⌋\lfloor n/p \rfloor of those. Every multiple of p2p^2 gives a second factor that the first count missed, and there are ⌊n/p2⌋\lfloor n/p^2 \rfloor of those. Every multiple of p3p^3 gives a third. A number like p3⋅5p^3 \cdot 5 is counted in all three layers, which is right, since it holds three factors of pp.

That is the whole proof. It is a count in layers, and you can rebuild it at the exam desk in under a minute.

Trailing zeros of 100!

A number ends in as many zeros as it has factors of 10=2⋅510 = 2 \cdot 5, and 100!100! has far more twos than fives, so only the fives matter. Then

v5(100!)=20+4=24.v_5(100!) = 20 + 4 = 24.

So 100!100! ends in exactly 2424 zeros. The twos are there in plenty: v2(100!)=50+25+12+6+3+1=97v_2(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97. You can ignore that number, and you should be able to say why.

A harder example: the largest k

What is the largest kk such that 12k12^k divides 50!50!?

Split 12=22⋅312 = 2^2 \cdot 3. Then 12k=22k⋅3k12^k = 2^{2k} \cdot 3^k, and you need both parts. First the exponents in 50!50!:

v2(50!)=25+12+6+3+1=47,v3(50!)=16+5+1=22.v_2(50!) = 25 + 12 + 6 + 3 + 1 = 47, \qquad v_3(50!) = 16 + 5 + 1 = 22.

The twos allow 2k≤472k \le 47, so k≤23k \le 23. The threes allow k≤22k \le 22. The smaller bound wins, and the answer is k=22k = 22. The three is the bottleneck, even though 1212 is mostly made of twos. The 4747 twos would cover 2323 copies, but there are only 2222 threes.

The habit that saves marks: factor the target into prime powers, compute each prime's exponent, then divide the exponent in n!n! by the exponent in the target and round down. Take the minimum over the primes.

The reverse question

Sometimes you are given the power and asked for nn. What is the smallest nn such that 2102^{10} divides n!n!?

Walk upward. The exponent v2(n!)v_2(n!) only increases when nn passes an even number, so test even nn. At n=10n = 10 you get 5+2+1=85 + 2 + 1 = 8. At n=12n = 12 you get 6+3+1=106 + 3 + 1 = 10. So n=12n = 12.

When the exponent is large, do not walk. Use the digit form: vp(n!)≥ev_p(n!) \ge e means n−sp(n)≥e(p−1)n - s_p(n) \ge e(p - 1). The digit sum sp(n)s_p(n) is small next to nn, so start at n=e(p−1)n = e(p-1) and move up a few steps. For p=2p = 2 and e=10e = 10, start at n=10n = 10: that gives 10−2=810 - 2 = 8, too small. At n=12n = 12 (binary 11001100) you get 12−2=1012 - 2 = 10.

When to reach for it

The signals are these.

Where it goes wrong

Two slips cover most lost marks.

Legendre's formula is for primes only. For 1212 or 100100 you factor first, as above. Another trap hides in the problem statement. A question about (2n)!(2n)! changes nn before you start, and one about (n!)2(n!)^2 doubles the exponent. Write down exactly which factorial you are taking a valuation of.

Where it connects

Valuations are one prime at a time, and that is the habit this formula trains. The proof that the harmonic sum is never an integer for n≥2n \ge 2 lives on the same idea: find the one term with the biggest power of 22 and watch it refuse to cancel. Both belong to modular thinking, where you look at one prime at a time instead of the whole number.

Take five problems that mention a factorial and, before you do anything else, write down vpv_p of it for the primes in play. Often that line is most of the solution. The problem archive has plenty to practise on, and the daily problem gives you a new one each day.

Related guides

Techniques in this guide

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level