87
$\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$
61
$\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.


[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{#c0f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$

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

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

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{blue}{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.$

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

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

$\endgroup$
  • $\begingroup$ For the proof of the Congruence Power rule, why is $A^{n+1}$≡a$^{n+1}$? $\endgroup$ – committedandroider Feb 13 '15 at 22:49
  • $\begingroup$ @com We applied the Product Rule to the prior two congruences in that proof. $\endgroup$ – Bill Dubuque Feb 13 '15 at 22:51
  • $\begingroup$ And is it for convenience that you leave out the mod m in A≡a mod(m) and B≡b mod(m)? $\endgroup$ – committedandroider Feb 13 '15 at 22:56
  • $\begingroup$ @com No need to keep repeating it when there is only one modulus involved (so no ambiguity). $\endgroup$ – Bill Dubuque Feb 13 '15 at 23:01
  • $\begingroup$ In the proof for the Congruence Product rule, how did you make this inference - m| (A−a) B+a (B−b) from the first two - m|(A - a) and m | (B - b)? $\endgroup$ – committedandroider Feb 13 '15 at 23:11
25
$\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
    $\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 '17 at 22:37
19
$\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$
11
$\begingroup$

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

$\endgroup$
10
$\begingroup$

This not an answer but an interesting other criteria 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$
  • 2
    $\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 '18 at 10:16
8
$\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$
7
$\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$
6
$\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$
  • 1
    $\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 '18 at 10:17
  • $\begingroup$ @RosieF Thanks for the suggestive question, I have supplemented the answer. $\endgroup$ – Yuri Negometyanov Feb 27 '18 at 10:50
2
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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