[Math] Even Digits Multiple Of Nine

elementary-number-theory

Folks, I foud this problem online, and I am having trouble to understand the logic in the sentence the I highlited:

"Problem

Find the smallest multiple of nine containing only even digits.

Solution

If a number is divisible by nine then the sum of digits must be a multiple of nine.

But if all of the digits are even then they must sum to an even multiple of nine, and the smallest even multiple of nine is eighteen.

Hence we are looking for the most efficient way to write eighteen as the sum of even digits: 2 + 8 + 8. That is, the smallest multiple of nine containing only even digits is 288.

Find the first five multiples of nine containing only even digits."

I've applied the same "rule" to other numbers, so a gess its not a rule. But I'm intrigued by this logic though.

Best Answer

Each number in base ten can be written as $$d_0\cdot 10^0+d_1\cdot 10^1+\cdots+d_n10^n$$ where each $d_i$ is between $0$ and $9$ inclusive. (We would write the number in base ten as the concatenation $d_nd_{n-1}\cdots d_0$).

But note that $10\equiv 1 \pmod 9$, and thus every power of ten is $1$ modulo $9$ (that is, the remainder of a power of ten when divided by $9$ must be $1$).

So if we write our number modulo $9$, we have $$d_0\cdot 10^0+d_1\cdot 10^1+\cdots+d_n10^n=d_0+d_1+\cdots+d_n.$$ Thus, if our number is divisible by $9$, it must be congruent to $0$ modulo $9$, and so the sum of the digits must be divisible by $9$.

Edit: If you have never seen congruences and modular arithmetic, this article should be helpful. It is simpler than it sounds. We write $a\equiv b\pmod n$ if $b$ is the remainder of $a$ when divided by $n$.

Related Question