Tests of divisibility - 2

I asked last time, "What is the significance of $2$ as a multiplier in the test for divisibility by $7$?'' I also asked, ``Are there tests similar to this for testing divisibility by other divisors - like $9$, $11$, $13$, $17$, $19$, ..."


The answer to the latter question is a loud "Yes!". Indeed, one can find such a test for any divisor which has no factors in common with $10$; that is, any divisor whose units digit is $1$, $3$, $7$ or $9$.


The logic behind this gets revealed when we understand the role played by the multiplier $2$ in the test for divisibility by $7$.


One way to understand the role played by $2$ is to note that $7$ has $21$ as a multiple (note that $21$ has $2$ as its tens digit), and if we apply the transformation $10a + b \mapsto a - 2b$ to $21$, we get $0$ right away. We also get $0$ if we apply it to multiples of $21$ like $42$, $63$, $84$, $105$, $126$, ... Try it out and you'll see this for yourself.


Noting this, we are led to invent a new test of divisibility. Let $k$ be any positive integer. Consider the following function $f_k$ which acts on the positive integers $x$ thus: If $x = 10a + b$, where $0 \le b \le 9$, then $f_k (x) = a - k b$. Then:

• $x$ is divisible by $10k + 1$ if and only if $f_k (x)$ is divisible by $10k + 1$.

To see that this claim is valid, observe that
\[kx + f_k (x) = k(10a + b) + (a - kb) = a(10k + 1).\]
Now:

• If $x$ is divisible by $10k + 1$, then so is $kx$, and so also is $f_k (x)$ from the above relation.
• If $f_k (x)$ is divisible by $10k + 1$, then so also is $kx$, from the above relation. And since $k$ and $10k + 1$ are coprime (they must be, because $10k + 1$ leaves remainder $1$ when divided by $k$), this means that $x$ itself is divisible by $10k + 1$.

It follows that $x$ is divisible by $10k + 1$ if and only if $f_k (x)$ is divisible by $10k + 1$.


From this observation we quickly get many different tests of divisibility, all at the same time (in fact, infinitely many of them):

• Putting $k = 3$, we get a test of divisibility by $31$: The integer $10a + b$ is divisible by $31$ if and only if $a - 3b$ is divisible by $31$. So the test is: Subtract three times the units digit from the rest of the number, and proceed as earlier.
• Putting $k = 4$, we get a test for divisibility by $41$: The integer $10a + b$ is divisible by $41$ if and only if $a - 4b$ is divisible by $41$. So the test is: Subtract four times the units digit from the rest of the number, and proceed as earlier.
• Similarly, $k = 6$ gives a test for divisibility by $61$, $k = 7$ gives a test of divisibility by $71$, and so on.

What about $k = 2$? This gives us a test for divisibility by $21$. But $21 = 3 \times 7$ is a composite number. So the same test serves as a test for divisibility by both $3$ and $7$. Hence:

• The number $10a + b$ is divisible by $3$ if and only if $a - 2b$ is divisible by $3$.
• The number $10a + b$ is divisible by $7$ if and only if $a - 2b$ is divisible by $7$.

Similarly, if $k = 5$ we get another composite number, $51 = 3 \times 17$. Hence:

• The number $10a + b$ is divisible by $17$ if and only if $a - 5b$ is divisible by $17$.

(Note that from $k = 5$ we get another test for divisibility by $3$; however a bit of thought will show that it is equivalent to the test obtained by taking $k = 2$. So we need not list it here.)


If $k = 9$ we get yet another composite number, $91 = 7 \times 13$. So from this we get a test for divisibility by $13$:

• The number $10a + b$ is divisible by $13$ if and only if $a - 9b$ is divisible by $13$.

Two values of $k$ of particular interest are $k = 1$, and $k = 8$. Let us see why.


If $k = 1$ then $10k + 1 = 11$. The test now is:

• The number $10a + b$ is divisible by $11$ if and only if $a - b$ is divisible by $11$.

Now the mapping $10a + b \mapsto a - b$ amounts to this: Subtract the units digit from the rest of the number.


I wonder if you see that this test is just a disguised form of the usual test for divisibility by $11$.


If $k = 8$ then $10k + 1 = 81 = 9 \times 9$; so this should give us a test for divisibility by $9$. The test is:

• The number $10a + b$ is divisible by $9$ if and only if $a - 8b$ is divisible by $9$.

Now, it is obvious that $a - 8b$ is divisible by $9$ if and only if $a + b$ is divisible by $9$ (because $(a + b) - (a - 8b) = 9b$, which is a mutiple of $9$). Hence:

• The number $10a + b$ is divisible by $9$ if and only if $a + b$ is divisible by $9$.

Now the mapping $10a + b \mapsto a + b$ amounts to this: Add the units digit to the rest of the number.


I wonder if you see that this test too is just a disguised form of the usual test for divisibility by $9$.


In this manner we can get a test for divisibility by any number with units digit $1$, and by any number which divides a number with units digit $1$.


A very similar line of reasoning gives tests for divisibility by numbers with units digit $9$; i.e., divisors like $19$, $29$, .... But we'll leave this to the next post.