Back

Divisibility

ALL MODULES

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}

Example 9

What is the highest power of

7

that divides

1000!

Solution

∴ The highest power of

7

which divides

1000! = 142 + 20 + 2 = \bm{164}

Answer:

164

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

p

q

and

r

respectively and note the quotients.
Step 4: The lowest quotient from Step

3

is the answer.

Example 10

What is the highest power of

24

that divides

90!

Solution

Step 1:

24 = 2^{3} \times 3 ^{1}

Step 2:

Step 3:

The highest power of

2^{3} = \text{Quot} \left(\dfrac{86}{3} \right) = 28

The highest power of

3^{1} = \text{Quot} \left(\dfrac{44}{1} \right) = 44

Step 4: Lowest quotient in step 3 is

28

.

∴ The highest power of

24

which divides

90! = \bm{28}

Answer:

28

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.

Example 11

When

200!

is written as a natural number, how many consecutive zeroes are there in the extreme right of the number?

Solution

We get

n

zeroes at the end of a number if it is a multiple of

10^{n}

.
∴ We need to find the highest power of 10 that divides

200!

10 = 2^{1} \times 5^{1}

As the power of both the prime factors is the same (which is

1

), the larger prime will be occurring fewer number of times in a given factorial.

∴ Highest power of

2

which divides

200!

> Highest power of

5

which divides

200!

As we are concerned with the smaller of these powers, the highest power of

5

which divides

200!

will be the highest power of

10

which divides

200!

Number of zeroes at the end of

200! \space =

The highest power of

5

200!

= 40 + 8 + 1 = 49

Answer:

49

Example 12

n!

has

19

zeroes right before the first non-zero digit, then which of the following could be the value of

n

?

(1)

75

(2)

83

(3)

87

(4)

90

Solution

As explained above, to find the number of zeroes at the end, we need to find the highest power of

5

that divides

n!

We start with the smallest number in the options.

Highest power of

5

that divides

\bm{75!} = 15 + 3 = \bm{18}

83!

has one more

5

multiple (which is

80

) than

75!

.

Highest power of

5

that divides

\bm{83!} = 18 + 1 = \bm{19}

∴

\bm{83!}

will have

\bm{19 \space zeroes}

at the end.

Answer:

83

Loading Video....