Divisibility rule of 7

Prove that a positive integer is divisible by 7 if and only if the integer obtained by alternately adding and subtracting the three digit integers formed from the successive blocks of three decimal digits beginning with adding the block containing the units digit and working to the left is divisible by 7.

I tried using $10\equiv 3\pmod 7$ like the other divisibility rule proofs, but I don't think it works the same way for 7. A hint given in the book says 1001=(7)(11)(13)

• $1 \equiv 1 \pmod {7}.$ $1000 \equiv -1 \pmod {7}.$ $1000000 \equiv 1 \pmod {7}.$ $1000000000 \equiv -1 \pmod {7}.$ – Will Jagy Sep 28 '16 at 0:21
• @DERPYPENGUIN "if the integer obtained by alternately adding and subtracting the three digit integers formed from the successive blocks of three decimal digits beginning with adding the block containing the units digit and working to the left is divisible by 3." = HEADACHE... can you provide an example please? – the_candyman Sep 28 '16 at 0:25
• Another manner: All integer $N$ can be written as $$N=\sum_{k=0}^n a_k7^k$$ where $a_k\in \{0,1,2,3,4,5,6\}$ (representation of $N$ in base $7$). This way you have $$N\text{ divisible by }\space 7\iff a_0=0$$. – Piquito Sep 28 '16 at 0:42
• – lab bhattacharjee Sep 28 '16 at 4:52

Let $$b=\overline{a_1a_2....a_n}$$ be an n-digit number. We can break $$b$$ into parts, as follows: $$b= \overline{a_{n-2}a_{n-1}a_{n}} + 1000(\overline{a_{n-5}a_{n-4}a_{n-3}}) + 1000000(\overline{a_{n-8}a_{n-7}a_{n-6}}) + \ldots$$

Al you do now, is note that $$1001=7 \times 143$$ and $$999999=7 \times 142857$$. Similarly, you can prove that $$10^{6n+3} \equiv -1 \mod 7$$ (which means that $$10^{6n+3}$$ leaves a remainder of $$-1$$ (or $$6$$) when divided by $$7$$) and $$10^{6n} \equiv 1 \mod 7$$. Thus, when we take remainders above: $$b \equiv \overline{a_{n-2}a_{n-1}a_{n}} + (-1)(\overline{a_{n-5}a_{n-4}a_{n-3}}) + (1)(\overline{a_{n-8}a_{n-7}a_{n-6}}) + \ldots \mod 7$$

Thus, you can see where the pattern comes from. I'll leave the rigorous details to you.

By the way, I have simpler rule for division by $$7$$:

Take your number $$\overline{a_1a_2\ldots a_n}$$, remove the digit $$a_n$$, subtract $$2a_n$$ from the rest of the number namely $$\overline{a_1a_2\ldots a_{n-1}}$$. repeat this until you get a small number. If this number is divisible by $$7$$, then your number is divisible by $$7$$.

Note: instead of subtracting $$2a_n$$, we can even add $$5a_n$$, and the result remains.

I will leave it to you to test this method out and to prove it.

Instead of divisible by $3$ it should be divisible by $7$. The hint means that if you have $123456789=123 \cdot 10^6 + 456 \cdot 10^3 + 789 \cdot 1$ you can use that $10^6 \equiv 1 \pmod 7$ and $10^3 \equiv -1 \pmod 7$ to write $123456789=123 \cdot 10^6 + 456 \cdot 10^3 + 789 \cdot 1\equiv 123 + 456(-1) + 789 \pmod 7$