8
$\begingroup$

Let $b = a_5a_4a_3a_2a_1a_0$ integer that has a maximum of six digits.

Here we have: if $b$ is a five-digit number, then $a_5 = 0$; if $b$ is a four-digit number , then $a_5$, $a_4 = 0$, and so on. Prove that

  • $$ b \equiv a_0 - a_3 + 3 (a_1 - a_4) + 2 (a_2 - a_5) \pmod 7 $$
  • $$ 10^6 \equiv 1 \pmod 7$$

From this derive the criterion of divisibility of an integer number $7$.

Can anyone help me with this?

I know that to determine if a number is divisible by $7$, take the last digit off the number, double it and subtract the doubled number from the remaining number. If the result is evenly divisible by $7$ (e.g. $14, 7, 0, -7$, etc.), then the number is divisible by seven.

$\endgroup$
  • $\begingroup$ Your divisibility check involving the last digit is correct but is not the point of the problem. It maintains divisibility by $7$ but does not maintain the remainder for numbers not divisible by $7$, so it will tell you whether a number is divisible by $7$ but not (without some further work) the remainder for numbers not divisible by $7$ $\endgroup$ – Ross Millikan Dec 26 '15 at 22:27
  • $\begingroup$ Let $n=10a+b$. Suppose $7r=a-2b$, then we have $n=10(7r+2b)+b=7(10r+3b)$. Do u mean like this? @RossMillikan $\endgroup$ – mod Dec 26 '15 at 22:31
  • $\begingroup$ Yes, but you divide by $10$ each step which changes the remainder. If $n=182$, which is divisible by $7$, you go to $14$, which still is. But if $n=184$, which has remainder $2$ on division by $7$, you go to $10$ which has remainder $3$. The rule in your question results in the same remainder as $b=4+3\cdot 8 + 2 \cdot 1=30$, which has remainder $2$ as does $184$ $\endgroup$ – Ross Millikan Dec 26 '15 at 22:35
8
$\begingroup$

Rewrite $b$ as

$$a_0 + 10^1a_1 + 10^2 a_2+ \dots+ 10^5 a^5$$

If you worked out $10^0, 10^1, 10^2, \dots, 10^5 \pmod 7$ for $a_0,a_1,\dots,a_5$ respectively, you'll get exactly the required coefficients.


The $10^6 \equiv 1 \pmod 7$ is there to indicate that the coefficients will repeat after every $6$ terms.

$\endgroup$
2
$\begingroup$

As $10^3\equiv-1\pmod7$

$$\sum_{r=0}^{3n-1}(10^{3r}a_{3r}+10^{3r+1}a_{3r+1}+10^{3r+2}a_{3r+2})\equiv\sum_{r=0}^{3n-1}(-1)^ra_{3r}a_{3r+1}a_{3r+2}\pmod7$$


OR

As $7\cdot3-10\cdot2=1,$

Use the reduction formula : $$21x-2(10x+y)\equiv x-2y\pmod7$$ for $10x+y$ recursively

$\endgroup$
0
$\begingroup$

Note that $1001=7\times 11 \times 13$ so subtracting $1001 \times (100a_6+10a_5+a_4)$ gives $100(a_2-a_5)+10(a_1-a_4)+(a_0-a_3)$ divisible by $7$.

Now we note that $98$ and $7$ are divisible by $7$ to reduce to $2(a_2-a_5)+3(a_1-a_4)+(a_0-a_3)$ as differing from the original number by a multiple of $7$.

Others have written n more technical ways. This is how I would approach the problem in practice - not needing to remember a formula, but having a working method to hand. A formula is handy for a computer or a calculator.

$\endgroup$
0
$\begingroup$

Your method of removing the last number, doubling, and subtracting from the remainder is a way of determining that a number is divisible by 7 but it is not the only way. I had never seen your way before but it is slick and easy to remember. Its drawback is that it only tells you whether or not a number is divisible by 7. If the number isn't divisible by 7 (and 6 out of 7 numbers will not be) then the test doesn't tell you what numbers are.

This problem's test is entirely different. For a six digit number, $a_5a_4a_3a_2a_1a_0$ will have the same remainder as $a_0 - a_3 + 3 (a_1 - a_4) + 2 (a_2 - a_5)$. The number will be divisible by 7 if and only if $a_0 - a_3 + 3 (a_1 - a_4) + 2 (a_2 - a_5)$ has remainder $0$. If $a_0 - a_3 + 3 (a_1 - a_4) + 2 (a_2 - a_5)$ has remainder, $m$, then $a_5a_4a_3a_2a_1a_0$ will be also have remainder $m$ and will $m$ larger than a multiple of 7.

The proof is easy.

$b = \sum_{i=0}^5 10^ia_i \equiv a_0 - a_3 + 3 (a_1 - a_4) + 2 (a_2 - a_5) \mod 7 \iff$

$\sum_{i=0}^5 10^ia_i -(a_0 - a_3 + 3 (a_1 - a_4) + 2 (a_2 - a_5)) \equiv 0 \mod 7 \iff$

$(10^5 + 2)a_5 + (10^4 + 3)a_4 + (10^3 + 1)a_3 + (10^2 - 2)a_2 + 7a_1 \equiv 0 \mod 7 \iff$

$100002a_5 + 10003a_4 + 1001a_3 + 98a_2 + 7a_1 \equiv 0 \mod 7 \iff$

$100002a_5 + 10003a_4 + 1001a_3 + 98a_2 + 7a_1 \equiv 0 \mod 7 \iff$

As 7 divides 100002, 10003, 1001, 98, and 7 this is true.

$10^6 = 1 \mod 7$ is a result of Fermat's little theorem that as gcd(10,7) = 1 $10^{7-1} \equiv 1 \mod 7$.

If you don't know Fermat's little theorem, this can be shown to be true by noting that:

$10^6 - 1 = (10^3 -1)(10^3 + 1) = (10-1)(10^2 + 10 + 1)(10 + 1)(10^2 - 10 + 1) = 9*111*11*91$ and noting $7|91$ so $7|10^6 - 1$ so $10^6 \equiv 1 \mod 7$.

We can extend this result to numbers larger than 6 digits by noting

$B = \sum_{i=0}^n10^ia_i = \sum_{i=0}^m{10^{6i}}(\sum_{l=0}^510^la_l \equiv \sum_{i=0}^m(-1)^i(a_{6i} - a_{6i+3} + 3 (a_{6i +1} - a_{6i+4}) + 2 (a_{6i+2} - a_{6i+5}) \mod 7$.

(In other words, do the above in groups of 6 digits.)

I am utterly certain the point of the exercise was NOT to discover a new divisibility test. I have utterly no intention of remembering this test or ever using it again.

====

Addendum: So why does your test work.

$B =\sum_{i=0n}^n10^ia_i \equiv 0 \mod 7 \iff$

$\sum_{i=1}^n10^ia_i \equiv -a_0 \mod 7 \iff$

$10\sum_{i=1}^n10^{i-1}a_i \equiv -a_0 \mod 7 \iff$

$50\sum_{i=1}^n10^{i-1}a_i \equiv -5a_0 \mod 7 \iff$

$\sum_{i=1}^n10^{i-1}a_i \equiv -5a_0 \mod 7 \iff$

$\sum_{i=1}^n10^{i-1}a_i \equiv 2a_0 \mod 7 \iff$

$\sum_{i=1}^n10^{i-1}a_i - 2a_0\equiv 0 \mod 7 \iff$

$\lfloor B/10 \rfloor - 2a_0\equiv 0 \mod 7 \iff$

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