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.

  • $\begingroup$ 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. $\endgroup$ – vadim123 Apr 24 '15 at 13:42
  • 3
    $\begingroup$ 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. $\endgroup$ – rogerl Apr 24 '15 at 13:43
  • 1
    $\begingroup$ The correct answer is 476 if that helps. $\endgroup$ – Alexey Burdin Apr 24 '15 at 13:44
  • $\begingroup$ $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. $\endgroup$ – Bill Dubuque Apr 24 '15 at 14:23
  • $\begingroup$ $m \equiv 17 \pmod{17}$ is false. It is divisible by $17$? $\endgroup$ – 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}$$

  • $\begingroup$ $2 \dot \, 153 + 17 = 323 \rightarrow $ digit sum $=8$. $\endgroup$ – Aaron Maroja Apr 24 '15 at 14:58
  • $\begingroup$ How did you use the Chinese remainder theorem there? $\endgroup$ – Amad27 Apr 24 '15 at 15:14
  • $\begingroup$ @Amad27 I've expanded the above to explain the use of the Chinese Remainder Theorem. $\endgroup$ – Zac Apr 25 '15 at 4:12
  • $\begingroup$ this answer is overkill. $\endgroup$ – user26486 Apr 25 '15 at 4:40
  • $\begingroup$ @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. $\endgroup$ – 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.


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.