Let,$D=d_1d_2d_3d_4d_5d_6d_7d_8d_9$ be a nine-digit number consisting of the digits $d_1, . . . ,d_9$,not necessarily all distinct.

Let $E=e_1e_2e_3e_4e_5e_6e_7e_8e_9$ be another nine digit number like D.If we substitute any $e_i$ for the corresponding $d_i$,then it will be divisible by $7$.

Let $F=f_1f_2f_3f_4f_5f_6f_7f_8f_9$ be another nine digit number,with same relation to E as E has to D.We need to prove that,$d_i-f_i$ is divisible by 7.

Any positive integer $D=d_1d_2d_3d_4d_5d_6d_7d_8d_9$  can be expressed $(10^8)d_1+(10^7)d_2+...(10^0)d_9$ . Since 10=3 mod 7, and since it holds that if a=b mod c then $a^n=b^n$  mod c, then D can be expressed much more simply mod 7; that is,$D= 2d_1 +3d_2 +1d_3 -2d_4 -3d_5 -d_6 +2d_7 +3d_8 +d_9$ = x mod 7. Each number in E must make the modified D equal 0 mod 7, so for each $d_i$ , $$e_i = \frac{x+7k}{c}-d_i$$ , where c is the coefficient of $d_i$  and k is an element of {$-2,-1,0,1,2$}. The patient reader should feel free to verify that this makes D = 0 mod 7.

I don't understand why $e_i$ must be equal to $(x+7k)/(c) -d_i$ and why k must be an element of that particular set.I would greatly appreciate it if anyone could explain how they obtain the formula regarding $e_i$ and why k must be in the set {$-2,-1,0,1,2$}. This problem is from the Intermediate Modular Aithmetic section of AoPS. Link given here (scroll down).

  • $\begingroup$ What does the "coefficient of $d_i$" mean? $\endgroup$ – EuYu Dec 1 '13 at 7:55
  • $\begingroup$ @EuYu,sorry that I forgot to add that.When D is written in the form $(10^8)d_1+. . . .+d_9$ and reduced modulo 7,then we get the coefficients $c_i$ for each d_i. $\endgroup$ – rah4927 Dec 1 '13 at 8:03
  • $\begingroup$ So $c_i$ is just $10^\ell$ mod $7$ for some $\ell$? (P.S. It would probably be clearer if you labelled your $d_i$s in reverse order from $0$. i.e. $d_8d_7d_6d_5d_4d_3d_2d_1d_0$. That way each $d_i$ corresponds to $10^i$.) $\endgroup$ – EuYu Dec 1 '13 at 8:07
  • $\begingroup$ I don't know what the link is. Can you post the url into the comments? I'll edit it into the question afterwards. $\endgroup$ – EuYu Dec 1 '13 at 8:13
  • $\begingroup$ @EuYu,thanks for adding the link. $\endgroup$ – rah4927 Dec 1 '13 at 8:28

The stated condition is false. The correct equation should be $$d_i = \frac{x + 7k}{c_i} + e_i\tag{1}$$ Note that the condition of replacing any $d_i$ by $e_i$ and making $D$ divisible by $7$ equates to $$D - 10^{9-i}d_i + 10^{9-i}e_i \equiv x - c_id_i + c_ie_i \equiv 0 \pmod 7$$ This is equivalent to the existence of some integer $k$ such that $$x - c_id_i + c_ie_i + 7k = 0 \implies d_i = \frac{x + 7k}{c_i} + e_i$$ The (incorrect) equation $$c_id_i + c_ie_i = x + 7k$$ implies that $E \equiv x \equiv D \pmod 7$ as stated in the given solution. Letting $$D = 123456789$$ $$E = 442137338$$ produces a counter-example. Each digit of $442137338$ can be substituted into the corresponding position in $123456789$ to produce a number divisible by $7$. However, we have $$123456789 \equiv 1 \neq -1 \equiv 442137338 \pmod 7$$

The full result holds in general though and the idea of the proof holds, albeit with a few necessary corrections. From previously, we have $$c_id_i \equiv x + c_ie_i$$ Summing the above through $i=1,\cdots, 9$ gives $$\sum c_id_i \equiv x \equiv 9x + \sum c_ie_i \equiv 2x + E \pmod 7$$ In other words, this gives $$E \equiv -x \pmod 7\tag{2}$$ Together, equations $(1)$ and $(2)$ will allow you to correct the proof to yield the final result.

  • $\begingroup$ Could you explain the sentence $\sum c_id_i \equiv x \equiv 9x + \sum c_ie_i \equiv 2x + E \pmod 7$ a bit more?I don't understand why x must be congruent to 9x+(sum of $c_ie_i$) $\endgroup$ – rah4927 Dec 1 '13 at 10:14
  • $\begingroup$ $D$ is congruent to $\sum c_id_i$ (by definition) and $D$ is congruent to $x$, hence $x \equiv D \equiv \sum c_id_i$. On the other hand, $c_id_i = x + c_ie_i$. Adding up the equations $9$ equations, one for each $i$, gives $\sum c_id_i = 9x + \sum c_ie_i$. Hence $x \equiv \sum c_id_i \equiv 9x + \sum c_ie_i$. $\endgroup$ – EuYu Dec 1 '13 at 10:27
  • $\begingroup$ ,thanks.Another thing-' This is equivalent to the existence of some integer $k$ such that $$x - c_id_i + c_ie_i + 7k = 0 \implies d_i = \frac{x + 7k}{c_i} + e_i$$'But isn't this also equivalent to the existence of a k such that $x-c_id_i+c_ie_i -7k=0$?Is this correct as well? $\endgroup$ – rah4927 Dec 1 '13 at 10:40
  • $\begingroup$ Well yes, your $k$ is just the negative of my $k$. $\endgroup$ – EuYu Dec 1 '13 at 10:43

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.