# Proof Of Divisibility Rules

Main article: Divisibility Rules

*Divisibility rules* are efficient short-cut methods to check whether a given number is completely divisible by another number or not. These divisibility tests, though were initially made only for the set of natural numbers \((\mathbb N)\) but they can be applied to the set of all integers \((\mathbb Z)\) as well if we just ignore the signs and imply our divisibility rules. Note that the term 'complete divisibility' means that one of the numbers with the smaller magnitude must be a divisor of the one with the greater magnitude.

But from where do these divisibility rules come from? How are we so sure about it that it will work for every integer? Let us unveil the answers to all these questions as we explore the underlying principles behind this set of rules based on deductive reasoning and our knowledge of modular arithmetic.

#### Contents

- Divisibility Rules for some selected integers
- Proofs
- Divisibility by 2 (similar for 5 and 10)
- Divisibility by 3 (similar for 9)
- Divisibility by 4 (similar for 25)
- Divisibility by 6
- Divisibility by 7
- Divisibility by 8 (similar for 125)
- Divisibility by 11
- Divisibility by 12
- Divisibility by 13
- See also

## Divisibility Rules for some selected integers

**Divisibility by 1:**Every number is divisible by \(1\).**Divisibility by 2:**The number should have \(0, \ 2, \ 4, \ 6,\) or \(8\) as the unit's digit.**Divisibility by 3:**The sum of digits of the number must be divisible by \(3\).**Divisibility by 4:**The number formed by the ten's and unit's digit of the number must be divisible by \(4\).**Divisibility by 5:**The number should have \(0\) or \(5\) as the unit's digit.**Divisibility by 6:**The number should be divisible by both \(2\) and \(3\).**Divisibility by 7:**The absolute difference between twice the unit's digit and the number formed by the rest of the digits must be divisible by \(7\) (process can be repeated for many times until we don't arrive at a sufficiently small number).**Divisibility by 8:**The number formed by the hundred's, ten's and unit's digit of the number must be divisible by \(8\).**Divisibility by 9:**The sum of digits of the number must be divisible by \(9\).**Divisibility by 10:**The number should have \(0\) as the unit's digit.**Divisibility by 11:**The absolute difference between the sum of alternate pairs of digits must be divisible by \(11\).**Divisibility by 12:**The number should be divisible by both \(3\) and \(4\).**Divisibility by 13:**The sum of four times the unit's digits with the number formed by the rest of the digits must be divisible by \(13\) (process can be repeated for many times until we don't arrive at a sufficiently small number).**Divisibility by 25:**The number formed by the ten's and unit's digit of the number must be divisible by \(25\).**Divisibility by 125:**The number formed by the hundred's, ten's and unit's digit of the number must be divisible by \(125\).

## Proofs

Now, we will be discussing the derivations of these rules. In every proof, the variable will take the form

\[\large N = \overline {a_n a_{n-1} a_{n-2} \cdots a_2 a_1 a_0}\]

\[\text{OR}\]

\[N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0\]

## Divisibility by 2 (similar for 5 and 10)

Any number with \(2, \ 4, \ 6, \ 8\) and \(0\) as the unit digit is divisible by \(2\).

The number \(506\) is divisible by \(2\) because \(6\) is divisible by \(2\).

We have,

\(N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 \)

Taking \(\pmod{2}\) of \(N\) we get,

\(\begin{align} N & \equiv 0+0+0+ \cdots +0+0+ a_0 \pmod{2} \qquad \qquad \qquad \small \color{blue}{\text{As} \ 10^k \ \text{where} \ k \ge 1 \ \text{is always divisible by} \ 2} \\ N & \equiv a_0 \pmod{2} \end{align}\)

Therefore, \(N \equiv 0 \pmod{2}\) if \(a_0 \equiv 0 \pmod{2}\).

Since, \(a_0\) is a single digit number. The only values that satisfy are \(0, \ 2, \ 4, \ 6\) and \(8\).

The same approach can be used for \(5\) and \(10\) as well due to the fact that \(10^k\) where \(k \ge 1\) is always divisible by \(5\) and \(10\) as well and hence, the values fitting for \(a_0\) in this case are \(0\) and \(5\) for the number \(5\) and \(0\) for the number \(10\), thus proving the divisibility tests of \(5\) and \(10\).\[ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}\]

## Divisibility by 3 (similar for 9)

Any number whose sum of digits is divisible by \(3\) is also divisible by \(3\).

The number \(168\) is divisible by \(3\) because \((1+6+8)=15\) is divisible by \(3\).

We have,

\(N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 \)

Taking \(\pmod{3}\) of \(N\) we get,

\(\begin{align} N & \equiv 1 \times a_n\pmod{3} + 1 \times a_{n-1}\pmod{3} + 1 \times a_{n-2}\pmod{3} + \cdots + 1 \times a_2\pmod{3} + 1 \times a_1\pmod{3} + 1 \times a_0\pmod{3} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \small \color{blue}{\text{As} \ 10^k-1 \ \text{where} \ k \ge 1 \ \text{is always divisible by} \ 3} \\ & \equiv \left( a_n + a_{n-1} + a_{n-2} + \cdots + a_2 + a_1 + a_0 \right) \pmod{3} \end{align}\)

Therefore, \(N \equiv 0 \pmod{3}\) if \( a_n + a_{n-1} + a_{n-2} + \cdots + a_2 + a_1 + a_0 \equiv 0 \pmod{3}\).

Thus, the sum of digits must be divisible by \(3\) for the number to be divisible by \(3\).

The same approach can be used for \(9\) as well due to the fact that \(10^k - 1\) where \(k \ge 1\) is always divisible by \(9\) as well and hence, the sum of digits of the number in this case must be divisible by \(9\) so that the number itself is divisible by \(9\), thus proving the divisibility test of \(9\).\[ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}\]

## Divisibility by 4 (similar for 25)

Any number whose digits in the tens and units place taken in that order respectively, if divisible by \(4\), then the number is also divisible by \(4\).

The number \(11564\) is divisible by \(4\) because \(64\) is divisible by \(4\).

We have,

\(N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 \)

Taking \(\pmod{4}\) of \(N\) we get,

\(\begin{align} N & \equiv 0+0+0+ \cdots +0+10 a_1+ a_0 \pmod{4} \qquad \qquad \qquad \small \color{blue}{\text{As} \ 10^k \ \text{where} \ k \ge 2 \ \text{is always divisible by} \ 4} \\ N & \equiv 10 a_1 + a_0 \pmod{4} \end{align}\)

Therefore, \(N \equiv 0 \pmod{4}\) if \(10a_1 + a_0 = \overline {a_1 a_0} \equiv 0 \pmod{4}\).

Thus, the if the tens and units place of a number taken in that order is divisible by \(4\) then the number is also divisible by \(4\).

The same approach can be used for \(25\) as well due to the fact that \(10^k\) where \(k \ge 2\) is always divisible by \(25\) as well and hence, if the digits in the tens and units place of a number taken in that order respectively, if divisible by \(25\), then the number is also divisible by \(25\).\[ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{Q.E.D.}\]

## Divisibility by 6

Any number which is divisible by \(2\) and \(3\) both is also divisible by \(6\) as well.

The number \(678\) is divisible by \(6\) because \(678\) is divisible by both \(2\) and \(3\).

This doesn't require any detailed proof other that the fact that if

\(N \equiv 0 \pmod{2}\) and \(N \equiv 0 \pmod{3}\), then \(N \equiv 0 \pmod{2 \times 3 = 6}\). As \(2\) and \(3\) are co-prime numbers.

## Divisibility by 7

Any number whose absolute difference between twice the units digit and the number formed by the rest of the digits, if it is \(0\) or divisible by \(7\), then the number is also divisible by \(7\).

The number \(343\) is divisible by \(7\) because \(34 - 2 \times 3 = 28\) is also divisible by \(7\).

We have,

\(N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 \)

Let,

\(N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 = 7k \qquad \quad \small \color{blue}{\text{for some integer} \ k}\)

\(N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 \right) + a_0 = 7k\)

Add and subtract \(20 a_0\) on the L.H.S. to get,

\(N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 \right) + 20 a_0 - 20 a_0 + a_0 = 7k\)

\(N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 - 2 a_0 \right) + 21 a_0 = 7k\)

\(N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 - 2 a_0 \right) = 7k - 21 a_0 \)

\(N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 - 2 a_0 \right) \equiv 0 \pmod{7}\)

\(N = 10 \left( \overline{a_n a_{n-1} a_{n-2} \cdots a_2 a_1} - 2 a_0 \right) \equiv 0 \pmod{7}\)

Since, \(10 \equiv 3 \pmod{7}\), therefore, for \(N\) to be divisible by \(7\), \(\overline{a_n a_{n-1} a_{n-2} \cdots a_2 a_1} - 2 a_0 \equiv 0 \pmod{7}\).

Thus, for a number if the absolute difference between twice the units digit and the number formed by the rest of the digits, is \(0\) or divisible by \(7\), then that number is also divisible by \(7\).

## Divisibility by 8 (similar for 125)

Any number whose digits in the hundreds, tens and units place taken in that order respectively, if divisible by \(8\), then the number is also divisible by \(8\).

The number \(74152\) is divisible by \(8\) because \(152\) is divisible by \(8\).

We have,

\(N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 \)

Taking \(\pmod{8}\) of \(N\) we get,

\(\begin{align} N & \equiv 0+0+0+ \cdots +10^2 a_2+10 a_1+ a_0 \pmod{8} \qquad \qquad \qquad \small \color{blue}{\text{As} \ 10^k \ \text{where} \ k \ge 3 \ \text{is always divisible by} \ 8} \\ N & \equiv 100 a_2 + 10 a_1 + a_0 \pmod{8} \end{align}\)

Therefore, \(N \equiv 0 \pmod{8}\) if \(100 a_2 + 10a_1 + a_0 = \overline {a_2 a_1 a_0} \equiv 0 \pmod{8}\).

Thus, the if the hundreds, tens and units place of a number taken in that order is divisible by \(8\) then the number is also divisible by \(8\).

The same approach can be used for \(125\) as well due to the fact that \(10^k\) where \(k \ge 3\) is always divisible by \(125\) as well and hence, if the digits in the hundreds, tens and units place of a number taken in that order respectively, if divisible by \(125\), then the number is also divisible by \(125\).

## Divisibility by 11

Any number whose absolute difference of the sum of digits occurring in the even positions and the sum of digits occurring in odd positions, if it is \(0\) or divisible by \(11\), then the number is also divisible by \(11\).

The number \(105204\) is divisible by \(11\) because \(\left|(0+2+4)-(1+5+0)\right|=0\) is divisible by \(11\).

We have,

\(N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 \)

Taking \(\pmod{11}\) of \(N\) we get,

\(N \equiv \pm a_n \mp a_{n-1} \pm a_{n-2} \cdots \mp a_2 \pm a_1 \mp a_0 \pmod{11} \qquad \qquad \small \color{blue}{\text{As} \ 10^k \equiv +1 \pmod{11} \ \text{if} \ k \ \text{is even and} \ 10^k \equiv -1 \pmod{11} \ \text{if} \ k \ \text{is odd}}\)

- Suppose \(n\) is even, then we have:
\(N \equiv a_n - a_{n-1} + a_{n-2} - \cdots + a_2 - a_1 + a_0 \pmod{11} \\ N \equiv \left( a_n + a_{n-2} + \cdots + a_2 + a_0 \right) - \left( a_{n-1} + a_{n-3} + \cdots + a_3 + a_1 \right) \pmod{11}\)

Therefore, \(N \equiv 0 \pmod{11}\) if \(\left( a_n + a_{n-2} + \cdots + a_2 + a_0 \right) - \left( a_{n-1} + a_{n-3} + \cdots + a_3 + a_1 \right) \equiv 0 \pmod{11}\), given that \(n\) is even.

- Suppose \(n\) is odd, then we have:
\(N \equiv -a_n + a_{n-1} - a_{n-2} + \cdots + a_2 - a_1 + a_0 \pmod{11} \\ N \equiv \left( a_{n-1} + a_{n-3} + \cdots + a_2 + a_0 \right) - \left( a_n + a_{n-2} + \cdots + a_3 + a_1 \right) \pmod{11}\)

Therefore, \(N \equiv 0 \pmod{11}\) if \(\left( a_{n-1} + a_{n-3} + \cdots + a_2 + a_0 \right) - \left( a_n + a_{n-2} + \cdots + a_3 + a_1 \right) \equiv 0 \pmod{11}\), given that \(n\) is odd.

From the above two conditions, we infer that for a number to be divisible by \(11\), its absolute difference of the sum of digits occurring in the even positions and the sum of digits occurring in odd positions, should be \(0\) or divisible by \(11\).

## Divisibility by 12

Any number which is divisible by \(3\) and \(4\) both is also divisible by \(12\) as well.

The number \(1092\) is divisible by \(12\) because \(1092\) is divisible by both \(3\) and \(4\).

This also doesn't require any detailed proof other that the fact that if

\(N \equiv 0 \pmod{3}\) and \(N \equiv 0 \pmod{4}\), then \(N \equiv 0 \pmod{3 \times 4 = 12}\). As \(3\) and \(4\) are co-prime numbers.

## Divisibility by 13

Any number whose sum of four times the units digit and the number formed by the rest of the digits, if it is divisible by \(13\), then the number is also divisible by \(13\).

The number \(169\) is divisible by \(13\) because \(16 + 4 \times 9 = 52\) is also divisible by \(13\).

We have,

\(N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 \)

Let,

\(N = 10^n a_n + 10^{n-1} a_{n-1} + 10^{n-2} a_{n-2} + \cdots + 10^2 a_2 + 10 a_1 + a_0 = 13k \qquad \quad \small \color{blue}{\text{for some integer} \ k}\)

\(N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 \right) + a_0 = 13k\)

Add and subtract \(40 a_0\) on the L.H.S. to get,

\(N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 \right) + 40 a_0 - 40 a_0 + a_0 = 13k\)

\(N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 + 4 a_0 \right) - 39 a_0 = 13k\)

\(N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 + 4 a_0 \right) = 13k + 39 a_0 \)

\(N = 10 \left( 10^{n-1} a_n + 10^{n-2} a_{n-1} + 10^{n-3} a_{n-2} + \cdots + 10 a_2 + a_1 + 4 a_0 \right) \equiv 0 \pmod{13}\)

\(N = 10 \left( \overline{a_n a_{n-1} a_{n-2} \cdots a_2 a_1} + 4 a_0 \right) \equiv 0 \pmod{13}\)

Since, \(10 \equiv 10 \pmod{13}\), therefore, for \(N\) to be divisible by \(13\), \(\overline{a_n a_{n-1} a_{n-2} \cdots a_2 a_1} + 4 a_0 \equiv 0 \pmod{13}\).

Thus, for a number if the sum of four times the units digit and the number formed by the rest of the digits, is divisible by \(13\), then that number is also divisible by \(13\).

Based on the similar logical approach, a divisibility test can be made for each and every number by just observing their pattern over successive powers of \(10\).

## See also

**Cite as:**Proof Of Divisibility Rules.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/proof-of-divisibility-rules/