Ways to check whether a number is multiple of another number.

Question

We know that, giving a number, by adding up each of its digit, and mod the result by 3, if the reminder is 0, then the number is a multiple of 3, otherwise, it's not.

This algorithm works for 9 too.

I am wondering do there have similar general algorithms to check other small prime numbers, e.g. 7 or 11?

Or, just that 3 and 9 are too special?

Answer 1

A number written with digits $d_n\ldots d_2 d_1 d_0$ in decimal notation means $$ 10^n d_n + \cdots + 10^2 d_2 + 10^1 d_1 + d_0 $$

Divisibility tests are generally based on working modulo the divisor and correcting for the effect of the $10^n$ factors of the sum.

Dividing by $3$ and $9$ are special because $10\equiv 1$ modulo $3$ or $9$, so the $10^n$ factors disappear completely. These are the only divisors with this property (except for $1$, which is trivial). For all other divisors, different digit positions contribute differently to the sum, and the divisibility rules are correspondingly more complicated to state.

(Well, actually the divisibility rules for $2$ and $5$ are even simpler because $10\equiv 0$ modulo $2$ or $5$, so all terms in the sum above except for $d_0$ vanish completely and you need only to look at the last digit).

---

In other bases than ten, say, base $b$, it is similarly simple to test for divisibility by $b-1$ -- or divisibility by any divisor of $b-1$. In base sixteen, for example, the sum-of-digits test works for divisibility by $3$ but not for $9$ (because $9$ does not divide fifteen). But it does work for divisibility by $5$ in that setting.

---

If you know programming, here is pseudocode for a generic divisibility test:

// input: d[n] ... d[0] are the digits of the input number
// input: D, the divisor
b = 10 // the base
s = 0  // a running sum
w = 1  // magic sauce: note carefully what happens to this
for i = 0 to n:
   s = s + w * d[i]
   w = (b * w) % D
// now s is divisible by D if and only if the original number was

The nice shape of the tests for $D=3$ and $D=9$ are because in that case w = (b * w) % D is a no-op (because (b*w)%D == ((b%D)*(w%D))%D always and b%D==1) so w stays $1$ throughout the loop, unlike in other cases.

The more complex divisibility tests for other divisors correspond to precomputing the sequence of ws.

Answer 2

The special feature of $9$ is that it is one less than the number of our fingers (i.e., our base). In other words, $3\mid 10-1$. However, $7\mid 10^6-1$, so we immediately find a (not so perfect) rule: group the digits in groups of six from the end, add those six-digit numbers, and check if the sum is divisible by $7$ (possibly by repeating this procedure). Similarly, from $11\mid 10^2-1$, we can work with groups of two digits to test divisibility by $11$.

Incidentally, there is a simpler test for $11$: the alternating digit sum. Similarly, you can work with the alternating sum of groups of three diits for $7$.

Answer 3

While there are motley divisibility tests derivable from $\,c\mid 10 a + b\iff c\mid ja+kb\,$ for small $\,j,k\,$ it is usually simpler and quicker to just use modular arithmetic (which, unlike said tests, has the benefit of computing the remainder, so may be used to check arithmetic, as in casting out nines).

This universal method amounts to evaluating a radix polynomial in nested Horner form, using modular arithmetic. For example, consider evaluating a $4$ digit radix $10$ number modulo $7$.

$$\begin{align} \rm\ d_3\ d_2\ d_1\ d_0 \rightarrow\ &\rm ((d_3\cdot 10 + d_2)\cdot 10 + d_1)\ 10 + d_0\\ \equiv\ &\rm (\color{#c00}{(d_3\cdot\ 3\ + d_2)}\cdot\ 3\ + d_1)\ \ 3\ + d_0\!\!\pmod{7}\end{align}\qquad$$

because $\rm\ 10\equiv 3\,\ (mod\,\ 7)\:.\:$ Thus we can compute the remainder $\rm\ (mod\ 7)\ $ by repeatedly replacing the two leading digits $\rm \,d_k\,d_{k-1}\,$ by $\rm \ \color{#c00}{(d_k\cdot 3 + d_{k-1})}\ {\rm mod}\ 7.\,$ For example

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

$\rm\qquad\qquad\qquad\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\qquad\qquad\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\qquad\qquad\qquad\equiv\phantom{4\ 3\ 5} \color{#b0f}{2\ 1}\quad $ by $\rm\quad \color{royalblue}5\cdot 3 + \color{royalblue}1\ \equiv\ \color{#b0f}2 $

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