# Prove that there exists a number divisible by 1999 with digit sum 1999

My nephew in the secondary school asked me how to solve the problem as stated in the title. Honestly, I do not have any idea how to do it:

Prove that there exists a positive integer number such that 1999 divides it, and the sum of all of its digit is also 1999.

Can anybody shed some light on how to solve it? Any help is much appreciated!

Thanks!

• Corollary of this question. – 6005 Sep 13 '15 at 21:50
• Now the harder question: what's the smallest such positive integer that satisfies these conditions? – nneonneo Sep 14 '15 at 6:02
• I don't know if this answer is right, therefore sorry if i'm wrong. If exist a number $n$ with digit sum $1999$, $n\equiv 1 \pmod 3$ because $1999\equiv 1 \pmod3$. Therefore $n=3k+1$( with $k$ integer) but this number to be divisible by $1999$ is necessary that $k\equiv 666\pmod {1999}$. Therefore $n$ can be written in the form $$n=3(1999p+666)+1$$ but I don't know if exist a integr $p$ such that digit sum of $n$ is $1999$ – Domenico Vuono Sep 15 '15 at 15:01

Because $10$ is coprime to $1999$ there exists a positive integer $k$ such that $10^k\equiv1\pmod{1999}$. It follows that $1,10^k,10^{2k},10^{3k},\ldots,$ all leave remainder $1$ when divided by $1999$. Therefore the number

$$S=1+10^k+10^{2k}+\cdots+10^{1998k}$$ is divisible by $1999$. Furthermore, the decimal expansion of $S$ has $1999$ ones and the rest of its digits are all zeros.

• Because $1999$ is a prime, we can use $k=1998$ by Little Fermat. – Jyrki Lahtonen Sep 13 '15 at 16:04
• What a wonderful solution! I have thought about the problem several days but could not able to solve it. Thank you very very much! – Trung Ta Sep 13 '15 at 16:09
• How did you know where to begin? – David Sep 13 '15 at 22:19
• @David: I'm not sure. I've seen/used similar ideas to solve other problems. For example the question of proving that if $m$ is coprime to ten, then $m$ is a factor of some repunit (= an integer with a decimal expansion with all digits equal to $1$). The starting point there is also that $m\mid 10^k-1$ for some $k$. Here that trick didn't quite work. While $(10^{1998}-1)/9$ is divisible by $1999$, its decimal expansion has only $1998$ digits. All are equal to $1$, so the digit sum is only $1998$. A modification was needed. – Jyrki Lahtonen Sep 14 '15 at 8:56

Here's another solution.

Note that $1999$ has digit sum $28$, while $2 \cdot 1999 = 3998$ has digit sum $29$. Since $28$ and $29$ are relatively prime, and $1999 > 28 \cdot 29 - 28 - 29$, $1999 = 28a + 29b$ for some $a, b > 0$ (see Chicken McNugget Theorem). Then just string together $a$ copies of $1999$ followed by $b$ copies of $3998$: $$\underbrace{199919991999 \cdots 1999}_{a \text{ copies of } 1999} \underbrace{399839983998 \cdots 3998}_{b \text{ copies of } 3998}.$$ This is clearly divisible by $1999$, and its digit sum is $28a + 29b = 1999$.

• 1999 has digit sum 19? – GOTO 0 Sep 13 '15 at 22:14
• @GOTO0 Lol. sorry. fixed. – 6005 Sep 13 '15 at 22:16
• Oh, it is also a nice solution! Interesting approach! Thank you very much! – Trung Ta Sep 14 '15 at 2:54
• Nice! And good job finding an earlier version of this question. At least your solution, unlike mine, gives a different approach! – Jyrki Lahtonen Sep 14 '15 at 5:13
• I think the $\ge$ should be a $\gt$ or not? – Ivo Beckers Sep 14 '15 at 10:08

Starting from 11,111:
1...1 (n times) * 1999 = 2221..10889 with n-4 "1" in results (=2,221...*10^(n+3)).
e.g.

• 11,111 * 1999 = 22,210,889
• 111,111 * 1999 = 222,110,889, and so on

Proof: Let's suppose that it's true for n (it's true for n=5, 6 as above), for n+1:
1.11. * 10^(n+1) * 1999 =
1.11. * 10^n * 1999 + 10^(n+1) * 1999 =
2.221.. * 10^(n+3) + 1.999 * 10^(n+4) =
2.2211.. * 10^(n+4) what we had to prove.
Where 1.11. * 10^n represents the number consisting of n+1 "1" and 2.221.. * 10^n represents the number described above.

Sum of digits of 22,210,889 is 32 and it's increased by one each step.
2221..10889 (1968 "1" digits) has the sum of digits of 1999 and it's divisible by 1999 as it's equal to 1999 * 1..1 (consisting of 1972 "1")

• Thanks! This is also an interesting approach! – Trung Ta Sep 16 '15 at 14:15