# Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$.

Let $m$ be the least positive integer divisible by $17$ whose digits sum to $17$. Find $m$.

$m$ is a 3 digit number (because this was an AIME problem).

$$m \equiv 0 \pmod{17}$$

$$m \equiv 17 \pmod{9} \equiv -1 \pmod{9}$$

Applying the chinese remainder theorem, the solution is supposed to be:

$$m = 17 \cdot 9 = 153$$

but that isnt correct.

• You have not applied the CRT correctly. $153\equiv 0\pmod{9}$. The correct answer to the CRT should be $17$; however this is not the answer to the problem. – vadim123 Apr 24 '15 at 13:42
• Since $17$ is already $-1\mod{9}$, you want to add to it numbers that are multiples of both 17 and 9 until you get the number you want. It doesn't take long. – rogerl Apr 24 '15 at 13:43
• The correct answer is 476 if that helps. – Alexey Burdin Apr 24 '15 at 13:44
• $m\equiv 17\,$ both mod $17$ and $9$ $\iff 17,9\mid m\!-\!17\iff 17\cdot 9\mid m\!-\!17.$ CRT is not needed for that simple case. – Bill Dubuque Apr 24 '15 at 14:23
• $m \equiv 17 \pmod{17}$ is false. It is divisible by $17$? – Lebes Apr 24 '15 at 15:31

Lebes, from your lead and solving for $N$, we have $$N \equiv 0 \pmod{17}\equiv 17 \pmod{17}$$ and from the digit sum condition $$N \equiv 17 \pmod{9}.$$ Since $(17,9)=1$, we have $N\equiv17\pmod{153}$. [This uses principles from the Chinese Remainder Theorem - see the bottom for a detailed explanation]

Since this is only finding solutions where the digitsum $\equiv8\pmod{9}$, we now simply check the first few solutions to find the correct answer:

$1\times 153+17=170\longrightarrow$ digit sum $=8\qquad$Nope.

$2\times 153+17=323\longrightarrow$ digit sum $=8\qquad$Nope. [Fixed the error here]

$3\times 153+17=476\longrightarrow$ digit sum $=17\qquad$Found it!

Therefore $N=476$.

Thanks @AaronMaroja for the correction.

Explanation of the use of CRT for @Amad27:

Using the Chinese Remainder Theorem to solve $N \equiv 0 \pmod{17}$ and $N \equiv 17 \pmod{9} \equiv 8 \pmod{9}$. Breaking these down we get $a_1=0$, $a_2=8$, $m_1=17$, $m_2=9$, $M=m_1\times m_2=153$, $M_1=M/m_1=153/17=9$, $M_2=M/m_2=153/9=17$.

Now applying CRT we get $$M_1y_1\equiv 1\pmod{m_1}\rightarrow 9y_1\equiv 1\pmod{17},$$ and $$M_2y_2\equiv 1\pmod{m_2}\rightarrow 17y_2\equiv 1\pmod{9}\rightarrow 8y_2\equiv 1\pmod{9}.$$ It can be seen by observation that $y_1=2$ and $y_2=8$.

Finally, combining the above information we get $$m=a_1M_1y_1+a_2M_2y_2=0\times9\times2+8\times17\times8=1088.$$ Since $1088\equiv17\pmod{153}$, we have $$N\equiv m\pmod{M}\equiv17\pmod{153}$$

• $2 \dot \, 153 + 17 = 323 \rightarrow$ digit sum $=8$. – Aaron Maroja Apr 24 '15 at 14:58
• How did you use the Chinese remainder theorem there? – Amad27 Apr 24 '15 at 15:14
• @Amad27 I've expanded the above to explain the use of the Chinese Remainder Theorem. – Zac Apr 25 '15 at 4:12
• this answer is overkill. – user26486 Apr 25 '15 at 4:40
• @user31415 I'm just expanding on my previous one-liner on the CRT to fully explain how it comes about, as requested. It was more concise previously. – Zac Apr 25 '15 at 4:47

$\begin{cases}m\equiv 0\equiv 17\pmod {17}\\m\equiv 17\pmod{9}\end{cases}\implies 17, 9\mid m-17\stackrel{(17,9)=1}\implies 153\mid m-17$

So necessarily $m\in\{17,170,323,476,\ldots\}$. After checking $17,170,323,476$ in that order, only $476$ satisfies the sufficient conditions (of digits summing up to $17$). Answer: $476$.

This uses the hint by Bill Dubuque in the comments to op, so this answer is community wiki.