# Find the smallest positive integer that ends in $17$, is divisible by $17$, and the sum of its digits is equal to $17$.

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with primes and composities but other than that, the textbook gave no hints really and I'm really not sure about how to approach it. Any guidance hints or help would be truly greatly appreciated. Thanks in advance :) So anyway, here the problem goes:

Find the smallest positive integer that ends in $17$, is divisible by $17$, and the sum of its digits is equal to $17$.

• 15317 is such a number. Is it the smallest ? Can you take a hint from here and work further. Jul 20 '15 at 10:24
• @Shailesh Please explain in an answer how you got to 15317. Jul 20 '15 at 10:26
• Just took 17, digit sum is 8, that leaves a digit sum of 9 to go. 153 is 17 times 9. Jul 20 '15 at 10:45

The number has to be $15317$. I give in to the temptation of posting my earlier comment as an answer. The number ends in $17$, so we have a starting point, the digit sum is $8$. We now need a digit sum of $9$, and the number appended on the left has to be divisible by $9$. Since $17$ and $9$ are coprime, $17$ x $9$ = $153$ is the smallest such number. Hence the answer to the original question is $15317$.

• This is simply an ad-hoc way of formulating and solving the Constant-case CRT problem equivalent to the OP - see my comment on Rebecca's answer. Jun 24 '17 at 16:29

Starting point: If $n$ is the number then:

• $n \equiv 17 \pmod {100}$ since $n$ ends in $17$.
• $n \equiv 17 \pmod 9$ since the digits of $n$ sum to $17$.
• $n \equiv 17 \pmod {17}$ since $n$ is divisible by $17$.

The Chinese Remainder Theorem now reduces the possibilities greatly.

• 100, 9 and 17 are also conveniently coprime
– qwr
Jul 20 '15 at 10:44
• @qwr So by CCRT = Constant-case CRT, $\ n\equiv 17\,$ mod $100\cdot 9\cdot 17 = 15300,\,$ and the second smallest positive solution $\,n = 17+15300\,$ solves the OP.. Jun 24 '17 at 16:27

You should start finding the first number $N$ that is a multiple of $17$ whose digits sum $9$. (What kind of numbers are those whose digits sum $9$?)

If you append $17$ to the end of $N$, you shall get it.

Hint: The number ends in 17, so $n-17$ is divisible by 100 and by 17, otherwise $n$ is not divisible by 17. So check numbers that are 17 more than a multiple of 1700.

If the digits add to $17$ the rest of the digits, imagine they are $abcd$ must add to $9$.

And $abcd17 = 100*abcd+ 17$ must be divisible by $17$. As $100$ and $17$ are relatively prime $abcd$ must be divisible by $17$.

So in essence to question is what is the smallest number that is divisible by $17$ and with digits that add to $9$. If the digits add to $9$ is must be a multiple of $9$ so it must be a multiple of $9*17 = 153$.

So the question in essence is: what is the smallest multiple of $153$ with digits that add to $9$ and the answer to that is ... $153$.

The number you want is $15317$.