Divisibility rules and congruences

We need not 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\: (\color{#0a0}{d_2\cdot\color{#90f}{10} + d_1})\ 10 + d_0\ \equiv\ (\color{#0a0}{d_2\cdot 3 + d_1})\ 3 + d_0\ (mod\ 7)\ $ since $\rm\ \color{#90f}{10}\equiv\color{#0a0}3\ (mod\ 7).\:$ Hence we compute the remainder $\rm\ (mod\ 7)\ $ as follows. Start with the leading digit then repeatedly apply the operation: $\rm\color{#0a0}{multiply\ by\ 3\ then\ add\ the\ next\ digit}$, doing all of the arithmetic $\!\bmod 7$.

For example, let's use this algorithm to compute $\, 43211\bmod 7.\,$ The algorithm consists of repeatedly replacing the first two leading digits $\rm\ \color{#0a0}{d_n\ d_{n-1}}\ $ by $\rm\, \color{#0a0}{(\color{#000}3\, d_n + d_{n-1})}\bmod 7,\,$ namely

$$\begin{array}{rrl}\bmod 7\!:\ &\color{#0A0}{4\ 3}\ 2\ 1\ 1^{\phantom{|^{|}}}\!\!\!&\\ \equiv\!\!\!\! &\color{#c00}{1\ 2}\ 1\ 1 &\!{\rm by}\ \ \:\! \smash[t]{\overbrace{3\cdot \color{#0a0}4 + \color{#0a0}3}^{\rm\textstyle\color{#0a0}{\,\color{#000} 3\,\ d_n\! + d_{n-1}}\!\!\!\!\!\!\!}} \equiv\ \color{#c00}1\\ \equiv\!\!\!\! &\color{#0af}{5\ 1}\ 1&\!{\rm by}\ \ \ 3\cdot \color{#c00}1 + \color{#c00}2\ \equiv\ \color{#0af}5\\ \equiv\!\!\!\! & \color{#f60}{2\ 1}&\!{\rm by}\ \ \ 3\cdot \color{#0af}5 + \color{#0af}1\ \equiv\ \color{#f60}2\\ \equiv\!\!\!\! &\color{#8d0}0&\!{\rm by}\ \ \ 3\cdot \color{#f60}2 + \color{#f60}1\ \equiv\ \color{#8d0}0 \end{array}\qquad\qquad\quad\ \, $$

Hence $\rm\ 43211\equiv 0\pmod{\!7},\,$ indeed $\rm\ 43211 = 7\cdot 6173.\:$ Generally the modular arithmetic is simpler if we use least magnitude residues, e.g. $\rm\, \pm\{0,1,2,3\}\ \:(mod\ 7),\,$ by allowing negative digits, e.g. here. Note 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$).

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.

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.