We all know how to recognize numbers that are multiple of $2, 3, 4, 5$ (and other). Some other divisors are a bit more difficult to spot. I am thinking about $7$.
A few months ago, I heard a simple and elegant way to find multiples of $7$:
Cut the digits into pairs from the end, multiply the last group by $1$, the previous by $2$, the previous by $4$, then $8$, $16$ and so on. Add all the parts. If the resulting number is multiple of $7$, then the first one was too.
Example:
$21553$
Cut digits into pairs:
$2, 15, 53$
Multiply $53$ by $1, 15$ by $2, 2$ by $4$:
$8, 30, 53$
Add:
$8+30+53=91$
As $91$ is a multiple of $7$ ($13 \cdot 7$), then $21553$ is too.
This works because $100-2$ is a multiple of 7. Each hundreds, the last two digits are 2 less than a multiple of $7 (105 → 05 = 7 – 2, 112 → 12 = 14 – 2, \cdots)$
I figured out that if it works like that, maybe it would work if we consider $7=10-3$ and multiplying by $3$ each digit instead of $2$ each pair of digits.
Exemple with $91$:
$91$
$9, 1$
$9\cdot3, 1\cdot1$
$27, 1$
$28$
My question is: can you find a rule that works with any divisor? I can find one with divisors from $1$ to $19$ ($10-9$ to $10+9$), but I have problem with bigger numbers. For example, how can we find multiples of $23$?
Best Answer
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{red}{4\ 3}\ 2\ 1\ 1$
$\rm\qquad\equiv\phantom{4} \color{green}{1\ 2}\ 1\ 1\quad $ by $\rm\quad \color{red}4\cdot 3 + \color{red}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\:$).