Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
7  
You may want to look at this. There are many other accessible sources. –  André Nicolas Mar 12 '13 at 16:18
2  
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

2 Answers 2

up vote 10 down vote accepted

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

share|improve this answer

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
                   Vitthal Jadhav (DrZero.in)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.