NDA Maths · Binomial Theorem

Remainders & Divisibility via Binomial Expansion

Writing a base as (multiple ± 1) and expanding by the binomial theorem makes a remainder fall out — every term except the last is divisible by the modulus, so only the tail survives.

All Binomial Theorem notes NDA Maths strategy

Why this matters

Only 3 PYQs, but they are quick marks once you see the move: re-express the base near a multiple of the divisor. The same idea also handles the power of a prime hidden inside a factorial.

Concept 1 of 2

Remainders by the Binomial Trick

Intuition

To find a remainder of a big power, rewrite the base as a multiple of the divisor plus or minus a small number, then expand. Every term that carries the 'multiple' factor is divisible by the divisor and vanishes mod m — only the small leftover terms decide the remainder.

Definition

To find $A^n \bmod m$ : write $A = km \pm 1$ (or $km \pm c$ for a small $c$ ) and expand $(km \pm 1)^n = \sum_r \binom{n}{r}(km)^r(\pm 1)^{n-r}$ . Every term with $r \ge 1$ has a factor $m$ , so

A^n \equiv (\pm 1)^n \pmod{m}.

More generally, keep only the terms NOT divisible by

m

. Pairing this with a small subtraction (e.g.

7^n - 6n - 1

) shows divisibility because the surviving low-order terms cancel.

Base near a multiple of m

(km \pm 1)^n \equiv (\pm 1)^n \pmod{m}

Worked example

Find the remainder when

2^{120}

is divided by 7.

$2^{120} = (2^3)^{40} = 8^{40} = (7+1)^{40}$ .
$(7+1)^{40} = \sum_r \binom{40}{r} 7^r$ ; every term with $r \ge 1$ is divisible by 7.
Only the $r = 0$ term survives mod 7: $\binom{40}{0}\cdot 1 = 1$ .

Answer:Remainder

= 1

From the bank · past-year question

Example 1Binomial TheoremMODERATE

What is the remainder when

7^n-6n

is divided by 36 for

n=100

[Q36 · Sep · 2024]

Choose the base CLOSEST to a multiple of the divisor

Rewrite the base as the divisor (or a power of it)

\pm 1

8 = 7+1

for mod 7;

7 = 6+1

for mod 6/36. Picking a far-off form leaves many surviving terms and defeats the trick.

Drill 1 more on remainders by the binomial trick

Concept 2 of 2

Power of a Prime in n! (Legendre's Formula)

Intuition

To find the largest power of a prime dividing n!, count how many of 1…n are multiples of the prime, then multiples of its square, its cube, and so on — each layer contributes one extra factor. For a composite divisor, find the prime's exponent first and then divide.

Definition

The exponent of a prime $p$ in $n!$ is Legendre's formula

E_p(n!) = \left\lfloor \dfrac{n}{p} \right\rfloor + \left\lfloor \dfrac{n}{p^2} \right\rfloor + \left\lfloor \dfrac{n}{p^3} \right\rfloor + \cdots

(the sum is finite — stop when

p^k > n

). For a composite divisor like

8 = 2^3

: find the power of

2

n!

, then the highest

k

with

8^k \mid n!

\left\lfloor E_2(n!)/3 \right\rfloor

Legendre's formula

E_p(n!) = \sum_{i\ge 1} \left\lfloor \dfrac{n}{p^{\,i}} \right\rfloor

Worked example

26! = n \cdot 8^k

with

n, k

positive integers, find the maximum

k

Power of 2 in $26!$ : $\lfloor 26/2 \rfloor + \lfloor 26/4 \rfloor + \lfloor 26/8 \rfloor + \lfloor 26/16 \rfloor = 13 + 6 + 3 + 1 = 23$ .
Since $8 = 2^3$ , the max $k$ is $\lfloor 23/3 \rfloor$ .

Answer:

k = 7

From the bank · past-year question

Example 2Binomial TheoremMODERATE

26!=n\cdot 8^k

, where

k

and

n

are positive integers, then what is the maximum value of

k

[Q10 · Apr · 2024]

Count the prime, then divide by its exponent

For

8 = 2^3

, don't count "multiples of 8". Count the total power of 2 (via Legendre), then take the floor of that over 3. Counting 8s directly undercounts badly.

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 (2)

Remainders by the Binomial Trick
Base near a multiple of m
$(km \pm 1)^n \equiv (\pm 1)^n \pmod{m}$
Power of a Prime in n! (Legendre's Formula)
Legendre's formula
$E_p(n!) = \sum_{i\ge 1} \left\lfloor \dfrac{n}{p^{\,i}} \right\rfloor$

Watch out for (2)

Choose the base CLOSEST to a multiple of the divisor
→ Remainders by the Binomial Trick
Count the prime, then divide by its exponent
→ Power of a Prime in n! (Legendre's Formula)

Mastery check — 1 interleaved questions

Try each one before clicking. Questions are interleaved across the concepts above, not grouped — interleaving sharpens transfer.

Example 1Binomial TheoremEASY

What is the remainder when

2^{120}

is divided by 7?

[Q18 · Apr · 2024]

Drill every past-year question on this subtopic

3 questions from the bank — paginated, with cart and Word-export support.

Drill the 3 questions