Creating Divisibility Tests

Modulo Arithmetic : Some useful divisibility tests

Previous part

We'll use modulo arithmetic to show some famous and useful in practice divisibility tests.

Firstly, let's start with the simple powers of $2$ and $5$ :

Similarly, a number is divisible by $5^k$ if and only if the number formed by its last $k$ digits is divisible by $5^k$.

An example is $2016$ is divisible by $2^2 = 4$ if and only if $16$ is divisible by $4$, which is true.

Here's the proof of the divisibility test (we'll give it for $2^k$ only, the $5^k$ case follows analogously)

Let $n = a_m10^m + a_{m - 1}10^{m - 1} + ... + a_1(10) + a_0$.

If $m < k$, the result is clear. Thus, assume that $m \ge k$.

Then,

$n = a_m10^m + a_{m - 1}10^{m - 1} + ... + a_1(10) + a_0$ $\equiv a_{k - 1}10^{k - 1} + a_{k - 2}10^{k - 2} + ... + a_1(10) + a_0 \pmod{2^k}$.

This proves the claim.

Now, we continue with the slightly more complicated divisibilty test for $3$ and $9$.

A number is divisible by $3$ (or $9$) if and only if its sum of digits is divisible by $3$ (or $9$).

Try to prove it if you haven't before.

Again, let $n = a_m10^m + a_{m - 1}10^{m - 1} + ... + a_1(10) + a_0$.

Then,

$n = a_m10^m + a_{m - 1}10^{m - 1} + ... + a_1(10) + a_0$ $\equiv a_m1^m + a_{m - 1}1^{m - 1} + ... + a_1(1) + a_0$ $\equiv a_m + a_{m - 1} + ... + a_1 + a_0 \pmod{9}$. (The same goes for mod $3$.)

How about the divisibility tests of $11$? Well, instead of the sum of digits, it's their alternating sum that needs to be tested. The proof is similar, but if you're interested and can't prove it, see here for a list of divisibility rules.

Next part

Let's start by explaining the divisibility rule for $9$. Take a number, such as $3465$. Any number can be broken down into a place value with coefficient form, like $3465$ is $3 * 1000 + 4 * 100 + 6 * 10 + 5$. Now watch the steps below:

Substitute the powers of $10$ into $1$ + multiples of $9$: $3465 = 3(999 + 1) + 4(99 + 1) + 6(9 + 1) + 5$

When we expand this, we get: $3465 = 3 * 999 + 3 + 4 * 99 + 4 + 6 * 9 + 6 + 5$

We can collect the multiples of $9$, so we have: $3465 = x * 9 + 3 + 4 + 6 + 5$.

We have grouped our number. Now we see that if the sum of the digits(i.e., $3, 4, 6, 5$) is divisible by $9$, in this case it is true, the number is divisible by $9$.

This is also the divisibility trick for $3$, because whatever multiples we took out in the explanation above that were divisible by $9$ are also divisible by $3$, and the extra(the sum of the digits) should be divisible by $3$.

The divisibility trick for $11$ uses the fact that:

$(1 - 1)$ mod $11$ = $0$.

$(10 + 1)$ mod $11$ = $0$.

$(100 - 1)$ mod $11$ = $0$.

$(1000 + 1)$ mod $11$ = $0$.

$(10000 - 1)$ mod $11$ = $0$.

...................................................................

See the pattern above? We'll use this to check if our new number, $89166$, is divisible by $11$.

$89166 = 8(a * 11 + 1) + 9(b * 11 - 1) + 1(c * 11 + 1) + 6(d * 11 - 1) + 6(e * 11 + 1)$

Taking out the multiples of $11$, we get: $89166 = 11(8a + 9b + 1c + 6d + 6e) + 8 - 9 + 1 - 6 + 6$.

Therefore, if our number is divisible by $11$, the number obtained by adding alternative digits and subtracting the sums should be divisible by $11$.