1

The task of mine is: What is the smallest (non-iterated) digit sum of a positive and natural number that is divisible by $37$?

I have already done 80% of the task, I have proven that $1$ can't possibly be true. I also have proven that the digit sum $2$, that can be displayed as $2\times10^n$ such as $2;20;200$ etc., is impossible for a natural and positive number that is divisible by $37$. But the digit sum $2$ can be also made by two ones, like in $11$, $101$ or $100100$.

So my question is:

How can I prove, that $2$ is not a (non-iterated) digit sum of a positive and natural number that is divisible by $37$?

Misha Lavrov
  • 142,276
calculatormathematical
  • 2,222
  • Powers of $10$ are either $1,10$ or $26$ $\pmod {37}$. That tells us that two powers of $10$ can not add to a multiple of $37$. – lulu Sep 06 '18 at 19:52
  • 3
    Please do not deface your question after you get an answer. That makes the answers impossible to understand and the entire post unhelpful for future users. – hmakholm left over Monica Sep 06 '18 at 20:39

1 Answers1

3

Any number whose sum of digits adds up to $2$, and does not contain $2$ as a digit, must be of the form $10^x + 10^y$, where $x,y\in\mathbb Z^+$. This will be divisible by $37$ iff $$(10^x + 10^y)\equiv0 \pmod{37}\tag1$$

Observe that $10^3\equiv 1\pmod {37}$

As a result, for any $x\in\mathbb Z^+$, $$10^x\equiv10^{x\pmod3}\pmod{37}$$

Now, $x\pmod 3$ can only take values of $0,1,2$. We have that $$10^0\equiv 1\pmod{37}$$ $$10^1\equiv 10\pmod{37}$$ $$10^2\equiv 26\pmod{37}$$

For there to exist $x,y$ to satisfy $(1)$, we need that their values $\pmod{37}$ add up to a value divisible by $37$. Clearly, using any pair out of $\{1,10,26\}$ does not give a sum divisible by $37$, so this is not possible.

However, observe that using three such powers works - we have $1+10+26=37\equiv 0\pmod{37}$. Thus, there exists a number with digit sum $3$, with three digits of value $1$, that is divisible by $37$. One can see that $111$ satisfies this.

GoodDeeds
  • 11,185
  • 3
  • 22
  • 42