Problems about factorials rarely ask you to compute one. They ask how many zeros ends in, or whether divided by something is an integer, or what the largest is with dividing . Every one of those is a question about how often a prime divides , and Legendre's formula answers it in one line.
The formula
Write for the exponent of the prime in . So , because . Legendre's formula says
The sum stops by itself. Once every term is .
There is a second form that you should keep next to it. If is the sum of the digits of written in base , then
For this reads , the number 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 for every .
Why it is true
Count the factors of in one layer at a time. Every multiple of gives at least one factor, and there are of those. Every multiple of gives a second factor that the first count missed, and there are of those. Every multiple of gives a third. A number like is counted in all three layers, which is right, since it holds three factors of .
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 , and has far more twos than fives, so only the fives matter. Then
So ends in exactly zeros. The twos are there in plenty: . You can ignore that number, and you should be able to say why.
A harder example: the largest k
What is the largest such that divides ?
Split . Then , and you need both parts. First the exponents in :
The twos allow , so . The threes allow . The smaller bound wins, and the answer is . The three is the bottleneck, even though is mostly made of twos. The twos would cover copies, but there are only threes.
The reverse question
Sometimes you are given the power and asked for . What is the smallest such that divides ?
Walk upward. The exponent only increases when passes an even number, so test even . At you get . At you get . So .
When the exponent is large, do not walk. Use the digit form: means . The digit sum is small next to , so start at and move up a few steps. For and , start at : that gives , too small. At (binary ) you get .
When to reach for it
The signals are these.
- "Ends in zeros" or "is divisible by the largest power of". Any question that names the exponent of a prime in a factorial.
- A ratio of factorials that should be an integer. For example . Compare of the top and the bottom for each prime . Layer by layer, with and , you need , and that is settled by looking at the fractional parts of and alone.
- Binomial coefficients. is , so of it is a difference of three Legendre sums. For central binomials, turns out to be the number of ones in the binary form of .
- Divisibility of products of consecutive integers. The product of consecutive integers is divisible by , because it is . The problem about four consecutive integers and is the case .
Where it goes wrong
Two slips cover most lost marks.
- Dropping a layer. Writing as and forgetting the from . Stop only when exceeds , and say so.
- Rounding the wrong way at the end. Dividing by gives . The answer is , never .
Legendre's formula is for primes only. For or you factor first, as above. Another trap hides in the problem statement. A question about changes before you start, and one about 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 lives on the same idea: find the one term with the biggest power of 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 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
- EGMO 2020 Problem 1: solution, and the power of 2 that cannot hideA full solution to EGMO 2020 Problem 1: track the power of 2 in each term, show it climbs by 2 or falls by 1, and count the terms.
- Lifting the exponent lemma explained for competitionsThe lifting the exponent lemma in one line, the p = 2 version that catches almost everyone, and the signals that tell you a contest problem wants it.
- Chinese remainder theorem in olympiad problemsThe Chinese remainder theorem for coprime moduli, how to solve a system by hand, what changes when moduli share a factor, and where olympiads use it.
- Order modulo p in olympiad number theoryThe order of a modulo p divides p - 1 and every n with a^n = 1 mod p. How to use it to pin down prime factors, with a worked proof and the traps.
- Zsigmondy's theorem: statement, exceptions and examplesZsigmondy's theorem says a^n - b^n has a prime factor no earlier a^k - b^k has, with two exceptions. The statement, the traps, and a worked problem.
Techniques in this guide
- Modular ThinkingWhen the numbers are too big, shrink the universe.
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