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=(akak1a2a1a0)10=kj=0akj10kj. The expression
Q3(n)=(a2a1a0)10(a5a4a3)10+(a8a7a6)10
are called alternating sum of the digits of third order of n. For example,
Q3(123456789)=789456+123=456
Proposition: 7|n  7|Q3(n).

proof. ??

Thanks for any help.

Answer

Note n=c0+c11000++ck1000k=f(1000) is a polynomial in 1000 with integer coef’s ci thus mod 7: 1000103331n=f(1000)f(1)c0c1++(1)kck follows by applying the Polynomial Congruence Rule below.

Similarly mod where f is its radix 100 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\, 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)

Proof \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)

Proof \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)\ \ for all naturals \rm\,n.

Proof \ For \rm\,n=0\, it’s \,1\equiv 1\, so true. \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.

Congruence Inverse Rule \rm \quad\ \color{#c00}{A\equiv a}\ \Rightarrow\ A^{-1}\equiv a^{-1},\ if \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} by PR = Product Rule (note \rm\, a^{-1} exists by \,\rm \color{#c00}aA^{-1}\equiv \color{#c00}AA^{-1}\equiv 1\, by PR). Alternatively: if \rm\, A^{-1}\equiv b\, then PR
\rm\Rightarrow 1\equiv \color{#c00}Ab\equiv \color{#c00}ab\, so \rm\, {a}^{-1} \equiv b\equiv A^{-1}\, by uniqueness of inverses.

Congruence Quotient Rule If \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}}
Proof \ See this answer, and see here for modular fractions.

Polynomial Congruence Rule \ If \rm\,f(x)\, is polynomial with integer coefficients then \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 = degree \rm f.\, Clear if \rm\, n = 0.\, Else \rm\,f(x) = f(0) + x\,g(x)\, for \rm\,g(x)\, a polynomial with integer coefficients of degree \rm < n.\, By induction \rm g(A)\equiv g(a) so \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)\, 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 is not generally true (unless \rm B = b,\, so it follows by the Power Rule, or the Polynomial Rule with \rm\,f(x) = x^{\rm b}), but there is a more limited rule that applies to integer powers - see modular order reduction.

Attribution
Source : Link , Question Author : Mathsource , Answer Author : Bill Dubuque

Leave a Comment