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

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?

• 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. – Steven Stadnicki Nov 7 '19 at 3:55
• $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$ – J. W. Tanner Nov 7 '19 at 3:59

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}

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

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