# Divisibility rules and congruences

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
– leo Jul 21 '11 at 0:37
The only trouble is that is in Spanish. – leo Jul 21 '11 at 0:39
...construct test of divisibility by any number greater than $10$ except multiples of 2 and 5. – leo Jul 21 '11 at 0:45
Many of these rules are artifacts of a number's base representation in a particular base. – ncmathsadist Jul 21 '11 at 0:46

1
@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. – leo May 9 '12 at 2:51
show 2 more comments

## 3 Answers

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{#C00}{4\ 3}\ 2\ 1\ 1$

$\rm\qquad\equiv\phantom{4} \color{green}{1\ 2}\ 1\ 1\quad$ by $\rm\quad \color{#C00}4\cdot 3 + \color{#C00}3\ \equiv\ \color{green}1$

$\rm\qquad\equiv\phantom{4\ 3} \color{royalblue}{5\ 1}\ 1\quad$ by $\rm\quad \color{green}1\cdot 3 + \color{green}2\ \equiv\ \color{royalblue}5$

$\rm\qquad\equiv\phantom{4\ 3\ 5} \color{brown}{2\ 1}\quad$ by $\rm\quad \color{royalblue}5\cdot 3 + \color{royalblue}1\ \equiv\ \color{brown}2$

$\rm\qquad\equiv\phantom{4\ 3\ 5\ 2} 0\quad$ by $\rm\quad \color{brown}2\cdot 3 + \color{brown}1\ \equiv\ 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\:$).

-

I really appreciate you using hand-picked muted colors here. – mixedmath♦ 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.

-

– Gone 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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 57, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9260004162788391, "perplexity_flag": "head"}