prime numbers - How to recognise the digit multiplication, subtraction or addition when checking for divisibility by 7, 11, 13, 17 and 19?

I was studying this page Divisibility by prime numbers under 50 to check for the divisibility by 7, 11, 13, 17, 19 etc. Is there any way to recognise whether to add or sub the given times of unit digit from the truncated number and to know how many times do I have to multiply with the unit digit.

For example:

to check for the divisibility by 7: subtract 2 times the unit digit from truncated number.

for 11: subtract 1 times

for 13: add 4 times the unit digit etc.

Answer

Yes, we can. Suppose we want to test a number $n$ for divisibility by $d$. Notice that we can expand $n$ with a result of $x$ after truncating the last digit $y$:
$$n=10x+y.$$
And we want to find some number $n'$ of the form $n'=x+\alpha y$ such $n'$ is divisible by $d$ exactly when $n$ is. For numbers not divisible by $2$ or $5$, there is an elegant solution to this; in particular, there is some number $\alpha$ such that $d$ divides $10\alpha - 1$. Why this matters is then we can write

$$n'=\alpha n = 10\alpha x + \alpha y$$
which will be divisible by $d$ exactly when $n$ was ($\alpha$ and $d$ must be coprime, meaning that $k\alpha$ is divisible by $d$ exactly when $k$ was) but since $10\alpha = cd + 1$ for some integer $c$ (because $10\alpha -1$ is a multiple of $d$), we can write this as:
$$n'=(cd+1)x + \alpha y$$
and we can get rid of the $cd$ term, since it is divisible by $d$ and clearly if $n$ is divisible by $d$, so is $n-kd$ for any integer $k$. Thus, for our purposes, we can replace $n$ by $x+\alpha y$, getting rid of the $cdx$ term, without changing issues of divisibility by $d$.

This $\alpha$ term is the multiplicative inverse of $10$ mod $d$, which can be computed either by the Extended Euclidean algorithm, as described on the Wikipedia page. Trial and error would work too (you just need to find the first positive multiple of $d$ with a $9$ in the one's place or a negative multiple with a $1$ in the one's place). Notice that your existing identities follow this pattern; for $d=7$, we choose $\alpha=-2$, and $10\cdot (-2) - 1 = -21$, which is a multiple of $7$. Similarly, for $11$, we have $\alpha=-1$ and $10\cdot (-1) - 1 = -11$, which is a multiple of $11$ and, for $13$, we have $10\cdot 4 - 1 = 39$, which is a multiple of $13$.

So, for instance, to find a rule for $17$, we would notice that $-3\cdot 17= -51 = 10\cdot -5-1$. Thus, to compute divisibility by $17$, we chop off the unit digit $y$, and subtract $3y$ from the remaining number. To be very explicit, we can give the following general rules for divisibility tests of this form:

• If $d=10k + 1$, then subtract $k$ times the unit digit from the rest.


• If $d=10k + 3$, then add $3k+1$ times times the unit digit to the rest.


• If $d=10k + 7$, then subtract $3k+2$ times the unit digit from the rest.


• If $d=10k + 9$, then add $k+1$ times the unit digit to the rest.