Divisibility Rule for 7 using 315462

Solution 1:

Let $\, n = d_0 + d_1 10 + d_2 10^2 + \cdots + d_k 10^k = P(10).\ $ You are evaluating $\ \color{#0a0}{2\, P(3)}\,$ since $\, 2, 6, 4, 5,\ldots \equiv 2\cdot 3^k\pmod{7}$

Since $\, P(\color{#c00}{10})\equiv P(\color{#c00}3)\pmod{\! 7}\ $ we have $\,7\mid P(10)\iff 7\mid P(3)\iff 7\mid \color{#0a0}{2P(3)},\,$ because $\,{\rm mod}\ 7\!:\ \color{#c00}{10\equiv 3}\,$ $\Rightarrow$ $\,P(\color{#c00}{10})\equiv P(\color{#c00}3),\,$ by the Polynomial Congruence Rule.

Thus your method yields a valid divisibility test. If we instead used sequence $\,3^k \equiv 1,3,2,6,4,5\,$ then you'd get the standard test $\,7\mid P(10)\iff 7\mid P(3),\,$ which is usually optimized by evaluating $\,P(3)\,$ modulo $7,\,$ i.e. use mod $7$ arithmetic when you compute the "dot product". This method has the important advantage that $\,P(3)\,$ (but not $\,2P(3))\,$ has the same remainder mod $7$ as $\,P(10)\,$ so we can use it to do arithmetic mod $7$, e.g. as a check of decimal arithmetic - just like casting out nines, which similarly uses $\,{\rm mod}\ 9\!:\ 10\equiv 1\,$ $\Rightarrow$ $\,P(10)\equiv P(1),\,$ by the Polynomial Congruence Rule.

Remark $\ $ There's a better way - a universal divisibility test that is simpler and much easier recalled, viz. evaluate the above radix polynomial $\,P(x)\,$ 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 \color{#c00}{10} + d_1)\ \color{#c00}{10} + d_0\, \equiv\ (d_2\cdot\color{#c00} 3 + d_1)\ \color{#c00} 3 + d_0\pmod 7\ $ by $\rm\ \color{#c00}{10\equiv 3}\pmod{\! 7}.\,$ Thus 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 $\!\!\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\ 3 \,d_n + d_{n-1}\:\ (mod\ 7),\,$ namely

$$\begin{array}{rrl} &\color{#0A0}{4\ 3}\ 2\ 1\ 1&\\ \equiv\!\!\!\! &\color{#c00}{1\ 2}\ 1\ 1 &\!{\rm by}\ \ \ 3\cdot \color{#0a0}4 + \color{#0a0}3\ \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$$

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),\,$ e.g. see here. 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 or elevens).

The above is much better than a divisibility test since it actually calculates the remainder mod $7$ (unlike the above divisibility test, which can only be used to test if the remainder $= 0).\,$ Thus - as in casting out nines - we can perform further arithmetic with the remainders, e.g. using them to help check the correctness of calculations.

Solution 2:

I would have chosen the number $$ 546231 $$ because $$ 1 \equiv 1 \pmod 7 $$ $$ 10 \equiv 3 \pmod 7 $$ $$ 100 \equiv 2 \pmod 7 $$ $$ 1000 \equiv 6 \equiv -1 \pmod 7 $$ $$ 10000 \equiv 4 \pmod 7 $$ $$ 100000 \equiv 5 \pmod 7 $$

Then $$ 1000000 \equiv 1 \pmod 7 $$ and so on

The "dot product" with this number, repeated if necessary, with some target number $n,$ is equivalent to $n \pmod 7.$ That means that you can get your first "dot product," and if you are not yet sure, you can take this new number and do it again. After just a few tries this will be a number small enough to decide by sight.

Very similar to adding up the digits of a decimal number and repeating until the number is small, which tells you the remainder when dividing by $9.$

I see, yours is a cyclic shift, $$ 5462,31 \mapsto 315462 $$

Solution 3:

You can find a similar divisibility rule for any number $n$ that is relatively prime to $10$, you get a number of length equal to the order of $10\bmod n$.

For $n=3$ and $9$ this order is $1$, which is why we only need to sum all coefficients. When $n=11$ the order is $-1$, which is why the digits at even positions are subtracted and the others added.

In general, if $m$ is the order of $10\bmod n$, you are going to get $m$ coefficients, $a_1,a_2,\dots, a_m$ (where $a_i\equiv10^i\bmod n$).

To obtain the residue of a number $\bmod n$ you have to take the "iterated" dot product of the number, and the vector $a_m,a_{m-1},\dots,a_1$