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

• You may want to look at this. There are many other accessible sources. – André Nicolas Mar 12 '13 at 16:18
• I think it's worth noting that since $7\cdot11\cdot13=1001$, you can reduce modulo $1001$ before checking for divisibility by $7$, $11$ or $13$. That is why the tests for $7$ and $13$ in the page which @AndréNicolas linked to suggest forming alternating sums of groups of three digits. – Harald Hanche-Olsen Mar 12 '13 at 17:02
• A cheap answer – Antonio Hernandez Maquivar Oct 4 '16 at 10:53
• See this answer for a general approach. – Bill Dubuque Jun 14 '19 at 16:33

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