# 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

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

-

I) 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 divisible divisor then only number is divisible.

E.g. 1) 7 | N if and only if 7 | (N % 1001) i.e. N % 7 = (N % 1001) % 7

     similarly, N % 13 = (N % 1001) % 13,


II) By 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 'Modern approach to speed math secret' can refer to tinyurl.com/mlxk8pw . Book explore unique secret behind speed math , Booths multiplication etc. It explains whole speed math using Zero

                       Regard