# Divisibility by 7 rule, and Congruence Arithmetic Laws

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it.
Let $$n=(akak−1…a2a1a0)10=k∑j=0ak−j10k−jn = (a_ka_{k-1}\ldots a_2a_1a_0)_{10} = \displaystyle{\sum_{j=0}^{k}}a_{k-j}10^{k-j}$$. The expression
$$Q′3(n)=(a2a1a0)10−(a5a4a3)10+(a8a7a6)10−… Q_{3}^{\prime}(n) = (a_2a_1a_0)_{10} - (a_5a_4a_3)_{10} + (a_8a_7a_6)_{10} -\ldots$$
are called alternating sum of the digits of third order of $$nn$$. For example,
$$Q′3(123456789)=789−456+123=456 Q_{3}^{\prime}(123456789) = 789-456+123=456$$
Proposition: $$7|n ⇔ 7|Q′3(n)7 | n \ \Leftrightarrow \ 7 | Q_{3}^{\prime}(n)$$.

proof. ??

Thanks for any help.

Note $$n=c0+c11000+⋯+ck1000k=f(1000)n = c_0\! + c_1 1000 + \cdots\! + c_k 1000^k\! = f(1000)$$ is a polynomial in $$10001000$$ with integer coef’s $$ci\,c_i\,$$ thus $$mod 7: 1000≡103≡33≡−1⇒n=f(1000)≡f(−1)≡c0−c1+⋯+(−1)kck\,{\rm mod}\ 7\!:\ \color{#c00}{1000}\equiv 10^3\equiv 3^3\equiv \color{#c00}{-1}\,\Rightarrow\, n = f(\color{#c00}{1000})\equiv f(\color{#c00}{-1}) \equiv c_0 - c_1 + \cdots + (-1)^k c_k$$ follows by applying the Polynomial Congruence Rule below.

Similarly $$mod\bmod 7\!:\ \color{#c00}{100\equiv 2}\Rightarrow n = f(\color{#c00}{100})\equiv f(\color{#c00}2)\,$$ where $$ff$$ is its radix $$100100$$ polynomial as above.

[Note  If congruences are unfamiliar then instead see the rules in divisibility form]

Below are the basic congruence rules.  Let $$\rm\ A,B,a,b\,\rm\ A,B,a,b\,$$ be any integers.

Congruence Sum Rule $$\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#90f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#90f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$$

Proof $$\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#90f}{A+B – (a+b)} \rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#90f}{A+B - (a+b)}$$

Congruence Product Rule $$\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{#0a0}{AB\equiv ab}\ \ \ (mod\ m)\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{#0a0}{AB\equiv ab}\ \ \ (mod\ m)$$

Proof $$\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{#0a0}{AB – ab} \rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{#0a0}{AB - ab}$$

Congruence Power Rule $$\rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \ (mod\ m)\ \ \rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \ (mod\ m)\ \$$ for all naturals $$\rm\,n.\rm\,n.$$

Proof $$\ \$$ For $$\rm\,n=0\,\rm\,n=0\,$$ it’s $$\,1\equiv 1\,\,1\equiv 1\,$$ so true. $$\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$$ by the Product Rule, so the result follows by induction on $$\rm\,n.\rm\,n.$$

Congruence Inverse Rule $$\rm \quad\ \color{#c00}{A\equiv a}\ \Rightarrow\ A^{-1}\equiv a^{-1},\ \rm \quad\ \color{#c00}{A\equiv a}\ \Rightarrow\ A^{-1}\equiv a^{-1},\$$ if $$\rm\,A^{-1}\,\rm\,A^{-1}\,$$ exists.

Proof $$\rm\,\ A^{-1} \equiv A^{-1} \color{#c00}a a^{-1}\equiv A^{-1} \color{#c00}A a^{-1} \equiv a^{-1}\rm\,\ A^{-1} \equiv A^{-1} \color{#c00}a a^{-1}\equiv A^{-1} \color{#c00}A a^{-1} \equiv a^{-1}$$ by PR = Product Rule  (note $$\rm\, a^{-1}\rm\, a^{-1}$$ exists by $$\,\rm \color{#c00}aA^{-1}\equiv \color{#c00}AA^{-1}\equiv 1\,\,\rm \color{#c00}aA^{-1}\equiv \color{#c00}AA^{-1}\equiv 1\,$$ by PR).  Alternatively:  if $$\rm\, A^{-1}\equiv b\,\rm\, A^{-1}\equiv b\,$$ then PR
$$\rm\Rightarrow 1\equiv \color{#c00}Ab\equiv \color{#c00}ab\,\rm\Rightarrow 1\equiv \color{#c00}Ab\equiv \color{#c00}ab\,$$ so $$\rm\, {a}^{-1} \equiv b\equiv A^{-1}\,\rm\, {a}^{-1} \equiv b\equiv A^{-1}\,$$ by uniqueness of inverses.

Congruence Quotient Rule  If $$\rm\,(B,n)= 1\,\rm\,(B,n)= 1\,$$ then \rm\!\bmod n\!:\, {\begin{align}\rm A\equiv a\\ \rm B\equiv b\end{align}\,\Rightarrow\, \dfrac{A}B\equiv \dfrac{a}b\:\! \overset{\rm def}\equiv\, ab^{-1}}\rm\!\bmod n\!:\, {\begin{align}\rm A\equiv a\\ \rm B\equiv b\end{align}\,\Rightarrow\, \dfrac{A}B\equiv \dfrac{a}b\:\! \overset{\rm def}\equiv\, ab^{-1}}
Proof $$\ \$$ See this answer, and see here for modular fractions.

Polynomial Congruence Rule $$\ \$$ If $$\rm\,f(x)\,\rm\,f(x)\,$$ is polynomial with integer coefficients then $$\rm\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.\ \rm\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.\$$ Note: this is equivalent to the Factor Theorem.

Proof $$\ \$$ By induction on $$\rm\, n = \rm\, n =$$ degree $$\rm f.\,\rm f.\,$$ Clear if $$\rm\, n = 0.\,\rm\, n = 0.\,$$ Else $$\rm\,f(x) = f(0) + x\,g(x)\,\rm\,f(x) = f(0) + x\,g(x)\,$$ for $$\rm\,g(x)\,\rm\,g(x)\,$$ a polynomial with integer coefficients of degree $$\rm < n.\,\rm < n.\,$$ By induction $$\rm g(A)\equiv g(a)\rm g(A)\equiv g(a)$$ so $$\rm \color{#0a0}{A g(A)\equiv\! a g(a)}\,\rm \color{#0a0}{A g(A)\equiv\! a g(a)}\,$$ by the Product Rule. Hence $$\rm \,f(A) = f(0)+\color{#0a0}{Ag(A)}\equiv f(0)+\color{#0a0}{ag(a)} = f(a)\,\rm \,f(A) = f(0)+\color{#0a0}{Ag(A)}\equiv f(0)+\color{#0a0}{ag(a)} = f(a)\,$$ by the Sum Rule.

Beware  that such rules need not hold true for other operations, e.g.
the exponential analog of above $$\rm A^B\equiv\, a^b\rm A^B\equiv\, a^b$$ is not generally true (unless $$\rm B = b,\,\rm B = b,\,$$ so it follows by the Power Rule, or the Polynomial Rule with $$\rm\,f(x) = x^{\rm b}),\rm\,f(x) = x^{\rm b}),$$ but there is a more limited rule that applies to integer powers - see modular order reduction.