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$
3
  • $\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, 2015 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, 2015 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, 2015 at 22:35

4 Answers 4

Reset to default
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$
0
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .