Divisibility criteria for $7,11,13,17,19$

A number is divisible by $2$ if it ends in $0,2,4,6,8$. It is divisible by $3$ if sum of ciphers is divisible by $3$. It is divisible by $5$ if it ends $0$ or $5$. These are simple criteria for divisibility.

I am interested in simple criteria for divisibility by $7,11,13,17,19$.

Solution 1:

$(1)$

The formulae for $2,3,5,9,11$ can be derived from $\sum_{0\le r\le n}{a_r10^r}$

Observe that $\sum_{0\le r\le n}{a_r10^r}\equiv a_0\pmod 2$

$\sum_{0\le r\le n}{a_r10^r}\equiv a_0\pmod 5$

$\sum_{0\le r\le n}a_r10^r\equiv \sum_{0\le r\le n}a_r\pmod 3$ as $9\mid(10^r-1)$

$\sum_{0\le r\le n}a_r10^r\equiv \sum_{0\le r\le n}(-1)^ra_r\pmod {11}$ as $10^r\equiv(-1)^r\pmod{11}$

$\sum_{0\le r\le n}a_r10^r\equiv(a_0+a_2+a_4+\cdots)-(a_1+a_3+a_5+\cdots)\pmod{11}$

$(2)$

$N=\sum_{0\le r\le n}a_r10^r\equiv \sum_{0\le r\le m-1}a_r10^r\pmod {10^m}\equiv \sum_{0\le r\le m-1}a_r10^r\pmod {2^m}$ as $2^s\mid 10^s$ where integer $s\ge0$

This explains why $2^m\mid N\iff $ the numbers with lower $m$ digits of $N$ is divisible by $2^m$

For example, $2524$ will be divisible by $2^2=4$ as $24$ is, but $2514$ will not be divisible by $2^2=4$ as $14$ is not.

Similarly for $5^m$

$(3)$

For any number $y$ co-prime with $10,$ we can have a reduction formula as follows:

If a number be $10a+b,$ we can find $u,v$ in integers such that $10u+y\cdot v=1$ (using Bézout's Identity)

So, $u(10a+b)+v\cdot y\cdot a=a(10u+y\cdot v)+u\cdot b=a+u\cdot b\implies 10a+b$ will be divisible by $y\iff y\mid(a+u\cdot b)$

For example if $y=7, $ we find $3\cdot7+(-2)10=1\implies u=-2,v=3$

So, $(a+u\cdot b)$ becomes $a-2b$

If $y=19,$ we find $2\cdot10+(-1)19=1\implies u=2\implies a+u\cdot b=a+2b$

We can always use convergent property of continued fractions to find $u,v$.

There is no strong reason why this can not be generalized to any positive integer bases.

Solution 2:

Let $n=\text{'abcdef'}=10^5a+10^4b+10^3c+10^2d+10e+f$. Using modular arithmetic,

$$n\equiv 5a+4b+6c+2d+3e+f\mod 7.$$

As $10^6\bmod7=1$, this repeats for the next groups of $6$ digits.

To get smaller coefficients, you can reduce some of them by $-7$, giving

$$n\equiv (f-c)+2(d-a)+3(e-b)\mod 7.$$

For instance

$$123456\equiv (6-3)+2(4-1)+3(5-2)\equiv18\mod7$$ isn't divisible by $7$.

You can generalize the method to other divisors.