Why is the divisible-by-3 rule true in base 10? Can this be generalized?

Question

In base 10, an integer is divisible by 3 if the sum of its digits is divisible by 3. Why is this true?

I've been giving it some thought, and I figure that it's because the remainder of 10 divided by 3 is 1, which acts as a sort of counting mechanism. Along these lines, I suspect that an integer is divisible by a prime digit p if the sum of its digits (as expressed in base b) is divisible by p, AND if the base b is one more than some multiple of p.

But it's been an awfully long time since I've done this sort of thing, and I'd love to know if I'm on the right track here (and why).

Answer 1

Your conjecture is true: indeed, if
b is 1+ a multiple of p,
then any power
b^k is also 1+ a multiple of p.

That an integer n is written n_k...n_1
(sorry, I'd need a better math writing system here: n_k, n_(k-1),..., n_1 are integers between 0 and b-1)
means that
n= sum of ( n_k times b^k)
and since b^k=1 + a multiple of p,
n_k times b^k = n_k + a multiple of p,
so one also has
n= (n_k + n_(k-1) +...+ n_1) plus a multiple of p

So n is divisible by p if and only if the number
n_k + n_(k-1) + ... + n_1
is divisible by p.

Note that p does not even have to be prime for the above proof to be true.

If you'd like to "do this sort of things again", you might want to start with finite rings and fields Z/pZ (i.e. arithmetics where one always counts "up to a multiple of p"). Have fun !

Answer 2

I'll try to give you a general answer. Suppose you're in a base b >1. Then, every integer N >=0 is of the form N = a_0 + a_1 b +...a_n b^n, where each a_i, i=0,1,...n are the digits we need to express n in base b. For each i, we have 0 <= a_i <= b-1. If N is expressed with n+1 digits, then a_n >0.

Let P the polynomial whose coefficients are a_0, a_1, ...a_n. Then, N = P(b). Now, suppose there exist positive numbers k and p such that b = k * p +1 , which implies the remainder of b divided by p is 1. According to Algebra, we have N = P(b) = (b-1) Q(b) + r, where Q is a polynomial of degree n -1 and r = P(1). It follows that N = k*p * Q(b) + P(1) Since the coefficients of P are integers and the coefficients of b -1 are 1 and -1 , the division algorithm for polynomials implies the coefficients of Q are integers. Therefore, Q(b) is an integer, because so is b. And we conclude that N/p = k*Q(b) + P(1)/p. Since k * Q(b) is an integer, it follows N is diviisible by pif and only if P(1) is divivisible by p. But we readily see that P(1) = a_0 +a_1....a_n, which isn exactly the desired concusion. And so you're right in your first assertion.

As for the second assertion, a similar reasining shows, even easier, that in base b >1, N is divisible by b-1 if and only if the a_0 + a_1....= a_n is, and N is divisible by b +1 if and only if the difference of the sum of digits of even order and the sum of the digits of odd order is divisible by b +1.

I hope I have helped

Answer 3

Very interesting idea. Let's see what I can do about it here.

Let's use base 8 and see if somethings divisible by 7.

try 77. first, we need to put this in base 8

77 = 9*8 + 5 = 1 x 64 + 1 x 8 + 5 = 115 (base 8)

now, 1+1+5 = 7 , which is divisible by 7

so, it looks like it works, but converting bases is more trouble than it's worth!

Great idea, though. You'll go far with groups, rings, fields in modern algebra!