Remainders & remainder theorem — notes, question types & practice · Number System

01

Overview

When 47 sweets are shared among 5 children, each gets 9 and 2 are left over. Here 47 is the dividend, 5 the divisor, 9 the quotient and 2 the remainder. The remainder is always smaller than the divisor. Every question in this lesson is built on that one idea.

02

The division formula

\text{dividend} = \text{divisor} \times \text{quotient} + \text{remainder}

With divisor 24, quotient 13 and remainder 17, the dividend is $24 \times 13 + 17 = 329$ . Questions that give two of the four quantities in words are asking for this formula.

Rule: Write the formula first, fill in what is given, and solve for the missing piece. Check that the remainder stays below the divisor.

03

Remainders add and multiply

The remainder of a sum or a product equals the remainder of the sum or product of the individual remainders. Replace each big number by its remainder first, then multiply small numbers.

For $(1021 \times 1023 \times 1025) \div 17$ : the remainders are $1$ , $3$ and $5$ , and $1 \times 3 \times 5 = 15$ , so the remainder is $15$ .

04

Negative remainders keep numbers small

A remainder may be written as a negative number. $98$ leaves $-1$ with $99$ , and $97$ leaves $-2$ . So $98 \times 97 \times 96$ leaves $(-1)(-2)(-3) = -6$ , and adding the divisor gives $93$ .

Tip: If your final remainder is negative, add the divisor once. If it is still negative, add again.

05

Big powers cycle

Powers repeat their remainders. Find a small power that leaves $1$ or $-1$ , then split the exponent.

$2^3 = 8$ leaves $1$ with $7$ , so $2^{100} = (2^3)^{33} \times 2$ leaves $2$ .
A base one more than the divisor always leaves $1$ .
A base one less than the divisor leaves $1$ for even powers and $d - 1$ for odd powers.
Fermat: for a prime $p$ that does not divide the base, $a^{p-1}$ leaves $1$ with $p$ .

06

When the new divisor divides the old

If $N$ leaves $r$ with divisor $D$ , and the new divisor $d$ is a factor of $D$ , then $N$ leaves $r \bmod d$ with $d$ . Since $342 = 18 \times 19$ , a remainder of $47$ with $342$ means remainders $11$ with $18$ and $9$ with $19$ .

Watch: This works one way only. Knowing the remainder with $d$ tells you nothing about the remainder with $D$ .

07

Dividing successively

'Divided successively by 4 and 5 leaving remainders 1 and 2' means: divide $N$ by $4$ , then divide that quotient by $5$ . Rebuild from the last step: the smallest final quotient is $0$ , so the middle value is $0 \times 5 + 2 = 2$ and $N = 4 \times 2 + 1 = 9$ .

08

Factorial sums collapse early

From $5! = 120$ onwards every factorial is a multiple of $15$ . So for $1! + 2! + \cdots + 50!$ divided by $15$ , only $1 + 2 + 6 + 24 = 33$ matters, and the remainder is $3$ .

Example: A number leaves remainder 5 with 9. Then $4N$ leaves $4 \times 5 = 20$ , and $20 \bmod 9 = 2$ .

09

Question types you will see

Each type: how to recognise it, the method step by step, and one question to try.

Type 1very common3 practice Q

Remainder with a factor of the old divisor

How to spot it:

A number leaves a remainder with a big divisor, and the question asks for the remainder with a smaller number that divides that divisor.

N = Dq + r,\ d \mid D \ \Rightarrow\ N \bmod d = r \bmod d

Method

Check that the new divisor $d$ truly divides the old divisor $D$ .
Divide the old remainder $r$ by $d$ .
The new remainder is $r \bmod d$ .

Why it works:

The term Dq is a multiple of d, so only r decides the remainder.

Try this

A number leaves remainder 47 when divided by 342. What is the remainder when it is divided by 19?

Show solution

$342 = 18 \times 19$ , so $19$ is a factor of $342$ .
Reduce the old remainder: $47 \bmod 19$ .
$47 = 2 \times 19 + 9$ , so the remainder is $9$ .

Answer

9

Type 2very common2 practice Q

Remainder of a product or sum

How to spot it:

Several large numbers are multiplied or added and the remainder with a modest divisor is asked.

(a \times b) \bmod d = [(a \bmod d) \times (b \bmod d)] \bmod d

Method

Replace every number by its remainder; negative remainders are allowed.
Multiply or add the small remainders.
Reduce again by $d$ , and add $d$ to any negative result.

Why it works:

Each number is a multiple of d plus a remainder, and multiples of d never change the remainder.

Try this

Find the remainder when 98 x 97 x 96 is divided by 99.

Show solution

Remainders with $99$ : $98 \to -1$ , $97 \to -2$ , $96 \to -3$ .
$(-1)(-2)(-3) = -6$ .
Add the divisor: $99 - 6 = 93$ .

Answer

93

Type 3very common3 practice Q

Remainder of a large power

How to spot it:

A power like 2 to the 95 or 5 to the 70 is divided by a small number, usually 7, 9, 13 or a number near the base.

a^{p-1} \equiv 1 \pmod p, \qquad (d - 1)^n \equiv (-1)^n \pmod d

Method

Reduce the base with respect to the divisor.
Find the smallest power that leaves $1$ or $-1$ .
Split the exponent using that power and keep the leftover part.
Multiply the leftover remainder by the cycle answer and reduce.

Why it works:

Once some power leaves remainder 1, the remainders repeat in a fixed cycle.

Try this

Find the remainder when 2 to the power 95 is divided by 7.

Show solution

$2^3 = 8$ leaves $1$ with $7$ .
$95 = 3 \times 31 + 2$ , so $2^{95} = (2^3)^{31} \times 2^2$ .
Remainder: $1 \times 4 = 4$ .

Answer

4

Type 4common2 practice Q

Division formula: find the dividend

How to spot it:

The divisor and quotient are described in terms of the remainder, and the dividend is asked.

\text{dividend} = \text{divisor} \times \text{quotient} + \text{remainder}

Method

Write every unknown in terms of the one given value, usually the remainder.
Compute the divisor and the quotient.
Substitute into the division formula.
Check the remainder is smaller than the divisor.

Why it works:

The formula is the definition of division; everything else is substitution.

Try this

In a division, the quotient is three times the remainder and the divisor is four times the quotient. If the remainder is 5, find the dividend.

Show solution

Quotient $= 3 \times 5 = 15$ .
Divisor $= 4 \times 15 = 60$ .
Dividend $= 60 \times 15 + 5 = 905$ .

Answer

905

Type 5common2 practice Q

Remainder of an expression built from N

How to spot it:

The remainder of N with a divisor is given, and the question asks for the remainder of a multiple, square or cube of N.

N \equiv r \ \Rightarrow\ kN \equiv kr,\ N^2 \equiv r^2, \ N^3 \equiv r^3 \pmod d

Method

Replace $N$ by its remainder $r$ everywhere in the expression.
Compute the small expression.
Reduce by $d$ ; add $d$ if the result is negative.
Check with the smallest such $N$ , which is $r$ itself.

Why it works:

N equals dq + r, and every term containing dq is a multiple of d.

Try this

When N is divided by 11 the remainder is 4. Find the remainder when N cubed plus N is divided by 11.

Show solution

Replace $N$ by $4$ : $4^3 + 4 = 64 + 4 = 68$ .
$68 \bmod 11$ : $68 = 6 \times 11 + 2$ .
Remainder $2$ . Check with $N = 15$ : $3390 \bmod 11 = 2$ .

Answer

2

Type 6occasional2 practice Q

Successive division

How to spot it:

A number is divided successively by two or three divisors, each acting on the previous quotient, and remainders are given.

x = d_1 y + r_1, \quad y = d_2 z + r_2

Method

Start from the last division and take its smallest quotient as $0$ .
Rebuild one step left: value $=$ divisor $\times$ next value $+$ remainder.
Repeat until you reach the original number.
Verify by dividing forward again.

Why it works:

Successive division is the division formula applied along a chain, so rebuilding runs backwards.

Try this

Find the smallest number which leaves remainders 1 and 2 when divided successively by 4 and 5.

Show solution

Second step: quotient $0$ , so the middle value is $0 \times 5 + 2 = 2$ .
First step: $4 \times 2 + 1 = 9$ .
Check: $9 \div 4 = 2$ remainder $1$ , and $2 \div 5 = 0$ remainder $2$ .

Answer

9

Type 7occasional

Remainder of a factorial sum

How to spot it:

A sum like 1! + 2! + ... + n! is divided by a number such as 15, 12 or 10, and the remainder is asked.

Method

Note the divisor: from $5! = 120$ on, every factorial is a multiple of $15$ , $10$ and $120$ .
Keep only the factorials that are not multiples of the divisor.
Add them, reduce by the divisor, and done.

Why it works:

A factorial accumulates every smaller factor, so large factorials contain the divisor as a factor.

Try this

Find the remainder when 1! + 2! + 3! + ... + 50! is divided by 15.

Show solution

Every term from $5! = 120$ on is a multiple of $15$ .
Add the first four: $1 + 2 + 6 + 24 = 33$ .
$33 \bmod 15 = 3$ .

Answer

3

10

Formula sheet

Division algorithm

N = d \times q + r, \quad 0 \le r < d

Product rule

\mathrm{rem}\left(\dfrac{a \times b}{d}\right) = \mathrm{rem}\left(\dfrac{R_a \times R_b}{d}\right)

same for sums

Fermat's little theorem

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

Divisor-multiple rule

N \equiv r \pmod{D},\ d \mid D \ \Rightarrow\ N \equiv r \pmod{d}

one-way rule

Base one more than divisor

(ad + 1)^n \equiv 1 \pmod{d}

Base one less than divisor

(ad - 1)^n \equiv (-1)^n \pmod{d}

1 if n even, d - 1 if n odd

11

Shortcuts that save time

⚡ Make the base plus or minus one

Write the base as (multiple of divisor) plus or minus 1. The whole power then collapses to plus or minus 1.

Example

Find the remainder when 15 to the power 47 is divided by 16.

Show solution

$15 = 16 - 1$ , so $15 \equiv -1 \pmod{16}$ .
$15^{47} \equiv (-1)^{47} = -1$ .
Add the divisor: $16 - 1 = 15$ .

Answer

15

⚡ Negative remainders for products

When factors sit just below the divisor, replace each by a small negative remainder and multiply those.

Example

Find the remainder when 98 x 97 x 96 is divided by 99.

Show solution

Remainders: $-1$ , $-2$ , $-3$ .
Product: $(-1)(-2)(-3) = -6$ .
Add the divisor: $99 - 6 = 93$ .

Answer

93

⚡ Divisor is a factor, just reduce

If the new divisor divides the old one, reduce the old remainder by the new divisor. If it does not divide it, this shortcut is not available.

Example

A number leaves remainder 29 when divided by 56. What is the remainder when it is divided by 8?

Show solution

$56 = 8 \times 7$ , so $8$ is a factor of $56$ .
$29 \bmod 8 = 5$ .
Remainder $5$ .

Answer

5

12

Mistakes to avoid

Where most students lose marks on this subtopic.

Mistake 01

Leaving a negative remainder as the final answer.

Add the divisor once (or twice) until the remainder is between 0 and d - 1.

Mistake 02

Using the divisor-multiple rule backwards, from a small divisor to a bigger one.

The rule only shrinks: from divisor D to its factor d, never the other way.

Mistake 03

Applying Fermat when the divisor is not prime or shares a factor with the base.

Fermat needs a prime divisor that does not divide the base.

Mistake 04

Multiplying the full big numbers before reducing.

Reduce every number to its remainder first, then multiply the small values.

Mistake 05

Reading successive division as two separate divisions of the same number.

The second division acts on the quotient of the first, so rebuild backwards from the end.

13

Quick revision

Read this the night before the exam.

Dividend $=$ divisor $\times$ quotient $+$ remainder, and $r < d$ .
Reduce each number first, then add or multiply the remainders.
Negative remainders keep arithmetic small; add the divisor to a negative result.
$(d+1)^n \to 1$ ; $(d-1)^n \to 1$ for even $n$ , $d-1$ for odd $n$ .
New divisor divides the old: answer is old remainder mod new divisor.
Successive division: rebuild from the last divisor backwards.
Factorials from $5!$ on are multiples of $15$ , so early terms alone decide.

14

Practice: 17 questions

Sets of 10, mixed across the question types above. Every answer has a step-by-step explanation.

Topic test · 10 questions

Suggested time 6 min · wrong answers go to your mistake notebook automatically.