# An intermediate Modular Arithmetic exercise from AoPS

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).

• What does the "coefficient of $d_i$" mean? – EuYu Dec 1 '13 at 7:55
• @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. – rah4927 Dec 1 '13 at 8:03
• 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$.) – EuYu Dec 1 '13 at 8:07
• I don't know what the link is. Can you post the url into the comments? I'll edit it into the question afterwards. – EuYu Dec 1 '13 at 8:13
• @EuYu,thanks for adding the link. – rah4927 Dec 1 '13 at 8:28

## 1 Answer

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.

• 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$) – rah4927 Dec 1 '13 at 10:14
• $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$. – EuYu Dec 1 '13 at 10:27
• ,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? – rah4927 Dec 1 '13 at 10:40
• Well yes, your $k$ is just the negative of my $k$. – EuYu Dec 1 '13 at 10:43