Divisibility of Factorial | Divisibility | Mockat

Quant›Divisibility›Divisibility of Factorial

Loading Video....

21:50

Divisibility of Factorial

Mockat Admin21:50

Module 4 of 8

Overview

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

CAT 2025 Lesson : Divisibility - Divisibility of Factorial

Divisibility

3. Factorials

3.1 Power of a prime number in a factorial

3.1.1 Successive Division

Example 9

Solution

3.2 Factorials and division of composite numbers

Example 10

Solution

3.3 Number of zeroes

Example 11

Solution

Example 12

Solution