Property of 2016

Question

What is the least multiple of $2016$ whose sum of digits is $2016$?

I am totally broke on this. What I only know is that the least number of digits should be greater than $224$ which is clearly not a practical hint. The prime decomposition may give some hint but am unsure. Any ideas. Thanks beforehand.

Answer 1

Looking at the last three digits, you are not going to get more than $24$ digit-sum from them, as the largest digit-sum avilable from multiples of $8$ below $1000$ is at $888$. So you will need $225$ digits in total, which is likely to be enough.

I'll start by finding out the value of $10^{225} \bmod 2016$

$2016=2^5\cdot3^2\cdot7 = 32\cdot 63$

$\lambda(63)$ $= \text{lcm}(\lambda(3^2),\lambda(7)) = \text{lcm}(6,6) = 6 \implies 10^6 \equiv 1 \bmod 63$

$10^{225} \equiv 10^{222}\cdot 10^3 \equiv 10^3\equiv 55 \bmod 63$
$10^{225} \equiv 0 \bmod 32$ trivially

Now Chinese Remainder Theorem says we can find a value that is $ 55 \bmod 63 $ and $0 \bmod 32$ - which translates to looking for a multiple of $32$ that is $\equiv 55 \bmod 63$.

$2\cdot 32 \equiv 1 \bmod 63 \implies (1+2(55-32))\cdot 32 \equiv 47\cdot 32$ is the multiple required, and thus $47\cdot 32 \equiv 1504 \equiv 10^{255} \bmod 2016$

The greatest multiple of $2016$ less than $10^{225}$ is thus $10^{225}-1504 = \overbrace{9\ldots9}^{\text{221 9s}}8496$, which actually does have the digit-sum required. So we already have an upper limit on the minimum value.

Since we have this cycle of $6$ values for $10^k\bmod 2016$ and $10^6 \equiv 1 \bmod 63$ $\implies$ $999999 \equiv 0 \bmod 63$ we can insert "$999999$" into a valid shorter value at any point clear of the last five digits (the factor of $2^5$ being determined by those last five digits). Specifically we can multiply the higher digits by $10^6$ (which doesn't change their value $\bmod 63$) and then add $999999\cdot 10^k$ which of course idivisible by $63$.

Thus when we find the minimum multiple in $9$ digits with a digit-sum of $72$ (which is $598989888$), we can extend that to $225$ digits using insertions of $999999$, keeping $5989$ as the high-value digits.

This gives us $598\overbrace{9\ldots9}^{\text{217 9s}}89888$ as the minimum multiple of $2016$ with a digit sum of $2016$.

Answer 2

HINT: The sum of the digits of $2016$ is $9$ - can you see a way of exploiting this fact to form a multiple of $2016$ which has some digits equal to $9$? If you can find a multiple with lots of digits equal to $9$ then you may be close to an answer. If you think about this the right way, you should find a way of getting a string of digits equal to $9$.