This question already has an answer here:

Why is any number N of base B, whose digits sum to a multiple of a prime factor P of B-1, also divisible by P?

(Also, how do you ask that question more succinctly?)

For examples:

  • B=7, P=2, N=22
  • B=7, P=3, N=12
  • B=10, P=3, N=18

By way of background, this came from thinking about how any number whose digits sum to a multiple of 3 is also divisible by 3. I can get as far as generalising it to the above question, and I can vaguely see "why" but haven't been able to prove it.

The vaguely why is that each number in B is constructed of multiples of digits in 0..B-1, whether you are summing digits or digits^(0..B-1). (maybe?)

Also thought it might be something to do with how carrying works when you're adding numbers.


marked as duplicate by Bill Dubuque elementary-number-theory Sep 10 '17 at 16:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Follows immediately by casting out $B-1$ in radix $B$ - see my answer in the linked dupe. $\endgroup$ – Bill Dubuque Sep 10 '17 at 16:53

By an interesting coincidence, I mentioned this fact in an earlier answer of mine today. Write your number in a base $b$ representation,

$$n = \sum_{k = 0}^\ell a_k b^k,$$ where $0 \leq a_k < b$. Consider this equation mod $(b-1)$, and note that $b^k \equiv 1^k \equiv 1 \bmod b-1$, so that

$$n \equiv \sum_{k=0}^\ell a_k 1^k \equiv \sum_{k = 0}^\ell a_k \mod b-1.$$

This says precisely that $b-1$ divides $n$ if and only if $b-1$ divides the digit sum of $n$, when written in base $b$. As a corollary, this is true for all divisors of $b-1$, including primes.

  • $\begingroup$ Thank you! I'm working through it. But... I'm expecting that last paragraph to read: "This says precisely that b-1 divides n if and only if b-1 divides the digit sum of n, when written in base b. As a corollary, this is true for all divisors of b-1, including primes." $\endgroup$ – azhrei Sep 8 '17 at 2:33
  • $\begingroup$ Whoops, you're right. I dropped many of my minus ones. $\endgroup$ – davidlowryduda Sep 8 '17 at 3:26

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