# Concept: Remainders

CONTENTS

INTRODUCTION

Remainder means something which is ‘left over’ or ‘remaining’.

If you have 11 chocolates and you share it equally amongst your four friends. How many chocolates will remain not shared?
If you give two chocolates each to your friends, you would have shared 8 chocolates. 3 chocolates will remain with you, and this leftover of 3 chocolates is called the remainder.

Mathematically we can write the above expression as:
11 ÷ 4 = 2 remainder 3 or
11 = 4 × 2 + 3
Where 11 is the dividend, 4 is the divisor, 2 is the quotient, and 3 is the remainder.

On dividing 25 by 7. We get 3 equal parts of 7 each, that add up to 21
3 x 7 = 21
We are left with 4. This 4 is the remainder.
⇒ 25 = 7 × 3 + 4

REMAINDER THEOREM

Remember:
• Remainder of sum of two numbers is same as the sum of their individual remainders.
• Remainder of product of two numbers is same as the product of their individual remainders.

$\mathrm{R}\left[\frac{{\mathrm{N}}_{1}+{\mathrm{N}}_{2}}{\mathrm{d}}\right]$ = $\mathrm{R}\left[\frac{{\mathrm{N}}_{1}}{\mathrm{d}}\right]$ + $\mathrm{R}\left[\frac{{\mathrm{N}}_{2}}{\mathrm{d}}\right]$

$\mathrm{R}\left[\frac{{\mathrm{N}}_{1}×{\mathrm{N}}_{2}}{\mathrm{d}}\right]$ = $\mathrm{R}\left[\frac{{\mathrm{N}}_{1}}{\mathrm{d}}\right]$ × $\mathrm{R}\left[\frac{{\mathrm{N}}_{2}}{\mathrm{d}}\right]$

Note: In case sum / product of remainders is greater than or equal to the divisor, then we can get the final remainder by again dividing by the divisor.

Example: Find the remainder when 37 × 48 is divided by 5

Solution:

$\mathrm{R}\left[\frac{37×48}{5}\right]$ = $\mathrm{R}\left[\frac{37}{5}\right]$ × $\mathrm{R}\left[\frac{48}{5}\right]$ = 2 × 3 = 6

Since 6 ≥ 5, we can get the final remainder by finding the remainder of 6 with 5.

$\mathrm{R}\left[\frac{6}{5}\right]$ = 1

Note$\mathrm{R}\left[\frac{37×48}{5}\right]$ = $\mathrm{R}\left[\frac{1776}{5}\right]$ = 1

CYCLICITY OF REMAINDERS

Example: Find the remainder when 2100 is divided by 5

Solution:
Let us check remainders of various powers of 2 when divided by 5.

$\mathrm{R}\left[\frac{{2}^{1}}{5}\right]$ = 2

$\mathrm{R}\left[\frac{{2}^{2}}{5}\right]$ = 4
$\mathrm{R}\left[\frac{{2}^{3}}{5}\right]$ = 3
$\mathrm{R}\left[\frac{{2}^{4}}{5}\right]$ = 1
$\mathrm{R}\left[\frac{{2}^{5}}{5}\right]$ = 2
$\mathrm{R}\left[\frac{{2}^{6}}{5}\right]$ = 4
$\mathrm{R}\left[\frac{{2}^{7}}{5}\right]$ = 3
$\mathrm{R}\left[\frac{{2}^{8}}{5}\right]$ = 1

We see that remainders follow a cyclic pattern which repeats after every 4 powers of 2.

$\mathrm{R}\left[\frac{{2}^{4k}}{5}\right]$ = $\mathrm{R}\left[\frac{{2}^{4}}{5}\right]$ = 1
$\mathrm{R}\left[\frac{{2}^{4k+1}}{5}\right]$ = $\mathrm{R}\left[\frac{{2}^{1}}{5}\right]$ = 2
$\mathrm{R}\left[\frac{{2}^{4k+2}}{5}\right]$ = $\mathrm{R}\left[\frac{{2}^{2}}{5}\right]$ = 4
$\mathrm{R}\left[\frac{{2}^{4k+3}}{5}\right]$ = $\mathrm{R}\left[\frac{{2}^{3}}{5}\right]$ = 3

$\mathrm{R}\left[\frac{{2}^{100}}{5}\right]$ = $\mathrm{R}\left[\frac{{2}^{4*25}}{5}\right]$ = 1

Example: Find the remainder when 12100 is divided by 5

Solution:
$\mathrm{R}\left[\frac{{12}^{100}}{5}\right]$ = $\mathrm{R}\left[\frac{12}{5}\right]$ × $\mathrm{R}\left[\frac{12}{5}\right]$ × $\mathrm{R}\left[\frac{12}{5}\right]$ × ... × $\mathrm{R}\left[\frac{12}{5}\right]$ [100 times]

⇒ $\mathrm{R}\left[\frac{{12}^{100}}{5}\right]$ = 2 × 2 × 2 × ... × 2 [100 times] = 2100

Since 2100 is greater than the divisor 5, we again calculate the remainder of 2100 when divided by 5

∴ $\mathrm{R}\left[\frac{{12}^{100}}{5}\right]$ = $\mathrm{R}\left[\frac{{2}^{100}}{5}\right]$

Now, this question becomes same as the previous example.

∴ $\mathrm{R}\left[\frac{{12}^{100}}{5}\right]$ = $\mathrm{R}\left[\frac{{2}^{100}}{5}\right]$ = 1

Example: Find the remainder when 18111 is divided by 7

Solution:
$\mathrm{R}\left[\frac{{18}^{111}}{7}\right]$ = ${\left(\mathrm{R}\left[\frac{18}{7}\right]\right)}^{111}$

⇒ $\mathrm{R}\left[\frac{{18}^{111}}{7}\right]$ = $\mathrm{R}\left[\frac{{4}^{111}}{7}\right]$

Now, let us figure out the cyclicity of remainder of powers of 4 when divided by 7.

$\mathrm{R}\left[\frac{{4}^{1}}{7}\right]$ = 4

$\mathrm{R}\left[\frac{{4}^{2}}{7}\right]$ = 2

$\mathrm{R}\left[\frac{{4}^{3}}{7}\right]$ = 1

Remainders will repeat after this. Remainders start repeating after remainder 1 is obtained.

∴ Cyclicity is of three terms.

⇒ $\mathrm{R}\left[\frac{{4}^{3k}}{7}\right]$ = 1

⇒ $\mathrm{R}\left[\frac{{4}^{3k+1}}{7}\right]$ = 4

⇒ $\mathrm{R}\left[\frac{{4}^{3k+2}}{7}\right]$ = 2

Now, $\mathrm{R}\left[\frac{{4}^{111}}{7}\right]$ = $\mathrm{R}\left[\frac{{4}^{3×37}}{7}\right]$ = 1

∴ $\mathrm{R}\left[\frac{{18}^{111}}{7}\right]$ = $\mathrm{R}\left[\frac{{4}^{111}}{7}\right]$ = $\mathrm{R}\left[\frac{{4}^{3×37}}{7}\right]$ = 1

NEGATIVE REMAINDER

When N is divided by d, remainder will be any integer from 0 till (d - 1).

By definition, remainder cannot be negative. But in certain cases, you can assume that for your convenience. But a negative remainder in real sense means that you need to add the divisor in the negative remainder to find the real remainder.

Example: When 14 is divided by 5, remainder is 4, while the negative remainder is (4 - 5) = -1.

As discussed earlier, when N objects are divided in groups of d leaving remainder r, it means there are r objects extra. It also means that to make another complete group of d objects we need to (d - r) more objects i.e., we are short of (d - r) objects.

Example: Find the remainder when 2111 is divided by 9

Solution:
$\mathrm{R}\left[\frac{{2}^{111}}{9}\right]$

Let us figure out the cyclicity of powers of 2 when divided by 9.

⇒ $\mathrm{R}\left[\frac{{2}^{1}}{9}\right]$ = 2

⇒ $\mathrm{R}\left[\frac{{2}^{2}}{9}\right]$ = 4

⇒ $\mathrm{R}\left[\frac{{2}^{3}}{9}\right]$ = 8 or negative remainder is -1

∴ $\mathrm{R}\left[\frac{{2}^{6}}{9}\right]$ = ${\left(\mathrm{R}\left[\frac{{2}^{3}}{9}\right]\right)}^{2}$ = (-1)2 = 1

∴ The cyclicity of remainders is that of 6 terms.

⇒ $\mathrm{R}\left[\frac{{2}^{111}}{9}\right]$ = $\mathrm{R}\left[\frac{{2}^{6×18+3}}{9}\right]$ = $\mathrm{R}\left[\frac{{2}^{3}}{9}\right]$ = 8

FERMAT'S LITTLE THEOREM

Fermat's Little Theorem states that remainder of ap-1 when divided by p leaves a remainder of 1 if p is a prime number and a & p are co-prime numbers.

i.e., $\mathrm{R}\left[\frac{{\mathrm{a}}^{\mathrm{p}-1}}{\mathrm{p}}\right]$ = 1

Example: Find the remainder when 8100 is divided by 13.

Solution:

Using FLT we know, $\mathrm{R}\left[\frac{{8}^{13-1}}{13}\right]$ i.e., $\mathrm{R}\left[\frac{{8}^{12}}{13}\right]$ = 1

Now we can need to find $\mathrm{R}\left[\frac{{8}^{100}}{13}\right]$

$\mathrm{R}\left[\frac{{8}^{96+4}}{13}\right]$

$\mathrm{R}\left[\frac{{8}^{96}}{13}\right]$ × $\mathrm{R}\left[\frac{{8}^{4}}{13}\right]$

${\left(\mathrm{R}\left[\frac{{8}^{12}}{13}\right]\right)}^{8}$ × $\mathrm{R}\left[\frac{{8}^{2}}{13}\right]$ × $\mathrm{R}\left[\frac{{8}^{2}}{13}\right]$

= 1 × -1 × -1

= 1

Note: Questions based on Fermat's Theorem have not been asked in CAT in recent few years.

EULER'S THEOREM

According to Euler’s theorem, any number a raised to the power Φ(d) will leave a remainder of 1 when it is divided by d, provided d and a are co-primes.

$\mathrm{R}\left[\frac{{\mathrm{a}}^{\mathrm{\Phi }\left(\mathrm{d}\right)}}{\mathrm{d}}\right]$ = 1

Φ(d) = number of coprimes to d which are less than d.

Note: Questions based on Euler's thorem have not been asked in CAT in recent few years.

WILSON'S THEOREM

When (p - 1)! is divided by p, the remainder will be (p – 1), where p is a prime number.

$\mathrm{R}\left[\frac{\left(\mathrm{p}-1\right)!}{\mathrm{p}}\right]$ = p - 1

Example: Remainder of 16! when divided by 17 is 16.

Based on Wilson's theorem we get another rule:

When (p - 2)! is divided by p, the remainder will be 1, where p is a prime number.

$\mathrm{R}\left[\frac{\left(\mathrm{p}-2\right)!}{\mathrm{p}}\right]$ = 1

Proof:
$\mathrm{R}\left[\frac{\left(\mathrm{p}-1\right)!}{\mathrm{p}}\right]$ = p - 1

⇒ $\mathrm{R}\left[\frac{\left(\mathrm{p}-1\right)}{\mathrm{p}}\right]$ × $\mathrm{R}\left[\frac{\left(\mathrm{p}-2\right)!}{\mathrm{p}}\right]$ = (p - 1)

⇒ (p - 1) × $\mathrm{R}\left[\frac{\left(\mathrm{p}-2\right)!}{\mathrm{p}}\right]$ = (p - 1)

∴ $\mathrm{R}\left[\frac{\left(\mathrm{p}-2\right)!}{\mathrm{p}}\right]$ = 1

Note: Questions based on Wilson's thorem have not been asked in CAT in recent few years.

## Feedback

Help us build a Free and Comprehensive Preparation portal for various competitive exams by providing us your valuable feedback about Apti4All and how it can be improved.