Take the 2-minute tour ×
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.

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

share|improve this question
add comment

3 Answers

up vote 5 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|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
add comment

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|improve this answer
2  
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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.