3
$\begingroup$

There is a 6 digit number $abcdef$. Given that it is divisible by $7$, show that $abc-def$ is also divisible by $7$.

Attempt at solution: $abcdef=10^5a + 10^4b + ... + f=7x$. Therefore, $7|a, 7|b, ...$. Hence, $abc=7m, def=7n$ and $7(m-n)$ must be divisible by $7$. Q.E.D

I still feel this proof is wrong somewhere. Can someone verify?

$\endgroup$
  • 2
    $\begingroup$ Yeah, that's wrong. You can't infer that $7|a$, $7|b$, etc from $7|10^5a+10^4b+...$ A simpler example: $7|42$, but $7\not | 4$ and $7 \not | 2$ $\endgroup$ – Bram28 May 7 '17 at 18:25
  • $\begingroup$ In general if $x+y$ is divisible by $7$, it does not mean that $x$ and $y$ are each divisible by $7$. $\endgroup$ – angryavian May 7 '17 at 18:25
  • $\begingroup$ Then what is the correct proof? $\endgroup$ – Mainak Roy May 7 '17 at 18:27
  • $\begingroup$ @MainakRoy I would say that you should go back to the drawing board for a bit :) Don't give up so quickly! But as a hint, think about this: why the 'break' right at the 1000 mark? How do 7 and 1000 relate? $\endgroup$ – Bram28 May 7 '17 at 18:28
  • $\begingroup$ Well, I really have no idea about modular arithmetic (and I'm in grade 10...). But I'll have another go at it, using algebraic methods. $\endgroup$ – Mainak Roy May 7 '17 at 18:49
10
$\begingroup$

My first reaction to "If $abcdef$ is divisible by $7$ then $abc-def$ is divisible by $7$" is "really, I had no idea that was true!". Then I'd think well, gee, if that's true then how could that be true and what would it imply. How can I get from $abcdef$ to $abc-def$?

$abcdef = 1000abc + def$ is a start.

and $1000abc + def + (abc - def) = 1000abc + abc = 1001(abc)$

So if $abc - def$ and $abcdef$ are both divisible by $7$ then $abcdef + (abc-def) = 1001(abc)$ is divisble by $7$. Is there any reason why that should be true? Also $def$ could be anything suppose we had $abc - def$ and $1001abc$ are both divisible by seven but we then change $def$ to $deg$ and $abc-deg$ *wasn't divisible by $7$ then $1001abc$ would still be divisible by $7$. How could that be possible?

The answer must have something to do with $1001$. How does that relate to $7$? Does $7$ divide $1001$ or have an interesting remainder. So I divide $1001$ by $7$ and get... $1001=7*143$.

So that's that.

Then I'd put it all together.

If $abcdef = 1000abc + def = 1001abc - (abc - def) = 7*143abc - (abc-def)$.

So $7|abcdef\iff 7|(abc-def)$.

A one line proof.

====

You commented that you don't know anything about modular arithmetic.

Modular arithmetic is the mathematics of remainders. I you are only interested in the remainders of things after dividing by $7$ and you wonder what the remainder of $45*73$ will be you don't have to do $45*73 = 3285$ and $3285\div 7 = 469$ with remainder ... um .... $0.2857 ...\times 7 = 2$. You can think "As far as we are concerned $45$ has remainder $3$ so we might as well say $45$ is $3$ and $73$ is $3$ and so $45*73$ is $3*3$ which equals $9$ which is $2$ as far as we are concerned. (Algebraically, we can justify this as $45*73 = (6*7 + 3)(7*10 + 3) = (7a + 3)(7b + 3) = 7^2ab + 3*7b + 3*7a + 3*3 = 7M + 3*3 = 7M + 9 = 7M + 7 + 2 = 7N + 2$. Where $a=6;b=10;M= 7ab+3a+3b;N=M+1$. But we don't care at all about the actual values of any of those. We only want the remainders.)

So we write $a \equiv b \mod n$ to mean "$a $ and $b$ have the same remainder when divided by $n$". And it's easy to verify: If $A \equiv a \mod n$ and $B \equiv b\mod n$ then $A+B \equiv a+b \mod n$ and $A*B \equiv a*b \mod n$ and $A^k \equiv a^k \mod n$.

So: $1000 \equiv -1 \mod 7$

So $1000k \equiv -k \mod 7$ for any integer.

So $abcdef = 1000abc + def \equiv -abc + def \equiv -(abc-def)\mod 7$

So $abcdef \equiv 0 \mod 7\iff abc-def \equiv 0\mod 7$.

And $k \equiv 0 \mod 7$ means "$k$ has remainder $0$ when divided by $7$" which means $7$ divides into $k$.

$\endgroup$
  • $\begingroup$ Surely "100abc + abc = 1001(abc)" was meant to be "1000abc + abc = 1001(abc)". (I suggested that edit, but apparently multiple moderators rejected it for "deviating from the original intent" and "does not make the post even a little bit ... more accurate".) $\endgroup$ – jamesdlin May 8 '17 at 5:25
  • $\begingroup$ Surely you are correct. $\endgroup$ – fleablood May 8 '17 at 5:34
  • $\begingroup$ How did I not notice that $abcdef = 1000abc + def$?.... Thank you so much! $\endgroup$ – Mainak Roy May 8 '17 at 9:41
4
$\begingroup$

Since $1000\equiv -1\pmod{7}$, we have $$abcdef=1000abc+def\equiv -abc+def\pmod{7}$$ and if the given number is divisible by 7, then by above result $-abc+def$ is divisible by 7.

$\endgroup$
1
$\begingroup$

The proof is wrong. Here's a correct one.

We need the values of $10^n\bmod 7$ for small $n$; from $n=0$ they are 1, 3, 2, 6, 4 and 5. Then $$\overline{abcdef}\equiv0\bmod7$$ $$5a+4b+6c+2d+3e+f\equiv0\bmod7$$ $$-(2a+3b+c)+2d+3e+f\equiv0\bmod7\tag1$$ $$-\overline{abc}+\overline{def}\equiv0\bmod7$$ $$\overline{abc}-\overline{def}\equiv0\bmod7$$ where $(1)$ is because subtracting a multiple of $n$ does not change the residue modulo $n$.

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