98
$\begingroup$

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

proof. ??

Thanks for any help.

$\endgroup$
3

9 Answers 9

69
$\begingroup$

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

$\endgroup$
13
  • 1
    $\begingroup$ For the proof of the Congruence Power rule, why is $A^{n+1}$≡a$^{n+1}$? $\endgroup$ Feb 13, 2015 at 22:49
  • 1
    $\begingroup$ @com We applied the Product Rule to the prior two congruences in that proof. $\endgroup$ Feb 13, 2015 at 22:51
  • 2
    $\begingroup$ And is it for convenience that you leave out the mod m in A≡a mod(m) and B≡b mod(m)? $\endgroup$ Feb 13, 2015 at 22:56
  • 1
    $\begingroup$ @com No need to keep repeating it when there is only one modulus involved (so no ambiguity). $\endgroup$ Feb 13, 2015 at 23:01
  • 2
    $\begingroup$ @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. $\endgroup$ Jul 7, 2021 at 15:23
27
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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$) $\endgroup$
    – Χpẘ
    May 2, 2017 at 22:37
25
$\begingroup$

$$ \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})+...}$$

$\endgroup$
17
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Rosie F
    Feb 27, 2018 at 10:16
11
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Rosie F
    Feb 27, 2018 at 10:17
  • 1
    $\begingroup$ @RosieF Thanks for the suggestive question, I have supplemented the answer. $\endgroup$ Feb 27, 2018 at 10:50
5
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.