Vtgyjfy

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

$(1)$

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

Observe that $sum_{0le rle n}{a_r10^r}equiv a_0pmod 2$

$sum_{0le rle n}{a_r10^r}equiv a_0pmod 5$

$sum_{0le rle n}a_r10^requiv sum_{0le rle n}a_rpmod 3$ as $9mid(10^r-1)$

$sum_{0le rle n}a_r10^requiv sum_{0le rle n}(-1)^ra_rpmod {11}$ as $10^requiv(-1)^rpmod{11}$

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

$(2)$

$N=sum_{0le rle n}a_r10^requiv sum_{0le rle m-1}a_r10^rpmod {10^m}equiv sum_{0le rle m-1}a_r10^rpmod {2^m}$ as $2^smid 10^s$ where integer $sge0$

This explains why $2^mmid Niff $ 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+ycdot v=1$ (using Bézout's Identity)

So, $u(10a+b)+vcdot ycdot a=a(10u+ycdot v)+ucdot b=a+ucdot bimplies 10a+b$ will be divisible by $yiff ymid(a+ucdot b)$

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

So, $(a+ucdot b)$ becomes $a-2b$

If $y=19,$ we find $2cdot10+(-1)19=1implies u=2implies a+ucdot 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,

$$nequiv 5a+4b+6c+2d+3e+fmod 7.$$

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

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

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

For instance

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

You can generalize the method to other divisors.