Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer
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).

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.