Proof Of Divisibility Rules | Brilliant Math & Science Wiki (2024)

Main article: Divisibility Rules

Divisibility rules are efficient shortcut methods to check whether a given number is completely divisible by another number or not. These divisibility tests, though initially made only for the set of natural numbers \((\mathbb N),\) can be applied to the set of all integers \((\mathbb Z)\) as well if we just ignore the signs and employ 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 can we be so sure 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.

• Divisibility by 1: Every number is divisible by \(1\).
• Divisibility by 2: The number should have \(0, \ 2, \ 4, \ 6,\) or \(8\) as the units digit.
• Divisibility by 3: The sum of digits of the number must be divisible by \(3\).
• Divisibility by 4: The number formed by the tens and units digit of the number must be divisible by \(4\).
• Divisibility by 5: The number should have \(0\) or \(5\) as the units digit.
• Divisibility by 6: The number should be divisible by both \(2\) and \(3\).
• Divisibility by 7: The absolute difference between twice the units digit and the number formed by the rest of the digits must be divisible by \(7\) (this process can be repeated for many times until we arrive at a sufficiently small number).
• Divisibility by 8: The number formed by the hundreds, tens and units 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 units 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 units digits with the number formed by the rest of the digits must be divisible by \(13\) (this process can be repeated for many times until we arrive at a sufficiently small number).
• Divisibility by 25: The number formed by the tens and units digit of the number must be divisible by \(25\).
• Divisibility by 125: The number formed by the hundreds, tens and units digit of the number must be divisible by \(125\).

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

\[ N = \overline {a_n a_{n-1} a_{n-2} \ldots 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.\]

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

See Also

The IOC says the Olympic Games has reached gender parity, but historic gender inequality still lingers | CNNLong Division CalculatorDivisible - Definition, Chart, Rules of Divisibility 1 to 13Divisible - Definition, Chart, Rules of Divisibility 1 to 13

Prove that 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 mod 2 of \(N,\) we get

\[\begin{align} N & \equiv 0+0+0+ \cdots +0+0+ a_0 \pmod{2} \qquad \big(\text{as } 10^k, \text{ where } k \ge 1, \text{ is always divisible by } 2\big)\\& \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 this condition are \(0, 2, 4, 6,\) and \(8\). \(_\square\)

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\).

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

Prove that 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 mod 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} \qquad \big(\text{as } 10^k-1, \text{ where } k \ge 1, \text{ is always divisible by } 3\big)\\ \\\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\). \(_\square\)

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\).

Any number whose digits in the tens and units places taken in that order are divisible by \(4\) is itself also divisible by \(4\).

Prove that 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 mod 4 of \(N,\) we get

\[\begin{align} N & \equiv 0+0+0+ \cdots +0+10 a_1+ a_0 \pmod{4} \qquad \big(\text{as } 10^k, \text{ where } k \ge 2, \text{ is always divisible by } 4\big) \\ & \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, if the tens and units places of a number taken in that order are divisible by \(4,\) then the number is also divisible by \(4\). \(_\square\)

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 is divisible by \(25\), then the number is also divisible by \(25\).

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

Prove that the number \(678\) is divisible by \(6\) because \(678\) is divisible by both \(2\) and \(3\).

This doesn't require any detailed proof other than 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 coprime numbers. \(_\square\)

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

Prove that 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\]

for some integer \(k.\) Then

\[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 LHS to get

\[\begin{align}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\\&= 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\\ 7k - 21 a_0 &=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}\\\\\Rightarrow 10 \left( \overline{a_n a_{n-1} a_{n-2} \ldots a_2 a_1} - 2 a_0 \right) &\equiv 0 \pmod{7}.\end{align}\]

Therefore, since \(10 \equiv 3 \pmod{7},\) for \(N\) to be divisible by \(7,\) it must be true that \(\overline{a_n a_{n-1} a_{n-2} \ldots 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\). \(_\square\)

Any number whose digits in the hundreds, tens, and units places taken in that order are divisible by \(8\) is itself also divisible by \(8.\)

Prove that 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 mod 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 \big(\text{as } 10^k, \text{ where } k \ge 3, \text{ is always divisible by } 8\big) \\ & \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, if the hundreds, tens, and units places of a number taken in that order are divisible by \(8,\) then the number is also divisible by \(8\). \(_\square\)

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 places of a number taken in that order are divisible by \(125\), then the number is also divisible by \(125\).

Any number whose absolute difference between the sum of digits in the even positions and the sum of digits in the odd positions is \(0\) or divisible by \(11\) is itself also divisible by \(11\).

Prove that the number \(105204\) is divisible by \(11\) because \(\big|(0+2+4)-(1+5+0)\big|=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 mod 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 \big(\text{as } 10^k \equiv +1 \bmod{11} \text{ if } k \text{ is even, and } 10^k \equiv -1 \bmod{11} \text{ if } k \text{ is odd}\big)\]

• Suppose \(n\) is even, then we have\[\begin{align}N &\equiv a_n - a_{n-1} + a_{n-2} - \cdots + a_2 - a_1 + a_0 \pmod{11} \\ &\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}.\end{align}\]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\[\begin{align}N &\equiv -a_n + a_{n-1} - a_{n-2} + \cdots + a_2 - a_1 + a_0 \pmod{11} \\&\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}.\end{align}\]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 between 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\). \(_\square\)

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

Prove that 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 than 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 coprime numbers. \(_\square\)

Any number whose sum of four times the units digit and the number formed by the rest of the digits is divisible by \(13\) is itself 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\]

for some integer \(k.\) Then

\[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 LHS to get

\[\begin{align}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\\&=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\\13k + 39 a_0&= 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}\\\\\Rightarrow 10 \left( \overline{a_n a_{n-1} a_{n-2} \ldots a_2 a_1} + 4 a_0 \right) &\equiv 0 \pmod{13}.\end{align}\]

Therefore, since \(10 \equiv 10 \pmod{13}\), for \(N\) to be divisible by \(13\), it must be true that \(\overline{a_n a_{n-1} a_{n-2} \ldots a_2 a_1} + 4 a_0 \equiv 0 \pmod{13}\).

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

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

• SAT Math: Factors, Divisibility and Remainders
• Application of Divisibility Rules
• Divisibility Rules