Remainder Theorems

Concept of Remainder

If a number A is divided by B, then A is the dividend and B is the divisor. There are two possibilities:

• Either a remainder is left
• Or No remainder is left, i.e. Remainder = 0 (means it completely divides)

Let’s see both of these cases in more detail.

Remainder is left

Here, Dividend = Divisor × Quotient + Remainder

In other words if on dividing A by B, we get a remainder of r, then we can write A as follows:
A = qB + r
(where q is the quotient, which is a whole number, i.e. it’s value can be 0, 1, 2, 3 ….)

E.g. a number when divided by 5 leaves a remainder of 2, can be written as (5q + 2)

No remainder is left

Here, Dividend = Divisor × Quotient

If remainder is zero, then:
A = qB

E.g. a number which is completely divisible by 5, i.e. a number which is a multiple of 5, can be written as 5q

Properties of remainders

Addition and Remainders

If two dividends A and B, when divided by a divisor Z, leaves remainders $r_1$ and $r_2$ respectively, then
the remainder when A + B is divided by Z is $r_1 + r_2$.

E.g. Remainder [$\frac{18}{5}$] = 3 and Remainder [$\frac{31}{5}$] = 1

∴ Remainder [$\frac{18 + 31}{5}$] = 3 + 1 = 4

Subtraction and Remainders

If two dividends A and B, when divided by a divisor Z, leaves remainders $r_1$ and $r_2$ respectively, then
the remainder when A - B is divided by Z is $r_1 - r_2$.

E.g. Remainder [$\frac{17}{5}$] = 2 and Remainder [$\frac{34}{5}$] = 4

∴ Remainder [$\frac{34 - 17}{5}$] = 4 - 2 = 2

Multiplication and Remainders

If two dividends A and B, when divided by a divisor Z, leaves remainders $r_1$ and $r_2$ respectively, then
the remainder when A × B is divided by Z is $r_1 × r_2$.

E.g. Remainder [$\frac{18}{5}$] = 3 and Remainder [$\frac{31}{5}$] = 1

∴ Remainder [$\frac{31 × 18}{5}$] = 1 × 3 = 3

Powers/Exponents and Remainders

If a dividend A on division by a divisor Z, leaves a remainder r, then
the remainder when An is divided by Z is $r^n$.

E.g. Remainder [$\frac{17}{5}$] = 2

∴ Remainder [$\frac{17^2}{5}$] = $2^2$ = 4

E.g. Remainder [$\frac{18}{5}$] = 3

∴ Remainder [$\frac{18^3}{5}$] = $3^3$ = 27 = 2

(27 is more than 5, so we divided 27 by 5 again and got the remainder 2.)

Concept of Negative Remainder

Remainder can be zero or some positive number less than the divisor. It can never be negative.

But sometimes we encounter negative remainders. Let’s see what they mean and how to handle them with the help of an example.

If 11 is the number being divided and 3 is the divisor, then we can write 11 as:
11 = 3 × 3 + 2 (here 2 is the remainder)
Or 11 = 3 × 4 – 1 (here -1 is the remainder)

Hence -1 is the corresponding negative remainder of the original remainder 2, when the divisor is 3.

To convert any negative remainder into non-negative remainder, just add the divisor to it.
So, original non-negative remainder = negative remainder + divisor = -1 + 3 = 2

Let us generalize this concept:

If two dividends A and B, when divided by a divisor Z, leaves remainders $r_1$ and $r_2$ respectively, then
the remainder when A - B is divided by Z is $r_1 - r_2$.

Let’s have a look at one more example:

Remainder [$\frac{23}{4}$] = 3 and Remainder [$\frac{41}{4}$] = 1

∴ Remainder [$\frac{41 - 23}{4}$] = 1 - 3 = -2

So, original non-negative remainder = negative remainder + divisor = -2 + 4 = 2

Finding remainder of an expression

There are two methods to find out the remainder of any expression.

• Cyclicity Method / Pattern Method
• Remainder Theorem method

Cyclicity method / Pattern Method

We saw earlier that the last digit of the powers of a number repeat in a certain pattern. Similarly, the remainders of powers of a number also follow a certain pattern of repetition. If we can identify this pattern, we can find out the remainder of any given division.

Let us find the pattern that remainders follow when various powers of 2 are divided by 5.

Remainder [$\frac{2}{5}$] = 2

Remainder [$\frac{2^2}{5}$] = 4

Remainder [$\frac{2^3}{5}$] = 3

Remainder [$\frac{2^4}{5}$] = 1

Remainder [$\frac{2^5}{5}$] = 2

Remainder [$\frac{2^6}{5}$] = 4

So, we can see the pattern of repetition: 2, 4, 3, 1 (here remainder repeats in a cycle of 4)

So, how can we use this information. Let’s see.

We know that the cyclicity when 2 is divided by 5 is 4.

It means that if the exponent of 2 is any multiple of 4, then the remainder should be 1. So, if the exponent is in the form:
4k + 0, then remainder is 1
4k + 1, then remainder is 2
4k + 2, then remainder is 4
4k + 3, then remainder is 3
(where k is any whole number, k = 0, 1, 2, 3…)

If we have to find the remainder when $2^{34}$ is divided by 5, we just need to divide 34 by 4 (cyclicity when 2 is divided by 5). The remainder we get is 2 (i.e. 4k + 2).
It means that $2^{34}$ will give the same remainder as $2^2$, i.e. 4.

Remainder Theorem Method

Let p(x) be a polynomial in x.
If p(x) is divided by (x − a). then the remainder will be p(a).

For example, if $x^2 + 3x + 5$ is divided by x – 2, the remainder will be:
f (2) = $2^2$ + (3 × 2) + 5 = 15

If $x^2 + 3x + 5$ is divided by x + 2, the remainder will be:
f (-2) = $(-2)^2$ + (3 × -2) + 5 = 3

Earlier we used the Pattern method to find the remainder when $2^{34}$ is divided by 5. Let us solve it using Remainder Theorem Method.

Since the numerator (i.e. dividend) is in terms of powers of 2, we need to express the denominator also in terms of powers of 2. We can write 5 as 4 + 1 = $2^2$ + 1.
Now we need to write the numerator in terms of $2^2 × 2^{34}$ = $(2^2)^{17}$
Let $2^2$ be x.
So, basically we need to find the remainder when $x^{17}$ is divided by (x + 1).
As per the remainder theorem, the required remainder = f (-1) = $(-1)^{17}$ = -1 = -1 + 5 = 4

Remainder Theorem Method Vs. Pattern Method

We can use the remainder theorem in cases where the denominator (i.e., the divisor) can be written in the form of one more or one less than some power of the base in the numerator.

For example:
In case of $\frac{2^{24}}{3}$, $\frac{2^{24}}{5}$ and $\frac{2^{24}}{7}$, the base in the numerator is 2.

$\frac{2^{24}}{3}$ – here the denominator can be written as 2 + 1

$\frac{2^{24}}{5}$ - here the denominator can be written as $2^2$ + 1

$\frac{2^{24}}{7}$ – here the denominator can be written as $2^3$ - 1

In cases where it is not possible to write the denominator and numerator in this manner, we should rather apply the Pattern Method (rather than the remainder theorem method).

Generalizations based on Remainder Theorem

Generalization 1

$\frac{(p + 1)^n}{p}$ will always give 1 as the remainder for all natural values of p and n.

Generalization 2

$\frac{p^n}{(p + 1)}$ will always give 1 as the remainder, when n is even.

Generalization 3

$\frac{p^n}{(p + 1)}$ will always give p as the remainder, when n is odd.

Remainder properties of Prime numbers

Property 1

For any prime p>3, $p^2$ − 1 is a multiple of 24.

E.g. if p = 5, then $5^2$ − 1 = 24 If p = 11, then $11^2$ − 1 = 120 (a multiple of 24)

Property 2: Fermat’s theorem

Let ‘x’ and ‘y’ be any two prime numbers.

Then $x^y$ − x is always divisible by y.

E.g. $2^3$ − 2 = 6 is divisible by 3.
$2^5$ − 2 = 30 is divisible by 5.
$3^3$ − 3 = 24 is divisible by 3.

Property 3: Fermat’s little theorem

Let ‘x’ and ‘y’ be any two relatively prime numbers (where ‘y’ is a prime number)

Then Remainder [$\frac{x^{y - 1}}{y}$] is 1.

E.g. if x = 10 and y = 7
Remainder [$\frac{10^6}{7}$] = 1

Let us double check it.
Remainder [$\frac{10^6}{7}$] = Remainder [$\frac{3^6}{7}$] = Remainder [$\frac{9^3}{7}$] = Remainder [$\frac{2^3}{7}$] = Remainder [$\frac{8}{7}$] = 1

Property 4: Wilson’s theorem

Let ‘p’ be a prime number, then:

Remainder [$\frac{(p − 1)!}{p}$] is (p − 1).

Remainder [$\frac{(p − 1)! + 1}{p}$] is always zero.

E.g. Let p = 5, then:

Remainder [$\frac{(5 − 1)!}{5}$], i.e. Remainder [$\frac{4!}{5}$] is (5 − 1) = 4.

Remainder [$\frac{(5 − 1)! + 1}{5}$], i.e. Remainder [$\frac{4! + 1}{5}$] is zero.

Remainder properties of Composite numbers

Property 1: Wilson’s theorem

If n is a composite number more than 4, then (n - 1)! will be divisible by n.

E.g. if n = 6, then (6 – 1)! = 5! = 120 is divisible by 6.
If n = 8, then (8 – 1)! = 7! = 5040 is divisible by 8.