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!
Solution 1:
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.
Solution 2:
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$.
Solution 3:
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")