8
$\begingroup$

Years ago while playing around with numbers came up with a divisibility rule for 7 using the number 315,462; where effectively you take the 'dot product' of your number with 315462 (repeated when necessary), and repeat.

Example: Is 298,427,052 divisible by 7?

We need to use 315462 repeated twice to match or exceed the number of digits, so 315,462,315,462 and multiply matching powers of ten while adding the products. In this case using our number (298427052) and (462315462)

$(2)(4) + (9)(6) + (8)(2) + (4)(3) + (2)(1) + (7)(5) + (0)(4) + (5)(6) + (2)(2) = 161$

Repeat procedure again

$(1)(4) + (6)(6) + (1)(2) = 42$

$(4)(6) + (2)(2) = 28$

$(2)(6) + (8)(2) = 28 $ (Cycles again, but 28 is divisible by 7)

The closest I could find online is someone else who also accidentally discovered it. His write-up might be more informative link; yet neither of us found a proof, both more heuristic testing. Is one available?

$\endgroup$
5
$\begingroup$

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(10)\equiv P(3)\pmod 7\ $ we have $\,7\mid P(10)\iff 7\mid P(3)\iff 7\mid \color{#0a0}{2P(3)}$.

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).\,$


Remark $\ $ There's a better way - a universal 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\ $ since $\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\ d_n\cdot 3 + d_{n-1}\:\ (mod\ 7),\,$ namely

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

$\rm\qquad\equiv\phantom{4} \color{#c00}{1\ 2}\ 1\ 1\quad $ by $\rm\quad \color{#0a0}4\cdot 3 + \color{#0a0}3\ \equiv\ \color{#c00}1 $

$\rm\qquad\equiv\phantom{4\ 3} \color{#0af}{5\ 1}\ 1\quad $ by $\rm\quad \color{#c00}1\cdot 3 + \color{#c00}2\ \equiv\ \color{#0af}5 $

$\rm\qquad\equiv\phantom{4\ 3\ 5} \color{#f60}{2\ 1}\quad $ by $\rm\quad \color{#0af}5\cdot 3 + \color{#0af}1\ \equiv\ \color{#f60}2 $

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

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.$

$\endgroup$
2
$\begingroup$

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 $$

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.