# Smallest digit sum for a specific number

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

• 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
Commented Sep 6, 2018 at 19:52
• 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. Commented Sep 6, 2018 at 20:39

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.

• @calculatormathematical Please stop suggesting edits to delete the answer. Commented Sep 6, 2018 at 21:14