JEE Mains Maths · Permutations and Combinations

Divisibility, Divisors and Factorials

Counting with number theory: the power of a prime in n!, divisors of a given form, how many numbers in a range are multiples of one number but not another, and pairs chosen by their remainders.

All Permutations and Combinations notes JEE Mains Maths strategy

Why this matters

Twenty PYQs, fifteen of them numerical answer. Five find the power of a prime in a factorial, ten count multiples or gcd conditions by inclusion–exclusion, and five sort numbers by remainder before pairing them. Three ideas cover the page.

Concept 1 of 3: Powers of a prime in n!, and counting divisors

The power of a prime

p

n!

\left\lfloor\frac np\right\rfloor+\left\lfloor\frac n{p^2}\right\rfloor+\cdots

: each multiple of

p

gives one factor, each multiple of

p^2

one more, and so on. For a composite base like

40=2^3\cdot5

, the answer is the smallest of the separate limits. A number

p^aq^b\cdots

has

(a+1)(b+1)\cdots

divisors; a condition on the divisor (odd, of the form

4n+1

) restricts each exponent.

Definition

Legendre: $v_p(n!)=\sum_{k\ge1}\left\lfloor\frac{n}{p^k}\right\rfloor$ .
Largest $m$ with $a^m\mid n!$ : $\min_p\left\lfloor\frac{v_p(n!)}{v_p(a)}\right\rfloor$ .
Divisors of $p^aq^b$ : $(a+1)(b+1)$ .
Odd divisors: set the exponent of 2 to 0.

Legendre's formula

v_p(n!)=\left\lfloor\frac np\right\rfloor+\left\lfloor\frac n{p^2}\right\rfloor+\left\lfloor\frac n{p^3}\right\rfloor+\cdots

Worked example

Find the largest

n

with

5^n\mid 100!

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

JEE Mains · 2025 · 2 Apr 2025 · Q51Moderate

Example 1 · Permutations and Combinations · Divisibility, Divisors and Factorials

The largest

n \in N

such that

3^{n}

divides 50 ! is:

The scarcer prime decides

For

40^n\mid n!

you need both

2^{3n}

and

5^n

. Compute each limit and take the smaller; the prime that appears less often usually wins.

Drill 4 more on powers of a prime in n!, and counting divisors

Concept 2 of 3: Counting multiples in a range

The multiples of

d

up to

N

number

\left\lfloor\frac Nd\right\rfloor

; in a range, subtract the count below it. 'By

a

b

' is

|A|+|B|-|A\cap B|

, where the overlap counts multiples of

\operatorname{lcm}(a,b)

. A gcd condition such as

\gcd(n,54)=2

becomes 'even, and not divisible by 3'.

Definition

Multiples of $d$ in $[a,b]$ : $\left\lfloor\frac bd\right\rfloor-\left\lfloor\frac{a-1}d\right\rfloor$ .
$|A\cup B|=|A|+|B|-|A\cap B|$ ; overlap uses the lcm.
$\gcd(n,m)=g$ : $g\mid n$ and $\gcd\left(\frac ng,\frac mg\right)=1$ .
Coprime to 24 means not divisible by 2 or 3.

Inclusion–exclusion

|A\cup B|=|A|+|B|-|A\cap B|

Worked example

How many numbers from 1 to 100 are divisible by 4 or 6?

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

JEE Mains · 2023 · 29 January 2023 · Q163Moderate

Example 2 · Permutations and Combinations · Divisibility, Divisors and Factorials

The number of 3 digit numbers, that are divisible by either 3 or 4 but not divisible by 48 , is

Use the lcm, not the product

Numbers divisible by both 4 and 6 are multiples of 12, not of 24. Always take the lcm for the overlap.

Drill 9 more on counting multiples in a range

Concept 3 of 3: Pairing numbers by their remainders

To count pairs whose sum is divisible by

m

, sort the numbers by remainder mod

m

: a pair works when the remainders add to

0

m

. Multiply the class sizes for each matching pair of classes. Powers work the same way:

6^m\equiv1\pmod5

for every

m

, so only the other term decides.

Definition

$x+y\equiv0\pmod m$ : remainders $r$ and $m-r$ .
Same class $r=0$ (or $r=\frac m2$ ): choose two from one class.
Ordered pairs: count $(r,s)$ and $(s,r)$ separately.
Cycles of powers mod $m$ decide divisibility of sums of powers.

Matching classes

\#\{x+y\equiv0\}=\sum_{r+s\equiv0}|C_r|\,|C_s|

Worked example

How many unordered pairs of distinct numbers from 1 to 10 have a sum divisible by 3?

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

JEE Mains · 2023 · 25 Jan 2023 · Q87Moderate

Example 3 · Permutations and Combinations · Divisibility, Divisors and Factorials

Let

x

and

y

be distinct integers where

1 \leq x \leq 25

and

1 \leq y \leq 25

. Then, the number of ways of choosing

x

and

y

such that

x+y

is divisible by 5, is

Ordered or unordered

'Ways of choosing

x

and

y

' with named variables counts ordered pairs. Decide before multiplying, and for pairs inside one class use

k(k-1)

ordered or

\binom k2

unordered.

Drill 4 more on pairing numbers by their remainders

Summary — formulas & gotchas at a glance

A revision cheat-sheet for the formulas and gotchas above. Click any concept name to jump back to its full explanation.

Formulas (3)

Powers of a prime in n!, and counting divisors
Legendre's formula
$v_p(n!)=\left\lfloor\frac np\right\rfloor+\left\lfloor\frac n{p^2}\right\rfloor+\left\lfloor\frac n{p^3}\right\rfloor+\cdots$
Counting multiples in a range
Inclusion–exclusion
$|A\cup B|=|A|+|B|-|A\cap B|$
Pairing numbers by their remainders
Matching classes
$\#\{x+y\equiv0\}=\sum_{r+s\equiv0}|C_r|\,|C_s|$

Watch out for (3)

The scarcer prime decides
→ Powers of a prime in n!, and counting divisors
Use the lcm, not the product
→ Counting multiples in a range
Ordered or unordered
→ Pairing numbers by their remainders

Test yourself on Permutations and Combinations

20 past JEE Mains questions from this chapter, timed at 48 minutes and marked the way the exam marks it. You see your score and every answer the moment you finish. Free to start.

Take the Permutations and Combinations chapter test Drill all 20 questions