CDS Mathematics · Number System

Remainders by Congruence & Cyclicity

Finding the remainder of an astronomically large power by replacing the base with its own remainder, then exploiting the fact that powers cycle — with the special case of a base congruent to minus one, and Fermat's little theorem for a prime modulus.

All Number System notes CDS Mathematics strategy

Why this matters

Twenty-six PYQs, seven of them HARD — this is the densest HARD unit in the chapter after Factorisation, and CDS asks it every single year. The good news is that almost all of it is one of four moves. The base-congruent-to-minus-one trick alone accounts for six questions, and Fermat's little theorem for four.

Concept 1 of 6: Replacing a number by its remainder

Remainders survive addition, subtraction and multiplication. So before doing anything with a huge number, replace it by its remainder on division by the modulus — the answer is unaffected and the arithmetic becomes trivial.

Definition

Write $a \equiv b \pmod n$ to mean $n \mid (a-b)$ , that is $a$ and $b$ leave the same remainder.

If $a\equiv a'$ and $b\equiv b'$ then $a+b\equiv a'+b'$ , $a-b\equiv a'-b'$ and $ab\equiv a'b'$ .
In particular $a^{k} \equiv (a')^{k}$ , which is what licenses reducing the base first.
Division is NOT allowed in general — you may not cancel a factor from both sides without checking it is coprime to the modulus.
The final answer must be brought into the range $0$ to $n-1$ .

Reduce the base first

a \equiv r \pmod n \;\Longrightarrow\; a^{k} \equiv r^{k} \pmod n

Worked example

What is the remainder when

43^{1000}

is divided by 7?

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2021 · CDS (II) 2021 — Elementary Mathematics · Q4Moderate

Example 1 · Number System · Remainders by Congruence and Cyclicity

What is the remainder after dividing the number

37^{1000}

by 9 ?

A remainder must land in 0 to n minus 1

If your working produces

-1

modulo 18, the remainder is 17, not

-1

. And a remainder on division by 9 can never be 9 — CDS puts exactly that value in the option list for the

37^{1000}

question. Normalise before you answer.

Drill 5 more on replacing a number by its remainder

Concept 2 of 6: When the base is one less than the modulus

a \equiv -1

, then

a^{n}

alternates:

-1

for odd

n

+1

for even

n

. Spotting that the base is one below the modulus is the single most productive observation in this unit, and it takes one glance.

Definition

If $a \equiv -1 \pmod n$ — that is, $a = n-1$ or any number one less than a multiple of $n$ — then

a^{k} \equiv (-1)^{k} = \begin{cases}1 & k \text{ even}\\ -1 \equiv n-1 & k \text{ odd.}\end{cases}

Look for it whenever the base is just under the modulus (17 and 18, 65 and 11 since $65 = 66-1$ , $p$ and $p+1$ ).
It pairs beautifully with a sum: if $a\equiv-1$ and $b\equiv+1$ , then $a^{k}+b^{k}\equiv 0$ for odd $k$ .
Also check $a \equiv +1$ , which is even simpler: every power is 1.

Alternating powers

a\equiv -1 \pmod n \;\Longrightarrow\; a^{k}\equiv(-1)^{k}\pmod n

Worked example

What is the remainder when

29^{101}

is divided by 30?

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2020 · CDS (II) 2020 — Elementary Mathematics · Q11Moderate

Example 2 · Number System · Remainders by Congruence and Cyclicity

17^{2020}

is divided by 18, then what is the remainder ?

Odd power of minus one is the modulus minus one, not minus one

65^{99} \equiv -1 \pmod{11}

means the remainder is 10. Writing

-1

1

are the two wrong answers offered. Similarly

7^{84}

modulo 344 uses

343 \equiv -1

with an even exponent, giving 1 — the parity of the exponent is doing all the work, so read it carefully.

Drill 5 more on when the base is one less than the modulus

Concept 3 of 6: Finding the cycle of powers modulo n

Powers of a fixed base repeat modulo

n

. Compute them until you hit 1 (or repeat an earlier value) — the length of that loop is the cycle, and then only the exponent's remainder modulo the cycle length matters. This is the general tool when neither the minus-one trick nor Fermat applies directly.

Definition

Compute $a^{1}, a^{2}, a^{3},\ldots$ modulo $n$ until a value repeats. If $a^{t}\equiv 1$ , the cycle length is $t$ and

a^{k} \equiv a^{\,k \bmod t} \pmod n,

with the convention that a remainder of 0 means

a^{t}\equiv 1

Look for a small power that is $\pm 1$ ; that shortcut usually appears within four or five steps ( $3^3 = 27 \equiv -1 \bmod 28$ , $2^3 = 8 \equiv 1 \bmod 7$ ).
Finding $a^{t}\equiv -1$ is just as useful: the cycle is then $2t$ .

Cycle reduction

a^{t}\equiv 1 \pmod n \;\Longrightarrow\; a^{k}\equiv a^{\,k \bmod t} \pmod n

Worked example

What is the remainder when

2^{50}

is divided by 9?

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2021 · CDS (I) 2021 — Elementary Mathematics · Q2Moderate

Example 3 · Number System · Remainders by Congruence and Cyclicity

What is the remainder when

2^{1000000}

is divided by 7?

Reduce the exponent modulo the CYCLE, not modulo the divisor

For

2^{50}

modulo 9 the cycle is 6, so reduce 50 modulo 6 — not modulo 9. Mixing the two moduli is the standard error and produces a plausible wrong answer. The divisor sets the arithmetic; the cycle length sets the exponent reduction.

Drill 4 more on finding the cycle of powers modulo n

Concept 4 of 6: Fermat's little theorem

For a prime modulus

p

, any base not divisible by

p

satisfies

a^{p-1}\equiv 1

. So the cycle length always divides

p-1

, and you get the answer without hunting for the cycle at all. CDS names this theorem directly in one question and uses it in three more.

Definition

Fermat's little theorem. If $p$ is prime and $p \nmid a$ , then

a^{p-1}\equiv 1 \pmod p.

Multiplying by $a$ gives the companion form $a^{p}\equiv a \pmod p$ , valid for every $a$ including multiples of $p$ .
It requires the modulus to be prime: $3^{3}-1 = 26$ is not a multiple of 4, so the statement fails at $p=4$ .
It explains why $n^{5}-n$ is always divisible by 5, and $n^{p}-n$ by $p$ .

Fermat's little theorem

a^{p-1}\equiv 1 \pmod p \quad (p \text{ prime},\ p \nmid a)

Worked example

What is the remainder when

3^{16}

is divided by 17?

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2016 · CDS (II) 2016 — Elementary Mathematics · Q15Hard

Example 4 · Number System · Remainders by Congruence and Cyclicity

What is the remainder when

2^{100}

is divided by 101 ?

The exponent p minus one gives 1; the exponent p gives the base back

2^{100} \bmod 101 = 1

but

2^{101} \bmod 101 = 2

. CDS has set both, one year apart, and the option lists overlap. Check whether the exponent is

p-1

p

before answering, and remember the theorem needs the modulus prime — which is exactly what the 2017 statement question tests.

Drill 3 more on fermat's little theorem

Concept 5 of 6: Pairing terms that cancel modulo n

In a sum of several powers, look for pairs whose bases add to the modulus. Each such pair is

a^{k} + (-a)^{k}

, which vanishes when

k

is odd. A four-term sum can collapse to zero in one line.

Definition

If $a+b \equiv 0 \pmod n$ — that is, $b \equiv -a$ — then for odd $k$ ,

a^{k}+b^{k} \equiv a^{k}+(-a)^{k} = 0 \pmod n.

Scan the bases for pairs summing to $n$ (or to a multiple of $n$ ).
The exponent must be odd; for even $k$ the pair doubles instead of cancelling.
More generally, reduce every base and look for any structure — equal residues in a difference cancel too, which is why $27^{27}-15^{27}$ is 0 modulo 6.

Cancelling pair

a+b\equiv 0 \pmod n,\ k \text{ odd} \;\Longrightarrow\; a^{k}+b^{k}\equiv 0

Worked example

What is the remainder when

11^{7} + 12^{7}

is divided by 23?

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2016 · CDS (II) 2016 — Elementary Mathematics · Q97Hard

Example 5 · Number System · Remainders by Congruence and Cyclicity

What is the remainder when

13^5 + 14^5 + 15^5 + 16^5

is divided by 29 ?

Pair the bases before reducing them individually

13^5+14^5+15^5+16^5

modulo 29 the structure is two pairs:

13+16=29

and

14+15=29

. Reducing each base on its own gives four unhelpful residues and a long computation; noticing the pairing gives 0 immediately. Always add the outermost bases together first to check for this.

Drill 1 more on pairing terms that cancel modulo n

Concept 6 of 6: Remainders of sums, differences and products of given remainders

If you know each number's remainder, you know the remainder of any sum, difference or product — just combine the remainders and reduce. The only care needed is with a difference, which can come out negative.

Definition

Given $m \equiv r_1$ and $n \equiv r_2 \pmod d$ :

$m+n \equiv r_1+r_2$ ;
$m-n \equiv r_1-r_2$ , and if that is negative add $d$ ;
$mn \equiv r_1 r_2$ ;

then reduce into $0$ to $d-1$ . Note that $m>n$ does not imply $r_1>r_2$ — the difference's remainder is determined by the residues, not by which number is bigger.

Combining remainders

m\equiv r_1,\ n\equiv r_2 \pmod d \;\Longrightarrow\; m\pm n\equiv r_1\pm r_2,\ \ mn\equiv r_1r_2

Worked example

Two numbers leave remainders 5 and 7 on division by 9. What remainders do their sum and their product leave?

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2025 · CDS (I) 2025 — Elementary Mathematics · Q43Moderate

Example 6 · Number System · Remainders by Congruence and Cyclicity

There are two natural numbers m and n

(m > n)

. When m is divided by 12, it leaves a remainder 4. When n is divided by 12, it leaves a remainder 6. Which of the following statements is/are correct ? I. The remainder when

(m + n)

is divided by 12 is 10. II. The remainder when

(m - n)

is divided by 12 is 10. Select the correct answer using the code given below :

m greater than n does not mean its remainder is greater

With

m\equiv 4

and

n\equiv 6

modulo 12 and

m>n

, the difference is

4-6=-2\equiv 10

— the same as the sum's remainder, which is why the 2025 question can truthfully say both are 10. Students who assume

r_1>r_2

because

m>n

compute

6-4=2

and get it wrong.

Drill 2 more on remainders of sums, differences and products of given 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 (6)

Replacing a number by its remainder
Reduce the base first
$a \equiv r \pmod n \;\Longrightarrow\; a^{k} \equiv r^{k} \pmod n$
When the base is one less than the modulus
Alternating powers
$a\equiv -1 \pmod n \;\Longrightarrow\; a^{k}\equiv(-1)^{k}\pmod n$
Finding the cycle of powers modulo n
Cycle reduction
$a^{t}\equiv 1 \pmod n \;\Longrightarrow\; a^{k}\equiv a^{\,k \bmod t} \pmod n$
Fermat's little theorem
Fermat's little theorem
$a^{p-1}\equiv 1 \pmod p \quad (p \text{ prime},\ p \nmid a)$
Pairing terms that cancel modulo n
Cancelling pair
$a+b\equiv 0 \pmod n,\ k \text{ odd} \;\Longrightarrow\; a^{k}+b^{k}\equiv 0$
Remainders of sums, differences and products of given remainders
Combining remainders
$m\equiv r_1,\ n\equiv r_2 \pmod d \;\Longrightarrow\; m\pm n\equiv r_1\pm r_2,\ \ mn\equiv r_1r_2$

Watch out for (6)

A remainder must land in 0 to n minus 1
→ Replacing a number by its remainder
Odd power of minus one is the modulus minus one, not minus one
→ When the base is one less than the modulus
Reduce the exponent modulo the CYCLE, not modulo the divisor
→ Finding the cycle of powers modulo n
The exponent p minus one gives 1; the exponent p gives the base back
→ Fermat's little theorem
Pair the bases before reducing them individually
→ Pairing terms that cancel modulo n
m greater than n does not mean its remainder is greater
→ Remainders of sums, differences and products of given remainders

Test yourself on Number System

20 past CDS questions from this chapter, timed at 24 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 Number System chapter test Drill all 26 questions