Divisibility Rule for 7 using 315462

Question

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?

Answer 1

Let $\, n = d_0 + d_1 10 + d_2 10^2 + \cdots + d_k 10^k = P(10),\,$ where $P(n)$ is $\,n$'s $ $ radix $10$ polynomial, with digits $\,d_i.\,$ You are evaluating $\ \color{#0a0}{2\, P(3)}\,$ since your sequence $\, 2, 6, 4, 5,\ldots \equiv 2\cdot 3^k\pmod{\!7}$.

Now $\,{\rm mod}\ 7\!:\ \color{#c00}{10\equiv 3}\,$ $\Rightarrow$ $\,P(\color{#c00}{10})\equiv P(\color{#c00}3),\,$ by the Polynomial Congruence Rule, therefore this congruence implies $\,7\mid P(10)\iff 7\mid P(3)\!\iff\! 7\mid \color{#0a0}{2P(3)},\,$ using divisibility mod reduction for the first $(\!\!\iff\!\!);$ whereas the second arrow uses by $\color{#0a0}{(7,2)=1}$ and Euclid's Lemma.

So your method yields a valid divisibility test. If we instead used sequence $\,3^k \equiv 1,3,2,6,4,5\,$ then we'd obtain 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 we compute the "dot product". This method has a big advantage: $\,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 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\ \bbox[5px,border:1px solid #c00]{3 \,d_n + d_{n-1}\bmod 7}\ $ viz.

$$\begin{array}{rrl} &\color{#0A0}{4\ 3}\ 2\ 1\ 1&\\ \equiv\!\!\!\! &\color{#c00}{1\ 2}\ 1\ 1 &\!{\rm by}\, \ \bbox[5px,border:1px solid #c00]{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.

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

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

Answer 4

you can just stack them on top of each other every 6 decimal digits instead of having to do a ton of dot products :

 8345298427052 (mod 7)

 ≡ 8 + 345,298 + 427,052 (mod 7)

 ≡ 772,358 (mod 7)

since 10^3 ≡ 6 (mod 7) ≡ -1 (mod 7), then

 ≡ (-1 * 772 + 358) (mod 7)

 ≡      -414        (mod 7)

 ≡      -414 + 7^3  (mod 7)
 ≡       -71        (mod 7)
 ≡        -1        (mod 7)  => [ 6 ]

Or let's try a gigantic example - the popular ECC prime 2^255 - 19 (mod 7)

 57896044618658097711785492504343953926634992332820282019728792003956564819949

              57896
 + 044618 =  102514
 + 658097 =  760611
 + 711785 = 1472396
 + 492504 = 1964900
 + 343953 = 2308853
 + 926634 = 3235487
 + 992332 = 4227819
 + 820282 = 5048101
 + 019728 = 5067829
 + 792003 = 5859832
 + 956564 = 6816396
 + 819949 = 7636345 

 ≡ (   7 + 636,345   ) (mod 7)
 ≡ (1000 * 636 + 352 ) (mod 7)
 ≡ (  -1 * 636 + 352 ) (mod 7)

 ≡ -284 (mod 7)
 ≡   -4 (mod 7) => [ 3 ]

or

 ≡ (       7,636,345  ) (mod 7)
 ≡ ( (̵7̵)̵(̵6̵3̵)̵(̵6̵3̵)̵(45) ) (mod 7)
 ≡ (              45  ) (mod 7) => [ 3 ] 

which matches both validation chains :

   (        (2)^255 - 19 ) (mod 7)
 ≡ ( 32 +  (32)^51  - 51 ) (mod 7)
 ≡ (  4 + (4^3)^17  -  2 ) (mod 7)
 ≡ (  4 +   (1)^17  -  2 ) (mod 7)
 ≡ (  4 +    1      -  2 ) (mod 7) => [ 3 ]

or

   ( (2)^255 - 19 ) (mod 7)
 ≡ ( (8)^85  -  5 ) (mod 7)
 ≡ ( (1)^85  -  5 ) (mod 7)
 ≡ (         -  4 ) (mod 7) => [ 3 ]