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

$(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.


General approach

For divisibility test by odd divisor except ending with 5:

  1. first find multiple of number in the form of $10^n-1$ or $10^n +1$

  2. Now compute remainder by $10^n-1$ or $10^n +1$ which is easy to compute

  3. If this remainder is exactly divisible, then the original number is divisible.

Example

$7 | N$ if and only if $7 | (N \% 1001)$

i.e. $N \% 7 = (N \% 1001) \% 7 $

Similarly, $N \% 13 = (N \% 1001) \% 13$.


Cross divisibility test

(VJ's universal divisibility test)

  • $7 | 10 T + U$ if and only if $7 | (1T-2U)$, or
  • $7 | 10 T + U$ if and only if $7 | (2T+3U)$, or
  • $7 | 10 T + U$ if and only if $7 | (T+5U)$ etc.


  • $13 | 10 T + U$ if and only if $13 | (3T-U)$, or

  • $13 | 10 T + U$ if and only if $13 | (2T-5U)$, or
  • $13 | 10 T + U$ if and only if $13 | (T+4U)$, or
  • $13 | 1000 T + U$ if and only if $13 |(T-U)$ etc.

In short, there are many approaches to check divisibility test by number. You can also check divisibility

  1. Using least Recurring length concept
  2. Using Fermat's little theorem
  3. Using vedic mathematics

To know more, read my Modern approach to speed math secret. This book explores the unique secret behind speed math, Booths multiplication etc. It explains whole speed math using Zero.


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.