Congruence Arithmetic Laws, e.g. in divisibility by $7$ test

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 = (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}^{\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 $$n$$. For example, $$Q_{3}^{\prime}(123456789) = 789-456+123=456$$ Proposition: $$7 | n \ \Leftrightarrow \ 7 | Q_{3}^{\prime}(n)$$.

What would be the proof of this?

Thanks for any help.

• Have you tried induction on $n$? Commented Jul 27, 2014 at 3:36
• The problem of induction is that there are several cases to consider. Commented Jul 27, 2014 at 3:38
• Commented Jul 27, 2014 at 4:55

Note $$n = c_0\! + c_1 1000 + \cdots\! + c_k 1000^k\! = f(1000)$$ is a polynomial in $$1000$$ with integer coef's $$\,c_i\,$$ thus $$\,{\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 $$\!\bmod 7\!:\ \color{#c00}{100\equiv 2}\Rightarrow n = f(\color{#c00}{100})\equiv f(\color{#c00}2)\,$$ 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,m\,$$ 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 it follows by induction on $$\rm\,n.\$$ Warning this does not remain true more generally if we analogously also replace the power $$\,\rm n\,$$ by any $$\rm\,N\equiv n\pmod{\! m},\,$$ see "Beware" below.

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}),$$ e.g. $$\rm\!\bmod {\rm prime}\ p\!:\ \color{#c00}{p\equiv 0}\,$$ but $$\rm\,a^{\large\color{#c00} p}\equiv a^{ \color{#c00}0}\!\!\iff\! a\equiv 1,\,$$ by little Fermat. But there is a more limited rule for integer powers - see modular order reduction,

• For the proof of the Congruence Power rule, why is $A^{n+1}$≡a$^{n+1}$? Commented Feb 13, 2015 at 22:49
• @com We applied the Product Rule to the prior two congruences in that proof. Commented Feb 13, 2015 at 22:51
• And is it for convenience that you leave out the mod m in A≡a mod(m) and B≡b mod(m)? Commented Feb 13, 2015 at 22:56
• @com No need to keep repeating it when there is only one modulus involved (so no ambiguity). Commented Feb 13, 2015 at 23:01
• @Jim By hypothesis both summand $\,A-a\,$ and $\,B-b\,$ are multiples of $m$ hence so too is their sum, since multiples are closed under integral linear combinations. Commented Jul 7, 2021 at 15:23

Since $1001=143\cdot7$ it follows that $1000^k=(-1)^k$ modulo $7$ $(k\geq0)$. From this we can deduce that $$\sum_{k\geq0}^n a_k\>1000^k=\sum_{k\geq0}(-1)^k a_k\quad({\rm modulo}\ 7)\ .$$

• So, you have really proved that "alternating sum of the digits of third orde of $n$" is equivalent $\mod 1001$ to $n$. And since 7 (and 13 and 11) are factors of 1001 the equivalence is also$\mod 7$ (and$\mod 11$ and$\mod 13$)
– Χpẘ
Commented May 2, 2017 at 22:37

$$\quad{13\times7\times 11=1001\\A= \overline{...a_4a_3a_2a_1a_0}\\A=a_0+10a_1+100a_2+1000a_3+10000a_4+100000a_5+10^6a_6+...=\\(a_0+10a_1+100a_2)+(1000a_3+10000a_4+10^5a_5)+(10^6a_6+10^7a_7+10^8a_8)+...\\=(a_0+10a_1+100a_2)+1000(a_3+10a_4+100a_5)+1000^2(a_6+10a_7+100a_8)+...\\(\overline{a_2a_1a_0})+1000(\overline{a_5a_4a_3})+1000^2(\overline{a_8a_7a_6})+...\\(\overline{a_2a_1a_0})+(1001-1)(\overline{a_5a_4a_3})+(1001-1)^2(\overline{a_8a_7a_6})+...=\\(\overline{a_2a_1a_0})+(7k-1)(\overline{a_5a_4a_3})+(7q-1)^2(\overline{a_8a_7a_6})+...=\\(\overline{a_2a_1a_0})-1(\overline{a_5a_4a_3})+1(\overline{a_8a_7a_6})+...+\overbrace{7k+7q+...}^{7q'}\\ }$$so if A divided by 7 $$\quad{A = \space (\overline{a_2a_1a_0})-1(\overline{a_5a_4a_3})+1(\overline{a_8a_7a_6})+...+\overbrace{7k+7q+...}^{7q'}\\A-7Q=(\overline{a_2a_1a_0})-1(\overline{a_5a_4a_3})+1(\overline{a_8a_7a_6})+...}$$

Hint. $10^{6k}-1 \equiv 10^{6k - 3}+1 \equiv 0 \pmod{7}$.

This not an answer but an interesting other criterion for divisibility by 7

Consider $$n\in\mathbb{N}$$ and divide it by $$10$$ :

$$n=10q+r\qquad\mathrm{with}\,0\le r<10$$

Then we have :

$$7\mid n\Leftrightarrow 7\mid q-2r$$

The proof is very easy :

• Suppose $$7\mid n$$. We have $$n=7k$$ for some nonnegative integer $$k$$. Then $$q-2r=q-2(n-10q)=21q-2n=7(3q-2k)$$.

• Conversely, suppose $$7\mid q-2r$$. We have $$q-2r=7K$$ for some nonnegative integer $$K$$. Then $$n=10(q-2r)+21r=7(10K+3r)$$

This criteria has to be combined with iteration to show all its power ... Here is an example :

For $$n=22925$$, we compute $$q=2292$$, $$r=5$$ and $$q-2r=2282$$

For $$n=2282$$, we compute $$q=228$$, $$r=2$$ and $$q-2r=224$$

For $$n=224$$, we compute $$q=22$$, $$r=4$$ and $$q-2r=14$$

Since $$7\mid14$$ and by applying three times the above criteria, we conclude that $$7\mid22925$$.

• The pertinent fact here is that $7\mid 21$. The method correctly shows whether or not 7 divides a given integer $n$. Unfortunately, it doesn't determine $n\bmod 7$ except when this is 0. Commented Feb 27, 2018 at 10:16

I think this method can by reduced using three coefficients $(1, 2, 3)$ to know if a number is a multiple of seven or not. We multiply the last number by $1$, the second from the right by $3$, and finally by $2$. Then next three digits by $(-1, -3, -2)$ and again by positive. For example:

$123456789$

$1 \cdot 9 + 3 \cdot 8 + 2 \cdot 7 -1 \cdot 6 -3 \cdot 5 -2 \cdot 4 + 1 \cdot 3 + 3 \cdot 2 + 2 \cdot 1 =$

$=47 - 29 + 11 = 29$

Number $29$ is not divisible by $7$, so is the number $123456789$

However I personally prefer simple formula:

$3 \times F + L$

$L$ - last digit

$F$ - everything in front of last digit.

So the number $105$ can be written as: $3 \cdot 10 + 5=35$ which is divisible by $7$, so is the number $105$.

Hope, that will help a bit.

For some simple insight:

Take some number $k<1000$. Now clearly $k$ has some remainder $r$ (which may be $0$) when divided by $7$. Or, to say the same thing, $7$ divides $k-r$.

What happens when we multiply $k$ by $1000$?

• We know that $7$ divides $1001$ and $7$ divides $k-r$ so $7$ divides $1001k - (k-r)$ $= 1000k - (-r)$. So we can say that $-r$ is the remainder of $1000k$ divided by $7$. (To get a positive remainder, just take $7-r$).

What happens when we multiply $k$ by $1000000$?

• We know that $7$ divides $1001$ and $7$ divides $1000k- (-r)$ so $7$ divides $1001\cdot 1000k - (1000k- (-r))$ $= 1000000k - r$. So we are back to $r$ as the remainder.

To get this proven properly requires modular arithmetic, or a couple of induction steps, but even so the pattern is apparent; each time we multiply by $1000$, the remainder from division by $7$ reverses sign. Which means we can go a little further than the original claim; we can not merely find divisibility by $7$ by looking at the alternating sum of third order, but also the remainder if the number is not evenly divisible by $7$.

In octal notation, the criterion of divisibility by $7$ is similar to the criterion of divisibility by $9$ in the decimal: if the sum of the octal digits of the number is divided by $7$, then the number itself is also. For example, $$1001_{10} = 1751_{8} \rightarrow 1_8 + 7_8 + 5_8 + 1_8 = 16_8 \rightarrow 1_8 + 6_8 = 7_8 \vdots 7.$$

In this form, the criterion can be used to control the moment of transition from a fixed number format to floating in programming languages with a non-strict typing of data.

• But if you're prepared to find the base-8 representation of your given number, why not find its base-7 representation instead? And you only need the last digit of that. Commented Feb 27, 2018 at 10:17
• @RosieF Thanks for the suggestive question, I have supplemented the answer. Commented Feb 27, 2018 at 10:50

Note that $1001$ is divisible by $7$, hence, $1000 \equiv -1 (\bmod 7)$.

Let, $n = a_0 + 10^1a_1+\ldots +10^ka_k$.

Partition $(a_0,\ldots,a_k)$ into groups of three to get $$n=\sum_{i=0}10^{3i}(a_i+10^1a_{i+1}+10^2a_{i+2})\equiv\sum_{i=0}(-1)^{i}(a_i+10^1a_{i + 1}+10^2a_{i + 2}) (\bmod 7)$$

And that is exactly what we were trying to prove.