# How does base of a number relate to modulos of its each individual digit?

I encountered a programming problem that need a little math. Since I took number-theory long time ago, from the top of my head, I could not think of a way to approach this problem.

Give a base 'b' ( 2, 3, 4, 5, 6 ... -> 26 ). So if I'm at base 10, I will have 10 digits: 0, 1, 2, 3...9. The digit of a base 'b' is called interesting if it satisfy this condition: 3 is an interesting digit because 118*3 = 354 and 3+5+4 = 12. Which means both 354 and 12 divides 3. By look at the result sets, I can see the relation is:
if b mod d = 1 then d is an interesting digit.
For example: 10 mod 9 = 10 mod 3 = 1. So both 3, 9 are interesting digits in base 10.

How could I prove this? Any hint?

Thanks,
Chan

-

You seem to be asking for what digits $\displaystyle 0 \lt d \lt b$ can we apply the following divisibility test:

A number is in base $\displaystyle b$ is divisible by $\displaystyle d$ if the sum of digits of the number is divisible by $\displaystyle d$.

This is certainly true for $\displaystyle b = 1 \mod d$.

Because $\displaystyle \sum_{k=0}^{n} a_k b^{k} - \sum_{k=0}^{n} a_k = \sum_{k=0}^{n} a_k (b^k -1) = 0 \mod d$

Thus $\displaystyle \sum_{k=0}^{n} a_k b^{k} = \sum_{k=0}^{n} a_k \mod d$.

If $\displaystyle b = r \mod d$ where $\displaystyle r \neq 1$, then we have that there is some $\displaystyle k$ for which $r^k - 1 \neq 0 \mod d$.

The number with $\displaystyle 1$ as the digit correponding to $\displaystyle b^k$, and $\displaystyle d-1$ in as the "units" digit (corresponding to $\displaystyle b^0$) is a counterexample to the divisibility rule for $\displaystyle d$.

-
thanks a lot! After reading your solution, I feel so shame of myself! –  Chan Jan 12 '11 at 17:08
@Chan: Don't be. Everyone misses the most obvious things sometime... And I would not call this one obvious. –  Aryabhata Jan 12 '11 at 17:29

If $b \ne 1 \pmod d$, then the number $10$ in base $b$ shows that $d$ is not interesting: it represents the number $b$, so it is not equal to $1 \pmod b$; but $1 + 0 = 1$. This, together with Moron's answer, shows that your conjecture is correct.

Edit Taking the question literally, I really need to exhibit a number that is divisible by $d$ but the sum of whose digits is not; or vice versa. If $d < b$, take the number $1.(d-1)$; the sum of its digits is $d$, but it represents $b+d-1$, which is not divisible by $d$. If $d \ge b$, then the representation of $d$ in base $b$ is two or more digits, so their sum must be less than what they represent (because all but the last digit represent numbers greater than themselves).

-
You are disproving a stronger statement: "The number and the sum of digits have the same remainder". –  Aryabhata Jan 12 '11 at 17:39
Thanks Moron, you're right. I've added a codicil. –  TonyK Jan 12 '11 at 17:46

This is simply the radix $\rm\:b\:$ generalization of casting out nines. Generally, if $\rm\:d\:$ divides $\rm\ b-1\$ then $\rm\: mod\ \ d:\:\ \ b\equiv 1\ \Rightarrow\ a_n b^n +\:\cdots\: + a_1 b + a_0 \ \equiv\ a_n +\: \cdots\: + a_1 + a_0\: =\:$ sum of the radix $\rm\:b\:$ digits. For further remarks on casting out nines see my post here.

-