SSC CGL Maths · Number System

Remainders by Congruence and Cyclicity

In a sum, a product or a power you may replace every number by its remainder, so even a huge power shrinks to a small number before you divide.

All Number System notes

Why this matters

Ten questions in the bank, seven EASY and three MODERATE, six of them from the 2024 shifts. None of them needs a long division: swap each number for its remainder, and a power with an exponent in the thousands collapses to 1 or to one less than the divisor in a single line.

Concept 1 of 2: Replacing a number by its remainder

N = 9k + 4

, the

9k

part is a pile of complete nines, and complete nines never change a remainder on division by 9. Only the 4 matters, so you can carry the 4 through any adding or multiplying.

Definition

Notation: $N \equiv r \pmod d$ reads 'N leaves the same remainder as r on division by d'.
In a sum, difference or product, replace each number by its remainder, work out the small result, then reduce it again. An expression like $5n^2 + 3n + 1$ is just products and sums, so the same swap works.
A divisor of the divisor: if $N$ leaves $r$ on division by $d$ , and $m$ divides $d$ , then $N$ leaves the remainder of $r$ on division by $m$ .
If $m$ does not divide $d$ , the remainder by $m$ cannot be found from this information alone.
Check with a small number: if $N$ leaves 4 on division by 9, try $N = 4$ or $N = 13$ .

Swapping numbers for remainders

N = dk + r \Rightarrow N \equiv r \pmod d \qquad a \equiv r, \ b \equiv s \pmod d \Rightarrow a + b \equiv r + s, \ ab \equiv rs \pmod d

dthe divisor
r, sthe remainders of a and b on division by d

Worked example

A number x leaves remainder 4 when divided by 9. Find the remainder when

x^2 + 2x

is divided by 9.

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

SSC CGL · 2024 · Tier I, 18 Sep 2024, Shift 1 · Q59Easy

Example 1 · Number System · Remainders by Congruence and Cyclicity

A number r when divided by 8 leaves remainder 3. What will be the remainder when

(r^2+6r+7)

is divided by 8?

Moving to a divisor that does not divide the first one

A remainder on division by 45 gives the remainder on division by 15, 9, 5 or 3, because they divide 45. It says nothing exact about division by 12.

Leaving the answer bigger than the divisor

After swapping, reduce again. Remainder 5 on division by 7, tripled, is 15, and the remainder is

15 - 14 = 1

, not 15.

Drill 3 more on replacing a number by its remainder

Concept 2 of 2: Remainders of large powers

Swap the base for its remainder first. If that remainder is 1, every power of it is 1. If it is one less than the divisor, it behaves like

-1

, and

-1

to any power is just

1

-1

. Anything else repeats in a short cycle.

Definition

Find the base's remainder on division by $d$ .
Remainder 1: $a^n$ leaves 1, for every $n$ .
Remainder $d - 1$ (that is, $a \equiv -1$ ): $a^n$ leaves 1 when $n$ is even and $d - 1$ when $n$ is odd.
Any other remainder: list the remainders of $a, a^2, a^3, \ldots$ until they repeat. If the cycle has length $c$ , $a^n$ leaves the same remainder as $a^{\text{remainder of } n \div c}$ (use $a^c$ when that remainder is 0).
Then add or subtract any extra terms and reduce. A negative result is not a remainder: add $d$ .

Powers when the base leaves 1 or one less than the divisor

a \equiv 1 \pmod d \Rightarrow a^n \equiv 1 \qquad a \equiv -1 \pmod d \Rightarrow a^n \equiv 1 \ (n \text{ even}), \ a^n \equiv d - 1 \ (n \text{ odd})

athe base
dthe divisor
nthe exponent

Worked example

Find the remainder when

11^{15}

is divided by 12, and the remainder when

2^{25}

is divided by 7.

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

SSC CGL · 2024 · Tier I, 10 Sep 2024, Shift 2 · Q68Moderate

Example 2 · Number System · Remainders by Congruence and Cyclicity

(77^{77} + 77)

is divided by 78, then the remainder will be:

Writing minus one as the remainder

A remainder is never negative. When the working gives

-1

on division by 13, the remainder is

13 - 1 = 12

Ignoring whether the exponent is odd or even

A base one less than the divisor leaves 1 for an even exponent but leaves one less than the divisor for an odd one. Check the exponent's parity before you write the answer.

Drill 5 more on remainders of large powers

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)

Replacing a number by its remainder
Swapping numbers for remainders
$N = dk + r \Rightarrow N \equiv r \pmod d \qquad a \equiv r, \ b \equiv s \pmod d \Rightarrow a + b \equiv r + s, \ ab \equiv rs \pmod d$
Remainders of large powers
Powers when the base leaves 1 or one less than the divisor
$a \equiv 1 \pmod d \Rightarrow a^n \equiv 1 \qquad a \equiv -1 \pmod d \Rightarrow a^n \equiv 1 \ (n \text{ even}), \ a^n \equiv d - 1 \ (n \text{ odd})$

Watch out for (4)

Moving to a divisor that does not divide the first one
→ Replacing a number by its remainder
Leaving the answer bigger than the divisor
→ Replacing a number by its remainder
Writing minus one as the remainder
→ Remainders of large powers
Ignoring whether the exponent is odd or even
→ Remainders of large powers

Test yourself on Number System

20 past SSC CGL questions from this chapter, timed at 12 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 10 questions