# 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? [duplicate]

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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Sep 10 '17 at 16:52

• Follows immediately by casting out $B-1$ in radix $B$ - see my answer in the linked dupe. – 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.