1
$\begingroup$

Prove the divisibility test by $7,11,13$ for numbers more than six digits


Attempt:

We know that $7\cdot 11 \cdot 13 = 1001$. The for a six-digit number, for example, $120544$, we write it as $$ 120544 = 120120 + 424 = 120\cdot1001 + 424 $$ thus we just check the divisibility of $424$ by $7,11,13$.

Know for a number with more than six digits, for example: $270060340$,

$$270060340 = 270270270 - 209930$$ $$ = 270 \cdot (1001001) - 209930 $$ $$ = 270 \cdot (1001000) + (270 - 209930) =270 \cdot (1001000) - 209660$$

so we check the divisibility of $209660 = 209209 + 451$, or just $451$.

But the test states that: for $270060340$, we group three digits from the right: $$ 270, 60, 340$$ then check divisibility of $340+270 - (60)$.

How to prove this?

$\endgroup$
2
  • $\begingroup$ Essentially, the test uses the fact that $a \equiv (a\mod 1000 - \lfloor a/1000\rfloor)\pmod {1001}$. Just iterate the $\lfloor a/1000\rfloor$ piece of this and note that the sign changes every time you do. $\endgroup$ – Steven Stadnicki Nov 7 '19 at 3:55
  • 1
    $\begingroup$ $a_0+1000a_1+1000000a_2+1000000000a_3+\dots+10^{3n}a_n\equiv a_0-a_1+a_2-a_3+\dots+(-1)^n a_n\mod1001$ $\endgroup$ – J. W. Tanner Nov 7 '19 at 3:59
1
$\begingroup$

It's the radix$+1$ divisibility test for radix $10^3,\,$ i.e. the analog of casting out $11's$ in radix $10,\,$ viz.

$\!\!\!\begin{align}\bmod 10^{\large 3}\!+\!1\!:\,\ \color{#0a0}{10^{\large 3}}\equiv \color{#c00}{\bf -1}\, \ \Rightarrow\!\!\!\! &\ \ \ \ \ \ \overbrace{d_0 + d_1 \ \color{#0a0}{10^{\large 3}} +\, d_2(\color{#0a0}{10^{\large 3}})^{\large 2}\! + d_3(\color{#0a0}{10^{\large 3}})^{\large 3}+\,\cdots }^{\!\!\!\!\!\!\!\textstyle\text{integer in radix $\color{#0a0}{10^{\large 3}}$ with digits $\,d_i$}} \\[.3em] &\equiv\, d_0\!+d_1(\color{#c00}{\bf -1})\!+d_2(\color{#c00}{\bf -1})^{\large 2}\! + d_3(\color{#c00}{\bf -1})^{\large 3} +\,\cdots \\[.3em] &\equiv\, d_0\ \ \color{#c00}{\bf -}\ \ d_1\ \ +\ \ d_2\ \ \color{#c00}{\bf -}\ \ d_3\ +\, \cdots\\[.2em] &\equiv\, \color{#c00}{\text {alternating}}\text{ digit sum}\end{align}$

where we employed the Congruence Sum & Product Rules (or Polynomial Rule)

$\!\begin{align}\text{E.g. in your 2nd example: }\ \ \ \ \ \ \ &\overbrace{270\,,\,060\,,\,340}^{\textstyle d_2,\ \ d_1,\ \ d_0}\\[.2em] \equiv\ &270\! -\! 060\! +\! 340\, \equiv\, 550\!\pmod{\!1001}\end{align}$

$\endgroup$
0
$\begingroup$

$1001$ divides $999,999$ and $999,999 = 1,000,000 - 1$

$270,060,340 = (270,000,000 - 27) + (60,000 + 60) + 340 + 27 -60$

The first two terms are divisible by $1001$ (and hence 7,11, and 13)

$\endgroup$
0
$\begingroup$

For 9-digit number: $abcdefghi$,

$$ abcdefghi = abc000000 + defghi = abc000000 + def \cdot 1001 - def + ghi $$ so we check divisibility of $$ abc000000 - def + ghi = abc \cdot 1001000 - abc000 - def + ghi$$ so we cehck divisibility of $$ -abc000 - def + ghi = -(abc \cdot 1001 - abc) - def + ghi$$ in the end we only check $abc + ghi - def$.

If 12-digit number: $$ a_{1} a_{2} ... a_{11}a_{12} = a_{1} a_{2} a_{3} 000000000 + \underbrace{a_{4} ... a_{12}}_{9-digit}$$

so we check the divisibility of $$ a_{1} a_{2} a_{3} 000000000 + ( a_{10}a_{11}a_{12} + a_{4} a_{5}a_{6} - a_{7}a_{8}a_{9}) $$ or just $$ = (a_{10}a_{11}a_{12} + a_{4} a_{5}a_{6} - a_{7}a_{8}a_{9} - a{1} a_{2} a_{3}) $$

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