CAT 2025 Lesson : Divisibility - Divisibility of Factorial

3. Factorials

Factorial is represented by an exclamation mark (!).

'n!', read as 'n factorial', is the product of all natural numbers less than or equal to n.
∴ $n! = 1 \times 2 \times ... \space \times n$

Exception: Although $0$ is not a natural number, $\bm{0! = 1}$.

3.1 Power of a prime number in a factorial

Let's look at this with an example. The highest power of $5$ that can divide $100!$, is the power of $5$ when $100!$ is prime factorised.

$100! = 1 \times 2 \times 3 \times ... \space \times 100$

$100!$ contains $\bm{20}$ multiples of $\bm{5}$ ⇒ $5 \times 1, \space 5 \times 2, \space ..., \space 5 \times 20$

In these, there are $\bm{4}$ multiples of $\bm{5^2}$ ⇒ $25 \times 1, \space 25 \times 2, \space 25 \times 3, \space 25 \times 4$

As the multiples of $5^2$ were already counted as multiples of $5$, we simply add them one more time.
∴ The highest power of $5$ which divides $100! = 20 + 4 = \bm{24}$

3.1.1 Successive Division

An easier way to find this is through successive division. The highest power of a prime number x, that divides $\bm{n!}$ is the sum of quotients when n is successively divided by $x$ (as shown below).



∴ The highest power of $5$ which divides $100! = 20 + 4 + 0 = \bm{24}$

3.2 Factorials and division of composite numbers

Let $x = a^{p}b^{q}c^{r}$, where $a$, $b$ and $c$ are prime numbers. To find the largest power of $x$ that would perfectly divide a given factorial, say $n!$.

Step 1: Prime factorise $x$ and write it as $x = a^{p}b^{q}c^{r}$
Step 2: Find the highest power of $a$, $b$ and $c$ that can perfectly divide $n!$
Step 3: Divide the highest power of $a$, $b$ and $c$ from Step $2$ by $p$, $q$ and $r$ respectively and note the quotients.
Step 4: The lowest quotient from Step $3$ is the answer.

3.3 Number of zeroes

The number of zeroes at the end of a factorial will be the highest power of $5$ that divides the factorial. This is explained in the example below.