22
$\begingroup$

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!

$\endgroup$
4
  • 3
    $\begingroup$ Corollary of this question. $\endgroup$
    – 6005
    Sep 13, 2015 at 21:50
  • 2
    $\begingroup$ Now the harder question: what's the smallest such positive integer that satisfies these conditions? $\endgroup$
    – nneonneo
    Sep 14, 2015 at 6:02
  • $\begingroup$ 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$ $\endgroup$ Sep 15, 2015 at 15:01
  • $\begingroup$ @nneonneo 11111.......111(1999 times)000000000000000000........(idk times 😂) $\endgroup$ Nov 19, 2020 at 12:38

3 Answers 3

41
$\begingroup$

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.

$\endgroup$
4
  • 4
    $\begingroup$ Because $1999$ is a prime, we can use $k=1998$ by Little Fermat. $\endgroup$ Sep 13, 2015 at 16:04
  • $\begingroup$ What a wonderful solution! I have thought about the problem several days but could not able to solve it. Thank you very very much! $\endgroup$
    – Trung Ta
    Sep 13, 2015 at 16:09
  • 3
    $\begingroup$ How did you know where to begin? $\endgroup$
    – David G
    Sep 13, 2015 at 22:19
  • $\begingroup$ @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. $\endgroup$ Sep 14, 2015 at 8:56
22
$\begingroup$

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$.

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

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")

$\endgroup$
1
  • $\begingroup$ Thanks! This is also an interesting approach! $\endgroup$
    – Trung Ta
    Sep 16, 2015 at 14:15

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.