10
$\begingroup$

Sorry if the question is old but I wasn't able to figure out the answer yet. I know that there are a lot of divisibility rules, ie: sum of digits, alternate plus and minus digits, etc... but how can someone derive those rules for any number $n$ let's say. I know it could be done using congruences, but how ?

Thank you !

  • 1
    Here: http://www.cidse.itcr.ac.cr/revistamate/ContribucionesV7n12006/Divisibilidad/index.html A method to2011-07-21
  • 0
    The only trouble is that is in Spanish.2011-07-21
  • 0
    ...construct test of divisibility by any number greater than $10$ except multiples of 2 and 5.2011-07-21
  • 0
    Many of these rules are artifacts of a number's base representation in a particular base.2011-07-21
  • 0
    @Leo your link seems to be broken. Can you fix it?2012-05-08
  • 1
    @draks [Here](http://dl.dropbox.com/u/57684129/revistamatematica/ContribucionesV7n12006/Divisibilidad/index.html) is. Since the link can be subject to future changes this information can be useful. The article is: _Reglas de divisibilidad, Vol. 7, No. 1, 2006_ of [this](http://dl.dropbox.com/u/57684129/revistamatematica/index.htm). Notice that it is in **Spanish**.2012-05-09
  • 0
    @leo Thanks, maybe a good opportunity to learn a new language... but if you ever find a translation or comparable reference, don't hesitate to post it.2012-05-09

3 Answers 3

17

One needn't memorize motley exotic divisibility tests. There is a universal test that is simpler and much easier recalled, viz. evaluate a radix polynomial in nested Horner form, using modular arithmetic. For example, consider evaluating a $3$ digit radix $10$ number modulo $7$. In Horner form $\rm\ d_2\ d_1\ d_0 \ $ is $\rm\: (d_2\cdot 10 + d_1)\ 10 + d_0\ \equiv\ (d_2\cdot 3 + d_1)\ 3 + d_0\ (mod\ 7)\ $ since $\rm\ 10\equiv 3\ (mod\ 7)\:.\:$ So we compute the remainder $\rm\ (mod\ 7)\ $ as follows. Start with the leading digit then repeatedly apply the operation: multiply by $3$ then add the next digit, doing all of the arithmetic $\rm\:(mod\ 7)\:.\:$

For example, let's use this algorithm to reduce $\rm\ 43211\ \:(mod\ 7)\:.\:$ The algorithm consists of repeatedly replacing the first two leading digits $\rm\ d_n\ d_{n-1}\ $ by $\rm\ d_n\cdot 3 + d_{n-1}\:\ (mod\ 7),\:$ namely

$\rm\qquad\phantom{\equiv} \color{#0A0}{4\ 3}\ 2\ 1\ 1$

$\rm\qquad\equiv\phantom{4} \color{#c00}{1\ 2}\ 1\ 1\quad $ by $\rm\quad \color{#0a0}4\cdot 3 + \color{#0a0}3\ \equiv\ \color{#c00}1 $

$\rm\qquad\equiv\phantom{4\ 3} \color{#0af}{5\ 1}\ 1\quad $ by $\rm\quad \color{#c00}1\cdot 3 + \color{#c00}2\ \equiv\ \color{#0af}5 $

$\rm\qquad\equiv\phantom{4\ 3\ 5} \color{#f60}{2\ 1}\quad $ by $\rm\quad \color{#0af}5\cdot 3 + \color{#0af}1\ \equiv\ \color{#f60}2 $

$\rm\qquad\equiv\phantom{4\ 3\ 5\ 2} \color{#8d0}0\quad $ by $\rm\quad \color{#f60}2\cdot 3 + \color{#f60}1\ \equiv\ \color{#8d0}0 $

Hence $\rm\ 43211\equiv 0\:\ (mod\ 7)\:,\:$ indeed $\rm\ 43211 = 7\cdot 6173\:.\:$ Generally the modular arithmetic is simpler if one uses a balanced system of representatives, e.g. $\rm\: \pm\{0,1,2,3\}\ \:(mod\ 7)\:.$ Notice that for modulus $11$ or $9\:$ the above method reduces to the well-known divisibility tests by $11$ or $9\:$ (a.k.a. "casting out nines" for modulus $9\:$).

  • 6
    I really appreciate you using hand-picked muted colors here.2012-06-21
6

A positive integer written as $x = d_k \ldots d_1 d_0$ (in base 10) is really $\sum_{j=0}^k d_j 10^j$. Suppose $10^j \equiv m_j \mod n$. Then $x$ is divisible by $n$ if and only if $\sum_{j=0}^k d_j m_j$ is divisible by $n$. Assuming $n$ and 10 are coprime, $10^j$ is periodic mod $n$, the minimal period being a divisor of $\varphi(n)$.

For example, in the case $n=7$, we have $m_0 = 1$, $m_1 = 3$, $m_2 = 2$, $m_3 = -1$, $m_4 = -3$, $m_5 = -2$, and then it repeats. So $x$ is divisible by 7 if and only if $(d_0 - d_3 + d_6 - d_9 + \ldots) + 3 (d_1 - d_4 + d_7 - d_{10} + \ldots) + 2 (d_2 - d_5 + d_8 - d_{11} + \ldots)$ is.

  • 0
    Rather than using said well-known test for divisibility by $7$, it's simpler to use (and easier to recall) Horner evaluation mod 7, e.g. see [this post.](http://groups.google.com/groups?selm=y8zzo06ukh0.fsf%40nestle.ai.mit.edu)2011-07-21
4

Here's one example... maybe it will help you to show that something is divisible by 3 iff its digits are divisible by 3. Write your number in expanded notation[using Robert Israel's notation]:

$N=\displaystyle\sum_{j=0}^n d_j10^j, d_j\in\{0,1,\dotsc,9\}$ (assume $d_n\neq 0$)

We want to know when this number is divisible by 3; said equivalently, when this number is congruent to $0\pmod{3}$. I claim it's when the sum of the digits is divisible by 3. To show this, take our number $N\pmod{3}$:

$\displaystyle\sum_{j=0}^n d_j10^j\equiv \displaystyle\sum_{j=0}^n d_j1^j =\displaystyle\sum_{j=0}^n d_j\pmod{3}\text{ and we see that}$

When $\displaystyle\sum_{j=0}^n d_j\equiv0\pmod{3},~\displaystyle\sum_{j=0}^nd_j10^j$ is divisible by 3.