# Proof for divisibility by $7$

One very classic story about divisibility is something like this.

A number is divisible by $2^n$ if the last $n$-digit of the number is divisible by $2^n$. A number is divisible by 3 (resp., by 9) if the sum of its digit is divisible by 3 (resp., by 9). A number $\overline{a_1a_2\ldots a_n}$ is divisible by 7 if $\overline{a_1a_2\ldots a_{n-1}} - 2\times a_n$ is divisible by 7 too.

The first two statements are very well known and quite easy to prove. However I could not find the way on proving the third statement.

PS: $\overline{a_1a_2\ldots a_n}$ means the digits of the number itself, not to be confused with multiplication of number.

-
There is also a similar less known trick for divisibility by 11. Since $10 = -1 \mod 11$, if you add the digits of a number in reverse order, alternating signs, and get something that is divisible by 11, then your original number is divisible by 11. For example for $1617$ you have $7-1+6-1 = 11$ so $1617$ is divisible by $11$. –  Vhailor Jun 10 '11 at 0:06
@Vhailor: I have heard about this too... Anyway, I dont think that reversing it is really needed. $1-6+1-7=-11$ :) –  zfm Jun 10 '11 at 0:15
This is so incredibly ironic: I was just recalling the "tricks" I learned for checking whether an integer is divisible by 3, 7, ...and spent time earlier today proving those claims! @Vhailor: 11 is new to me...thanks! –  amWhy Jun 10 '11 at 0:50
A small remark : for $2^n$, $3$, $9$ and $11$, those criteria also gives you a way to compute the residue when the number is not divisible (meaning $\overline{a_1 \cdots a_n} \equiv a_1 + \ldots + a_n \mod 9$, $\overline{a_1 \cdots a_n} \equiv a_n \mod 2$ ...). But the criterion for $7$ does NOT give you the residue (you only have $\overline{a_1 \cdots a_{n-1}}-2a_n \equiv 5 \overline{a_1 \cdots a_n} \mod 7$ so each step multiplies the residue by $5$). –  Joel Cohen Jun 10 '11 at 2:00
And if you work with slightly larger number, then starting from the fact that $1001=7\cdot1\cdot13$ we get that $1000\equiv -1\pmod p$ for $p=7,11,13$. This allows a speed up in the sense that you can reduce the number of digits by 3 at a time (early on). So for example $166145\equiv-166+145=-21\equiv0\pmod 7$ and $777751130\equiv -777751+130\equiv777-751+130=-26+130\equiv0\pmod{13}.$ –  Jyrki Lahtonen Jun 10 '11 at 3:49

$$5(\overline{a_1a_2\ldots a_n})=50(\overline{a_1a_2\ldots a_{n-1}})+5a_n=\overline{a_1a_2\ldots a_{n-1}}-2a_n\pmod{7}$$

-
So, 5 is the trick. –  zfm Jun 10 '11 at 0:08
@zfm : Yes, the trick relies on $5*10 \equiv 1 \mod 7$. Similarly, you could use the same idea to derive a criterion of divisibility by $11$ (using $(-1)*10 \equiv 1 \mod 11$), $13$ (using $4*10 \equiv 1 \mod 13$), or any prime number $p \ge 7$. –  Joel Cohen Jun 10 '11 at 1:45
Nice! Why do we not multiply 15? Then we get the remainder modulo 7. I mean 1998=3*(199-16)=3*183=9*(18-6)=2*5=3. mod 7. –  wxu Jun 10 '11 at 8:41
@wxu: If you want the remainder mod $7$, you can do it that way. But if you just want to test for divisibility, you don't need the multiplications by $3$, so it's slightly easier the other way. –  joriki Jun 10 '11 at 9:23

Let $x$ be the number you gave, with the full $n$ digits, and let $y$ be the number whose decimal representation is obtained by removing the last digit, namely $a_n$, of $x$.

The following equation is clear: $$x=10y +a_n.$$

Note that $10y +a_n$ is divisible by $7$ iff $20y+2a_n$ is divisible by $7$.

But $20y+2a_n$ is divisible by $7$ iff $-y+2a_n$ is divisible by $7$ (I subtracted $21y$), and this is the case if and only if $y-2a_n$ is divisible by $7$. That's exactly what we wanted to show.

We can write the above stuff using the language of congruences if we wish.

About iff: I slipped into jargon. The word (?) "iff" abbreviates "if and only if."

-
Note that this is essentially the same as my answer, since the number is being multiplied by $-2$ instead of $5$, and $-2=5\pmod{7}$. –  joriki Jun 10 '11 at 0:20

HINT $\rm\qquad 7\ |\ 10\ y + x\ \iff\ 7\ |\ y-2\ x\ \ \:$ since $\rm\:\ -2\ (10\ y + x)\ \equiv\ y - 2\ x\ \ (mod\ 7)$

i.e. lines $\rm\ -10\ y = x\$ and $\rm\ y = 2\ x\$ are equivalent over $\rm\:\mathbb Z/7\:,$ differing by a unit scaling (of $2$).

-

Regarding divisibility by 7 I created an algorithm that must be applied repetitively to each period of a large number. If the last sum results in a multiple of 7 then the tested number is also a multiple of 7, otherwise it is not. The sum of each period must be added to the sum of the next period.

N = abc

algorithm: – ( (x) + a + b + c + (y) ) mod 7

(x) must be mentally inserted before the hundreds and (y) must be mentally inserted after the ones in such a way that 7 divides both (x)a and c(y). In this rule no digits are inserted before or after the tens.

Numerical examples:

1) N = 462; – ( (1) + 4 + 6 + 2 + (1) ) mod 7 ≡ Ø

2) N = 863; – ( (2) + 8 + 6 + 3 + (5) ) mod 7 ≡ 4

3) N = 1.554; – ( 1 + (4) ) mod 7 ≡ 2; – ( 2 + (3) + 5 + 5 + 4 + (2) ) mod 7 ≡ Ø

4) N = 68.318; – ( 6 + 8 + (4) ) mod 7 ≡ 3; – ( 3 + (6) + 3 + 1 + 8 +(4) ) mod 7 ≡ 3

5) N = 852.655; – ( (2) + 8 + 5 + 2 + (1) ) mod 7 ≡ 3; – ( 3 + (5) + 6 + 5 + 5 + (6) ) mod 7 ≡ 5

To determine the remainder take the digit that forms with the last sum a multiple of 7. Remainders of the second, fourth and fifth examples:

2) Last sum is 4 → 4(2); 2 is the remainder 4) Last sum is 3 → 3(5); 5 is the remainder 5) Last sum is 5 → 5(6); 6 is the remainder

The application of this rule must be performed in a dynamic way. It is not necessary to write the inserted numbers; all you need is to add the written numbers and the mentally inserted numbers at sight, determine the difference of each sum and its next multiple of 7 (inverse additive) and go ahead till the value of the last inserted digit is added.

The bureaucratic application of the algorithm certainly will not be as quick as its dynamic application.

The rule works because before the use of the inverse additive the values of the digits of the first three digits are multiplied respectively by 3, 1 and 5; after the inverse additive the multipliers change to 4, 6 and 2. Each group of 6 digits of a number are multiplied by 4,6,2,3,1 and 5. These are the remainders determined by Pascal’s criterion regarding divisibility by 7.

In my blogspot I explain how easy is to create new real rules for divisibility by 7 and other aspects of my research. This is the first real rule for divisibility by 7 created by me.

English is not my native language and I am not a Mathematician.

-

To complete my last answer I ask you to watch this video:

Silvio Moura Velho

-
Welcome to MSE! I realize you do not yet have enough reputation, but this would have been better as a comment or as an update to the snwer you are referring to. Regards –  Amzoti Apr 26 '13 at 15:48

The reason why this formula works is because $21$ is a multiple of $7$ which ends in $1$. Thus, $21a_n$ is always multiple of $7$.

Then

$$7| \overline{a_1...a_n} \Leftrightarrow 7| \overline{a_1...a_n}-21 a_n \Leftrightarrow 7| \overline{a_1...a_{n-1}0}-20 a_n \Leftrightarrow 7| 10 \cdot[ \overline{a_1...a_{n-1}}-2 a_n] \,.$$

Since $gcd(7, 10)=1$ you get the desired result.

Comment 1 Same way you can get a criteria of divisibility for any number $m$ so that $gcd(m,10)=1$. If this is the case, $m$ has a multiple of the form $10k+1$ and then, you can prove that

$$m| \overline{a_1...a_n} \Leftrightarrow m| \overline{a_1...a_{n-1}}-ka_n$$

Comment 2 You can instead look for multiples of $7$ (or $m$)which end in $9$ and add instead of subtraction.

Since $7|49$ we get that

$7| \overline{a_1...a_n} \Leftrightarrow 7| \overline{a_1...a_n}+49 a_n \Leftrightarrow 7| \overline{a_1...a_{n-1}0}+50 a_n \Leftrightarrow 7| 10 \cdot[ \overline{a_1...a_{n-1}}+5 a_n] \,.$$- I'm taking the title of the question to allow general tests for divisibility by 7 even though the specifics of the original question is about a particular test. Apologies if this is not right - I'm still fairly new to mse. [Source for this answer is The Lore of Large Numbers, by P. Davis, p. 87-88] A number is divisible by 7 if and only if: (3 * units' digit) + (2 * tens' digit) - (1 * hundreds' digit) - (3 * thousands' digit) - (2 * ten thousands' digit) + (1 * hundred thousands' digit) is divisible by 7. If there are more digits present, the sequence of multipliers 3, 2, -1, -3, -2, 1 is repeated as often as necessary. If fewer digits are present, stop when get to the last multiplier. Example:$$7 * 457404 = 3201828 \begin{array} &3 & * & 8 & = & 24 \\ 2 & * & 2 & = & 4 \\ -1 & * & 8 & = &-8 \\ -3 & * & 1 & = &-3 \\ -2 & * & 0 & = &0 \\ 1 & * & 2 & = &2 \\ 3 & * & 3 & = & 9 \\ \end{array} $$Since 24 + 4 - 8 - 3 + 0 + 2 + 9 = 28 and 7 divides 28, 3201828 is divisible by 7. Proof for 3 digit numbers$$N = 100a + 10b + c,$$then if S is the sum required by the test,$$S = -a + 2b + 3c.$$Then 2S = -2a + 4b + 6c and N + 2S = 98a + 14b + 7c = 7(14a + 2b + c). The sum N + 2S is therefore a multiple of 7, say 7M. Now if N is a multiple of 7, say 7P, then 2S = 7M - 7P = 7(M - P). Since therefore 2S is divisible by 7 and S is whole, S also is divisible by 7 (or S = \frac{7X}{2}, where X is even because S is whole). Conversely, if S is a multiple of 7, say 7Q, then$$N = 7M - 14Q = 7(M - 2Q).$$This means that$N$must be a multiple of$7$. Yet another way to do it is to use a similar alternating sum test as for divisibility by 11, but in 3 digit groups, subtracting first, with the sum's divisibility by 7 determining the original number's divisibility by 7. In the$3201828$example, this is$828 - 201 + 3 = 630,$so since$630$is divisible by$7$, so is$3201828\$. I got this from http://mathforum.org/k12/mathtips/ward2.html.

-