Learn the idea. Try it yourself.

Read the explanation or try 6 questions with hints. Free, untimed and no sign-in needed.

Read the lessonStart practising →

All lessons · Malaysia study route

Your goal: Find how many copies of a prime occur inside a factorial without calculating the factorial. Use that count to decide exact divisibility, count trailing zeros and explain why an answer is the largest or smallest possible.

Preparation context: This is original number-theory preparation for students approaching Malaysia’s IMONST 1, including Junior students ready for the prerequisites below. The later written challenges develop proof skills. This is a topic lesson, not a claim about the full syllabus, an official paper or a prediction of future questions. Students from any country can use the same mathematics.

Before you start: Review factorials, prime factorisation and divisibility if necessary. You should know that 34 means four factors of 3, and that a positive integer divides another when the quotient is an integer. We introduce the floor notation and prime-exponent notation here.

A manageable route: In a first sitting of about 30–40 minutes, try the starting checks, study the factor layers and Examples 1–2, and attempt Problems 1–2. In a second sitting, study Examples 3–5 and attempt Problems 3–6. Read the base-12 bridge before attempting Problems 7–9 and the harder adaptive checks. Allow a separate 30–45 minutes for careful written proofs. These are suggested study times, not exam time limits.

Three checks before the new idea

1. What does an exponent count?

Write 72 as a product of primes. What is the largest integer a for which 2a divides 72?

Answer and next step

Divide out factors of 2: 72 = 2 × 36 = 2 × 2 × 18 = 2 × 2 × 2 × 9 = 23 × 32. There are three factors of 2, so a = 3. Indeed 72/8 = 9 is an integer, while 72/16 is not. The requested exponent is 3; the corresponding power is 8. If these were confused, revisit prime factorisation before continuing.

2. Count complete groups

How many positive multiples of 5 are at most 29?

Answer and next step

They are 5, 10, 15, 20 and 25, so the answer is 5. Division gives 29/5 = 5.8, but only five whole multiples fit. We write ⌊29/5⌋ = 5. For a nonnegative number xx, ⌊xx⌋ means the greatest integer no larger than xx. It rounds down, not to the nearest integer.

3. Cancel a shared factorial

Simplify 7!/5! without first multiplying out either factorial.

Answer and next step

Because 7! = 7 × 6 × 5!, cancelling the shared positive factor 5! gives 7!/5! = 7 × 6 = 42. It is not (7 − 5)! = 2. A factorial is a product, so cancellation removes shared factors rather than subtracting the exponents of the factorial sign.

Count factors instead of calculating the factorial

For a positive integer nn, the factorial nn! is the product 1 × 2 × ⋯ × nn. We also use 0! = 1. In this lesson all factorial inputs are nonnegative integers.

Suppose we want the largest power of 2 dividing 12!. Writing out the whole value of 12! would hide the structure. Instead, count how many factors of 2 the factors 1 through 12 contribute. For instance, 8 = 2 × 2 × 2 contributes three, while 12 = 2 × 2 × 3 contributes two.

A notation for exact divisibility

For a prime p and a positive integer N, write vp(N) for the exponent of p in the prime factorisation of N. For example, v2(72) = 3 and v5(72) = 0. Precisely, the power of p with that exponent divides N, but the next higher power does not. Also vp(1) = 0.

Prime exponents add when positive integers are multiplied: combining the prime factors of the two integers combines their copies of p. For instance, v2(8 × 12) = 3 + 2 = 5. If B divides A, they subtract in the integer quotient: vp(A/B) = vp(A) − vp(B). We will only use this quotient rule when the quotient is a positive integer.

The extra-factor layers

Original counting table: factors of 2 in 12!
LayerFactors that contributeExtra 2s
First factor of 22, 4, 6, 8, 10, 126
Second factor of 24, 8, 123
Third factor of 281
Fourth factor of 2None: 16 exceeds 120

The factor 8 appears in three rows deliberately: its three copies of 2 must each be counted. The factor 12 appears twice because it has two copies. Therefore v2(12!) = 6 + 3 + 1 = 10. Counting only the six even numbers would miss four extra copies.

The rule, with its conditions and proof

Prime-factor counting rule (Legendre’s formula). Let p be prime and n a nonnegative integer. Count the multiples of p, then the multiples of p2, then of p3, and so on. Add these counts and stop when the power exceeds n.

In symbols, vp(n!) = ⌊n/p⌋ + ⌊n/p2⌋ + ⌊n/p3⌋ + ⋯ . Only finitely many terms are nonzero.

Why it counts exactly. Every multiple of p contributes a first copy of p. A multiple of p2 contributes a second copy, in addition to its first. Continue this way. A factor containing exactly a copies of p appears in exactly the first a layers, so it contributes exactly the correct number of copies. The number of multiples of pj between 1 and n is ⌊n/pj⌋. Adding all layers therefore counts every prime factor once. When n = 0, all counts are zero, consistent with 0! = 1.

Keep the prime condition. For a composite divisor such as 12, count its prime ingredients separately. It is wrong to add ⌊nn/12⌋, ⌊nn/144⌋ and so on: factors such as 3 and 4 can combine to make 12 without either being a multiple of 12.

Five connected worked examples

Example 1. A prime other than 2

Find the largest integer a such that 3a divides 20!.

Idea. Count layers of 3 rather than evaluating 20!. There are six multiples of 3 up to 20: 3, 6, 9, 12, 15 and 18. Among them, 9 and 18 each supply a second copy of 3. There is no multiple of 27.

Thus v3(20!) = ⌊20/3⌋ + ⌊20/9⌋ = 6 + 2 = 8. The layer argument counts all copies, so 38 divides 20!, whereas 39 does not. That proves maximality as well as giving a candidate.

Your turn 1

Find the largest integer a such that 2a divides 15!.

A small hint

Use divisors 2, 4 and 8. The next power is already larger than 15.

Full solution

The three layer counts are ⌊15/2⌋ = 7, ⌊15/4⌋ = 3 and ⌊15/8⌋ = 1. Their sum is 11. Since the next layer is zero, there are exactly eleven factors of 2 in 15!: 211 divides it but 212 does not.

Why a decimal zero uses one 2 and one 5

A positive integer ends in at least k zeros in its decimal representation exactly when it is divisible by 10k. Since 10k = 2k × 5k, the number of trailing decimal zeros is the smaller of its exponents of 2 and 5. Zeros elsewhere in the digits do not matter.

For a factorial, there are always at least as many factors of 2 as factors of 5. Here is a proof rather than a guess from small cases. For every positive integer j, 2j ≤ 5j, so ⌊n/2j⌋ ≥ ⌊n/5j⌋. Add these inequalities over the finitely many nonzero layers. The prime-factor rule gives v2(n!) ≥ v5(n!). Thus the number of trailing decimal zeros of n! is v5(n!).

Example 2. The extra 5 hidden in 25

How many trailing decimal zeros does 48! have?

Idea. Each zero needs a 5; the previous proof guarantees a matching 2. There are ⌊48/5⌋ = 9 multiples of 5. The factor 25 supplies one extra 5, so add ⌊48/25⌋ = 1. There is no multiple of 125.

The result is 9 + 1 = 10 trailing zeros. It is not 9: 25 = 5 × 5 contributes two copies even though it is only one factor in the factorial.

Your turn 2

How many trailing decimal zeros does 60! have?

A small hint

Both 25 and 50 contribute an extra 5.

Full solution

The count is ⌊60/5⌋ + ⌊60/25⌋ = 12 + 2 = 14. Higher layers are zero. By the factorial comparison of twos and fives, there are enough twos to pair with all fourteen fives.

Example 3. A composite divisor has a recipe

Find the greatest nonnegative integer k for which 12k divides 20!.

Idea. Each copy of 12 needs two factors of 2 and one factor of 3, because 12 = 22 × 3. Count the supplies separately:

  • Twos: v2(20!) = 10 + 5 + 2 + 1 = 18. They can supply at most ⌊18/2⌋ = 9 copies of 12.
  • Threes: v3(20!) = 6 + 2 = 8. They can supply at most 8 copies.

Both requirements must hold, so the smaller capacity gives k = 8. Eight copies use sixteen twos and eight threes, all available. Nine copies would need nine threes, and only eight are present. This last comparison proves that 8 is the greatest possible exponent.

Your turn 3

Find the greatest nonnegative integer k for which 18k divides 16!.

A small hint

Use 18 = 2 × 32. Which prime is needed twice in each copy?

Full solution

We have v2(16!) = 8 + 4 + 2 + 1 = 15 and v3(16!) = 5 + 1 = 6. Each 18 needs one 2 and two 3s, so the capacities are 15 and ⌊6/2⌋ = 3. Hence k = 3. Three copies need three twos and six threes; four copies would require eight threes, which are unavailable.

Reverse the question: exact is different from at least

Let Z(nn) denote the number of trailing decimal zeros of nn!, for a nonnegative integer nn. The count never decreases as nn increases: moving from nn! to (nn + 1)! adds a positive integer factor and cannot remove any fives. It may remain unchanged, increase by one, or jump by more than one when the new factor contains several fives.

For example, Z(24) = 4, while Z(25) = 5 + 1 = 6. Thus no factorial has exactly five trailing decimal zeros: those up to 24! have at most four, and those from 25! onward have at least six. A value can be skipped.

Example 4. Find all factorials with six zeros

Find all nonnegative integers nn for which nn! has exactly six trailing decimal zeros.

Idea. Find where the count first reaches six and where it next increases. We have Z(24) = 4, Z(25) = 6 and Z(30) = 6 + 1 = 7. The intervening factors 26, 27, 28 and 29 have no factor 5, so the count stays six through 29!.

Consequently the answer is n = 25, 26, 27, 28 or 29. This list is complete: monotonicity excludes every smaller nn because Z(24) < 6, and every larger nn because Z(30) > 6.

Your turn 4

Find all nonnegative integers nn for which nn! has exactly seven trailing decimal zeros.

A small hint

Start at 30!, then locate the next factor with a 5.

Full solution

Z(29) = 6, Z(30) = 7 and Z(35) = 7 + 1 = 8. None of 31, 32, 33 or 34 contains a factor 5. Therefore n = 30, 31, 32, 33 or 34. Monotonicity and the two boundary counts exclude every other value.

Cancel by subtracting prime counts

For integers aa ≥ bb ≥ 0, the quotient aa!/bb! is the integer product (bb + 1) × ⋯ × aa. To count one prime in that product, subtract its count in bb! from its count in aa!. Do not automatically assume that a factorial quotient has more twos than fives: the result is not usually a factorial. For example, 5!/4! = 5 has one five but no twos, so it has no decimal zero. Check both supplies.

Example 5. Zeros after cancellation

How many trailing decimal zeros does the integer 20!/12! have?

Idea. Count the fives and twos left after cancelling 12!. The five counts are v5(20!) = 4 and v5(12!) = 2, leaving 4 − 2 = 2 fives.

The two counts are v2(20!) = 18 and v2(12!) = 6 + 3 + 1 = 10, leaving 18 − 10 = 8 twos. The smaller supply is two, so the quotient has 2 trailing decimal zeros. Both pairs can be formed, and a third would need another factor of 5.

Your turn 5

How many trailing decimal zeros does 30!/20! have?

A small hint

Count the prime factors before and after cancellation. Include the extra five from 25.

Full solution

The remaining five count is (6 + 1) − 4 = 3. The remaining two count is (15 + 7 + 3 + 1) − (10 + 5 + 2 + 1) = 26 − 18 = 8. The smaller count is 3, so there are exactly three trailing decimal zeros.

A bridge to zeros in another base

You do not need to convert a large number into base 12 to count its ending zeros. In any integer base b ≥ 2, one trailing zero means a factor of b; k trailing zeros mean a factor of bk. This follows from place value: each move one place to the left multiplies the value by b. Thus the number of trailing base-12 zeros is the greatest k for which 12k divides the number. Example 3 has already taught the required counting method.

The general recipe. Factor the base into distinct primes. If one prime occurs aa times in the base and occurs e times in your number, it can support at most ⌊e/aa⌋ copies of the base. Do this for every prime of the base and take the smallest capacity. Each capacity is necessary, and together they are sufficient because they supply every prime factor of the required power of the base.

As a short check, 144 = 24 × 32. In base 12 its zero count is the smaller of ⌊4/2⌋ and 2, namely 2; indeed 144 = 122 and its base-12 representation is 100. In decimal it has no trailing zero, because it has no factor of 5. Always name the base.

Five mistakes worth catching

  • Counting only multiples of the prime: a multiple of its square supplies an extra copy, and higher powers supply more.
  • Using a composite number in the prime-layer formula: factor it into primes and check each ingredient separately.
  • Answering with a power when an exponent was asked for: if 38 is the greatest dividing power, the exponent is 8.
  • Counting fives alone in an arbitrary quotient: count twos as well unless you have proved a comparison for that particular product.
  • Finding one value when the question says “all”: give the whole constant interval and rule out both sides. Some target zero counts are never attained.

Nine original written problems

Write your reasoning before opening a solution. Problems 1–2 build the method; Problems 3–6 change the constraint; Problems 7–9 ask for general arguments or a new application. The hints are optional and become more specific. These problems are original practice, not official IMONST questions.

Problem 1. The first factorial with enough threes

Find the smallest nonnegative integer n for which 34 divides n!.

Hint 1

Check what happens when the new factor is 9.

Hint 2

Compare the exponent of 3 in 8! with its exponent in 9!.

Full solution

In 8!, the only layer is ⌊8/3⌋ = 2, so 34 does not divide 8!. In 9!, the layer counts give ⌊9/3⌋ + ⌊9/9⌋ = 3 + 1 = 4, so it does divide 9!. Prime counts never decrease as factorial inputs increase, so every n ≤ 8 also fails. Hence the smallest value is 9.

Problem 2. Check both primes after cancelling

Find the number of trailing decimal zeros of 18!/8!.

Hint 1

The quotient is the product 9 × 10 × ⋯ × 18.

Hint 2

Subtract the five counts and the two counts separately, then compare the results.

Full solution

The quotient is a positive integer because 8! cancels from 18!. Its five count is ⌊18/5⌋ − ⌊8/5⌋ = 3 − 1 = 2. Its two count is (9 + 4 + 2 + 1) − (4 + 2 + 1) = 16 − 7 = 9. Each decimal zero needs one of each prime, so the smaller count gives 2 zeros. Nine twos are available, but a third zero is impossible because there are only two fives.

Problem 3. Two threes in each packet

Find the greatest nonnegative integer k for which 18k divides 25!.

Hint 1

Write the prime factorisation of 18 before counting.

Hint 2

Compare v2(25!) with half of v3(25!). Each copy of 18 needs two threes.

Full solution

Since 18 = 2 × 32, the required conditions are k ≤ v2(25!) and 2k ≤ v3(25!). The counts are v2(25!) = 12 + 6 + 3 + 1 = 22 and v3(25!) = 8 + 2 = 10. They give k ≤ 22 and k ≤ 5. Thus k = 5. Five copies use five twos and ten threes; six would require twelve threes, so the answer is maximal.

Problem 4. Remove one factor

Choose an integer tt from 1 through 15 and remove that factor from 15!. For which values of tt does the integer 15!/tt have exactly two trailing decimal zeros?

Hint 1

How many fives does 15! have before a factor is removed?

Hint 2

The remaining two count is at least 11 − 3 = 8. Decide how many fives must be removed.

Full solution

Every allowed t divides 15!, so the quotient is an integer. Initially v5(15!) = 3 and v2(15!) = 7 + 3 + 1 = 11. Since t ≤ 15, it contains at most three twos; a fourth would require t ≥ 16. Thus the quotient still has at least eight twos, and the fives determine its zero count.

To leave exactly two fives, tt must contain exactly one five. Within 1 through 15, these values are 5, 10 and 15. None is divisible by 25, so each removes exactly one five. Every other allowed value removes no five and leaves three zeros. This proves that the list is complete.

Problem 5. A missed zero count

Prove that no factorial has exactly eleven trailing decimal zeros. Then find all nonnegative integers nn for which nn! has exactly twelve trailing decimal zeros.

Hint 1

Look at the change from 49! to 50!.

Hint 2

Calculate Z(49), Z(50) and Z(55); then use monotonicity and the factors in between.

Full solution

The counts are Z(49) = 9 + 1 = 10 and Z(50) = 10 + 2 = 12. The factor 50 supplies two fives, so the count jumps over eleven. Monotonicity shows that factorials with nn ≤ 49 have at most ten zeros, while those with nn ≥ 50 have at least twelve. Hence exactly eleven is impossible.

The factors 51, 52, 53 and 54 introduce no five, so Z(nn) remains twelve for nn = 50 through 54. At 55, Z(55) = 11 + 2 = 13. The two boundary comparisons exclude every other value. Thus n = 50, 51, 52, 53 or 54.

Problem 6. The limiting prime can change

Find the smallest nonnegative integer n for which 126 divides n!.

Hint 1

You need at least twelve twos and six threes. Reaching one condition is not enough.

Hint 2

At 15!, check both supplies; then check the extra factor 16.

Full solution

Since 126 = 212 × 36, both prime requirements must hold. For 15!, the counts are v2(15!) = 7 + 3 + 1 = 11 and v3(15!) = 5 + 1 = 6. The threes suffice but the twos do not. Every smaller factorial has no more twos than 15!, so every n ≤ 15 fails.

Multiplying by 16 adds four twos and no threes. Thus 16! has fifteen twos and six threes, meeting both requirements. Hence the smallest input is n = 16. Unlike Example 3, the two supply was the final obstruction here.

Problem 7. Why successful zero counts come in groups of five

Let z be a nonnegative integer. Prove that either no factorial has exactly z trailing decimal zeros, or exactly five nonnegative integers nn satisfy this condition.

Hint 1

Partition the nonnegative integers into blocks 0–4, 5–9, 10–14, and so on.

Hint 2

In a block 5qq, …, 5qq + 4, the last four factors introduce no five. At the start of the next block a new factor divisible by 5 is added.

Full solution

For each nonnegative integer qq, consider the five inputs 5qq, 5qq + 1, …, 5qq + 4. Moving through this block multiplies the factorial only by integers not divisible by 5. Therefore the exponent of 5, and hence the zero count, is constant throughout the block. This includes the first block: 0!, 1!, 2!, 3! and 4! all have zero trailing decimal zeros.

From the end of one block to the start of the next, the new factor is 5(qq + 1), which is divisible by 5. The zero count therefore increases by at least one. Consequently different blocks have strictly increasing zero counts and cannot share the same count.

If z is attained, it is attained throughout one entire block and in no other block: exactly five inputs. If the count jumps over z, it is attained by none. This proves both alternatives without assuming that every zero count occurs.

Problem 8. One more zero in base 12

How many trailing zeros does 30! have when written in base 12? Find the smallest positive integer m such that m × 30! has at least one more trailing base-12 zero.

Hint 1

Each base-12 zero requires two twos and one three.

Hint 2

Compute both prime counts in 30!. To gain the next zero, compare them with the requirements of the next power of 12.

Full solution

Count v2(30!) = 15 + 7 + 3 + 1 = 26 and v3(30!) = 10 + 3 + 1 = 14. The base is 12 = 22 × 3, so the number of base-12 zeros is the smaller of ⌊26/2⌋ = 13 and 14. Thus 30! has 13 trailing base-12 zeros.

To have at least fourteen, the product must be divisible by 1214 = 228 × 314. Its threes already suffice, but it is short of two twos. Hence m must be divisible by 4. The smallest positive such integer is m = 4, and it works: the resulting counts are twenty-eight twos and fourteen threes. No smaller positive integer can supply two twos.

Problem 9. A whole family of exact exponents

Let p be a prime and n a positive integer. Prove that the integer (pn)!/n! is divisible by pn but not by pn+1.

Hint 1

Write the prime-layer counts for (pn)! and for nn! side by side.

Hint 2

The first layer for (pn)! is exactly nn. Every later layer equals the preceding layer in the count for nn!.

Full solution

Because p ≥ 2, we have pn ≥ n, so the quotient is the positive integer product (n + 1) × ⋯ × pn. The prime-layer count for (pn)! starts with ⌊pn/p⌋ = n. Its second term is ⌊n/p⌋, its third is ⌊n/p2⌋, and each following term continues the layer count for n!. Therefore vp((pn)!) = n + vp(n!).

Subtract the denominator’s prime count. We obtain vp((pn)!/n!) = n. There are exactly n copies of p in the quotient, proving both divisibility by pn and nondivisibility by pn+1.

For a concrete check, take pp = 3 and nn = 4. The quotient 12!/4! has 3-exponent (4 + 1) − 1 = 4, as claimed. This example checks the interpretation; the preceding argument proves the statement for every permitted pair.

Start a short practice round

First read Examples 1–5 so that both factorials and cancelled products feel familiar. The adaptive round chooses six responses from nine available multiple-choice checks. It gives hints, feedback and links back to the relevant explanation. You can use a requested solution as part of a response; finishing six responses means you completed the round, not that you solved six questions independently or mastered the topic.

The written proofs above are separate. The practice engine checks selected answers; it does not automatically grade an arbitrary proof. Practice is free and needs no account. Optional progress is remembered only when you choose to save it on this device.

Interactive practice loads here. You can also use the complete question set below.

Check a written solution

This is a self-review checklist, not an official examination marking scheme. Give yourself one point for each item you can identify in your argument.

  1. Set-up: I state the factorial input range, name the relevant primes and distinguish a requested exponent from a power.
  2. Counting: I include every nonzero prime-power layer and explain why the remaining layers vanish.
  3. Divisor requirements: I factor a composite divisor correctly and check all its prime requirements. For a quotient, I justify integrality before subtracting counts.
  4. Exactness: I show the claimed exponent or value works and why the next exponent, a smaller input, or any omitted case cannot work.
  5. Conclusion: I answer the question asked, name the base for trailing zeros, and give both directions when claiming a complete characterisation.

My proof notebook

Use paper or the optional browser notebook for your working. Saving is your choice; it does not submit your answer for grading.

Choose your next step

  • If extra factors were missed, reconstruct the 12! layer table and retry Your turn 1.
  • If the wrong prime controlled the answer, revisit the recipe for 12 and contrast it with Problem 6.
  • If “all” or “smallest” was difficult, revisit monotonicity and explain the boundary checks in Example 4.
  • If cancellation was unclear, revisit factorials before retrying Example 5.
  • After completing a round, return to your paper and retry the question that led you here without opening its solution. Use the return link when you arrived from a supported paper page, or keep the paper open in your browser.
  • Choose another topic in Malaysia’s study route, browse published country mock papers, or visit your optional local revision list.

Contest context and originality

The official IMONST 1 page provides Malaysia’s contest context and links to organiser resources. Released papers support prime-factor and divisibility reasoning as a useful preparation area; this lesson is not an official syllabus statement or an exam forecast. The explanations, examples, table, written problems and adaptive items here are original AI-assisted teaching material based on standard mathematics. No official problem is reproduced or translated, and no affiliation, endorsement or human-review claim is made. Context checked 24 October 2026.

Prepared for IMOolympiad.com. Report a specific unclear step or correction. Optional progress stays in this browser.