13
$\begingroup$

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.

  • 0
    @Joel: As @wxu pointed out underneath my answer, you can get the residue with just a little extra work by including a factor of $3$ for each step, to cancel the factor of $5$. You can always map the number of these factors to the interval $[-2,3]$, so you only have to memorize the permutation $(326451)$ associated with multiplying by $3$ and take up to $3$ steps in it.2011-06-11

7 Answers 7

23

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

  • 0
    @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.2011-06-10
8

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

  • 4
    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}$.2011-06-10
3

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

3

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.

2

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.

0

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

https://www.youtube.com/watch?v=ZUozMuPE1RA

Silvio Moura Velho

  • 0
    Welcome to MSE! I realize you do not yet have enough re$p$utatio$n$, but this would have been better as a comment or as an update to the snwer you are referring to. Regards2013-04-26
0

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