Number of 999 digit numbers divisible by 1010 with sum of digits being 2.

elementary-number-theory

My initial try was to run a little python code just to see what those numbers would look like.

These are the first few results that match the critirea:

$1010$

$10100$

$101000$

$1010000$

$10000010$

$10100000$

$100000100$

$101000000$

$1000001000$

$1010000000$

$10000010000$

$10100000000$

So obviously the first digit has to be $1$ and then there has to be another $1$ in some other place.

The next obvious observation is that every multiple of $10$ fulfills the criteria.

The last thing I know is, that $10^k\equiv-100(\mod)\Longleftrightarrow4|k$ has something to do with it.

Other than that I am really lost in the water right now. Could anyone that has an approach push me in the right direction?
Thanks in advance!

Edit 1:

I was given the hint: $10^{998}\equiv-10^i(\mod1010)$.
Found out this is only true if $i=4k+1$.
I don't understand what to do with it though.

I also found out that if a number is devisable by $1010$ it also needs to be devisable by $101$ and $10$. Again, I don't know how to use that info yet.

Edit 2:

Trying to show that a 999 digit number with digit sum of 2 can be written as $10^{998} + 10^n$:

Not sure how to show that correctly, but I'll try my best. Say we have a 999 digit number with two $1$s in it. The first number hast to be at position 999 otherwise it would not be a 999 digit number (without leading zeros). The other $1$ can be anywhere, BUT if we take the $n$ digits of zeros behind it. We can seperate it from the 999 digit number in the format of the above statement.

Best Answer

Show the following. Fill in the blanks as needed.

  1. A 999 digit number with digit sum of 2 can be written as $ 10^{998} + 10^n$, where $ 0 \leq n \leq 998$.
  2. Show that $10^{998} \equiv \underline{\quad} \pmod{1010}$. Hence, show that $ 10^{998} + 10^n \equiv 0 \pmod{1010}$ iff $10^n \equiv \underline{910 \equiv -100} \pmod{1010}$ iff $ n \equiv \underline{0} \pmod{\underline{4}}$
  3. There are $\underline{249}$ values of $ 0 \leq n \leq 998$ that satisfy the above condition.
  4. There are $\underline{249}$ 999 digit numbers with a digit sum of 2 that are a multiple of 1010.

Recall that

  • $10^{4k+1} \equiv 10 \pmod{1010}$
  • $10^{4k+2} \equiv 100 \pmod{1010}$
  • $10^{4k+3} \equiv -10 \pmod{1010}$
  • $10^{4k+4} \equiv -100 \pmod{1010}$
Related Question