Tests of divisibility - 1

Everyone knows the tests for divisibility by $2$ and $5$; they are obvious. The tests for divisibility by $4$, $8$, $3$, $6$, $9$ and $11$ are less obvious but still well known; each one is based in some way on the digits of the given number. (The logic behind these tests may be less clear - particularly for divisibility by $11$. But we expect that most students have at least an inkling of the underlying logic. I hope so anyway!) 

What about divisibility by $7$? Some of you may know of this test: 

Given an integer $N$, let $b$ be its units digit, and let $a$ be the rest of the number, obtained by deleting the units digit; this means that $N = 10a + b$. Now replace $N$ by $a - 2b$. In other word, subtract twice the units digit from the rest of the number. Now repeat the same step for the new number, and keep doing this till you get a small number $M$ for which you can check divisibility by $7$ mentally. If this check works out (i.e., $M$ is divisible by $7$), then the original number $N$ is divisible by $7$; else it is not. 

Thus this is an ``if and only if'' test. Here are two examples:

• If $N = 123456$, then we do $12345 - 12 = 12333$. Next we do: $1233 - 6 = 1227$. Next: $122 - 14 = 108$, and $10-16 = -6$. The last number ($-6$) is clearly not a multiple of $7$; hence, neither is the original number, $123456$.
• Or try $N = 1504055$. We get: $150405 - 10 = 150395$. Next: $15039 - 10 = 15029$. Next: $1502 - 18 = 1484$. Next: $148 - 8 = 140$. We can stop now, since $140$ is quite visibly a multiple of $7$. We conclude that $1504055$ too is a multiple of $7$.

Why does this work? Here is a proof; it uses two simple facts: 

• The sum and difference of two multiples of $7$ are also multiples of $7$.
• If $y$ is an integer such that $3y$ is a multiple of $7$, then $y$ itself is a multiple of $7$. (Do you see why? The point is that $3$ and $7$ are relatively prime to each other.)

Let us now show that for any two integers $a$ and $b$, the quantities $x = 10a+b$ and $y = a-2b$ are either both divisible by $7$ or both indivisible by $7$. For we have:

\[x - 3y = (10a + b) - 3(a - 2b) = 7a + 7b = 7(a + b),\]

which tells us that $x-3y$ is a multiple of $7$. Now:

• If $x$ is a multiple of $7$, then $3y$ is a multiple of $7$, and hence so is $y$.
• And if $y$ is a multiple of $7$, then so is $3y$, and hence so is $x$.

This reasoning carries right through the entire working of the algorithm. 


Conclusion. The initial number is a multiple of $7$ if and only if the final number is a multiple of $7$.

So this is why the test works, but the proof raises several more questions:

1. What is the significance of $2$ as a multiplier in the above test (i.e., "twice the units digit")? How could we have found this multiplier?
2. Are there tests similar to this for testing divisibility by $9$? $11$? $13$? $17$? $19$?

We'll try to answer these in the next entry! Cheers till then.