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
    $\begingroup$ Here: cidse.itcr.ac.cr/revistamate/ContribucionesV7n12006/… A method to $\endgroup$ – leo Jul 21 '11 at 0:37
  • $\begingroup$ The only trouble is that is in Spanish. $\endgroup$ – leo Jul 21 '11 at 0:39
  • $\begingroup$ ...construct test of divisibility by any number greater than $10$ except multiples of 2 and 5. $\endgroup$ – leo Jul 21 '11 at 0:45
  • $\begingroup$ Many of these rules are artifacts of a number's base representation in a particular base. $\endgroup$ – ncmathsadist Jul 21 '11 at 0:46
  • 1
    $\begingroup$ @draks Here 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. Notice that it is in Spanish. $\endgroup$ – leo May 9 '12 at 2:51

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
    $\begingroup$ I really appreciate you using hand-picked muted colors here. $\endgroup$ – davidlowryduda Jun 21 '12 at 22:59

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.

  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jul 21 '11 at 2:12

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.


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.