## Divisibility

We studied divisibility rules in secondary school. In this lesson, we will examine the basis behind these rules. This involves application of two vital concepts from Number Theory and Factors and Remainders lessons. These concepts are restated below. We will also look at concepts related to last digit and factorial.

### 1. Revisiting Basics

#### 1.1 Decimal Number System

Numbers are used to measure and count. The number system used globally is the decimal number system, where the base is $10$. This just means that there are $10$ digits in this number system. They are $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$.

In this number system, the placement of digits in a number creates the value for that number. In this lesson, we will be working with positive integers (or natural numbers) only.

From right to left, the places before the decimal points are units' place, tens' place, hundreds' place, thousands' place, etc. Each of these places have a certain value attached to it. They start with $10^{0}$ and increase with increments of 1 in the power. The table below shows till the seventh digit from the right.

Position (Right to Left) Value
Units' Place $10^{0}$
Tens' Place $10^{1}$
Hundreds' Place $10^{2}$
Thousands' Place $10^{3}$
Ten Thousands' Place $10^{4}$
Hundred Thousands' Place $10^{5}$
Millions' Place $10^{6}$

∴ The number $25,678$ means there are $2$ of $10^{4}, 5$ of $10^{3}, 6$ of $10^{2}, 7$ of $10^{1}$ and $8$ of $10^{0}$.

$2567 = (2 \times 10^{4}) + (5 \times 10^{3}) + (6 \times 10^{2}) + (7 \times 10^{1}) + (8 \times 10^{0})$

This forms the value of every number in the decimal system. The following is an example for a relatively larger number.

$5305680 = (5 \times 10^{6}) + (3 \times 10^{5}) + (0 \times 10^{4}) + (5 \times 10^{3}) + (6 \times 10^{2}) + (8 \times 10^{1}) + (0 \times 10^{0})$

We can also merge some of the places. For instance, the above number can also be expressed as
$5305680 = (5380 \times 10^{4}) + (5680 \times 10^{0})$ or $5305680 = (5 \times 10^{6}) + (305 \times 10^{3}) + (680 \times 10^{0})$

#### 1.2 Remainder rules

Sum Rule: Remainder of Sum of numbers = Sum of remainders when each of the numbers is divided by the divisor

When $n = a_{1} + a_{2} + a_{3} + ...,$

$\text{Rem} \left(\dfrac{n}{d} \right)$ $= \text{Rem} \left(\dfrac{a_{1} + a_{2} + a_{3} + ...}{d} \right)$ $= \text{Rem} \left(\dfrac{a_{1}}{d} \right)$ $+ \text{Rem} \left(\dfrac{a_{2}}{d} \right)$ $+ \text{Rem} \left(\dfrac{a_{3}}{d} \right) + ...$

Product Rule: Remainder of product of numbers = Product of remainders when each of the numbers is divided by the divisor

When $n = a_{1} \times a_{2} \times a_{3} \times ...,$

$\text{Rem} \left(\dfrac{n}{d} \right)$ $= \text{Rem} \left(\dfrac{a_{1} + a_{2} + a_{3} + ...}{d} \right)$ $= \text{Rem} \left(\dfrac{a_{1}}{d} \right)$ $+ \text{Rem} \left(\dfrac{a_{2}}{d} \right)$ $+ \text{Rem} \left(\dfrac{a_{3}}{d} \right) + ...$

### Example 1

What is the remainder when $34585$ is divided by $4$?

### Solution

$34585 = (3 \times 10^{4})$ $+ (4 \times 10^{3})$ $+ (5 \times 10^{2})$ $+ (8 \times 10^{1})$ $+ (5 \times 10^{0})$

$\text{Rem} \left(\dfrac{34585}{4} \right)$ $= \text{Rem} \left(\dfrac{(3 \times 10^{4}) + (4 \times 10^{3}) + (5 \times 10^{2}) + (8 \times 10^{1}) + (5 \times 10^{0})}{4} \right)$

Applying sum rule, we write this as

$= \text{Rem}\left(\dfrac{3 \times 10^{4}}{4} \right)$ $+ \text{Rem} \left(\dfrac{4 \times 10^{3}}{4} \right)$ $+ \text{Rem} \left(\dfrac{5 \times 10^{2}}{4} \right)$ $+ \text{Rem} \left(\dfrac{8 \times 10^{1}}{4} \right)$ $+ \text{Rem} \left(\dfrac{5 \times 10^{0}}{4} \right)$

If $n \ge 2, 2^{3}$ will perfectly divide $10^{n}$ and leave a remainder of $0$.
∴ Applying Product rule,

$= \text{Rem}\left(\dfrac{3 \times 0}{4} \right)$ $+ \text{Rem} \left(\dfrac{4 \times 0}{4} \right)$ $+ \text{Rem} \left(\dfrac{5 \times 0}{4} \right)$ $+ \text{Rem} \left(\dfrac{8 \times 10^{1}}{4} \right)$ $+ \text{Rem} \left(\dfrac{5 \times 10^{0}}{4} \right)$

$= \text{Rem} \left(\dfrac{80}{4}\right)$ $+ \text{Rem} \left(\dfrac{5}{4}\right)$ $= 0 + 1 = 1$

Answer: $1$

Note: This is the logic behind looking at the last two digits for divisibility by $4$.