19
$\begingroup$

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

$\endgroup$
5
  • 9
    $\begingroup$ You may want to look at this. There are many other accessible sources. $\endgroup$ Mar 12, 2013 at 16:18
  • 4
    $\begingroup$ 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. $\endgroup$ Mar 12, 2013 at 17:02
  • $\begingroup$ A cheap answer $\endgroup$ Oct 4, 2016 at 10:53
  • $\begingroup$ See this answer for a general approach. $\endgroup$ Jun 14, 2019 at 16:33
  • $\begingroup$ Here's one way of doing it for any divisor coprime to ten. For some divisors there are more efficient methods (handling more than one digit at a time). $\endgroup$ Apr 27, 2021 at 16:20

2 Answers 2

20
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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