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.

Test yourself — a quick 18-question Binomial Theorem recall quiz, instant score.

Concept 1 of 2: Remainders by the Binomial Trick

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.

The same idea in a real exam question:

NDA · Sep 2024 · Q36Moderate

Example 1 · Binomial Theorem · Remainders and Divisibility via Binomial Expansion

What is the remainder when

7^n-6n

is divided by 36 for

n=100

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)

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

The same idea in a real exam question:

NDA · Apr 2024 · Q10Moderate

Example 2 · Binomial Theorem · Remainders and Divisibility via Binomial Expansion

26!=n\cdot 8^k

, where

k

and

n

are positive integers, then what is the maximum value of

k

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)

Test yourself on Binomial Theorem

15 past NDA questions from this chapter, timed at 19 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 Binomial Theorem chapter test Drill all 3 questions