A divisibility theorem

(When and why does the digital root test work?)

Seth Schoen, December 10, 2001


More general case
-----------------

Iff (b-1) is divisible by d, then for all n, the sum of the digits of n
in the base b is divisible by d iff n is divisible by d.

To say this another way:

For the sum of any number's digits in the base b to be divisible by d
when, and only when, the number itself is divisible by d, it is a
necessary and sufficient condition that that (b-1) is divisible by d.

(This does _not_ mean that (b-1) not being divisible by d guarantees
that the sum of digits _always_ has divisibility opposite from that of
the number itself.  It is merely guaranteed that the sum of digits, in
that case, will _sometimes_ have a divisibility opposite from that of
the number itself.)


Proof of "sufficient" (1995)
----------------------------

Let a number n be written in a base b as an infinite sequence of
digits a_i (so that a_0 is the units place or least significant
digit), so that

inf
sum a_i b^i = n
 0

Then

inf
sum a_i (b^i-1+1) = n
 0

inf               inf
sum a_i (b^i-1) + sum a_i = n
 0                 0

Now,
            i-1
b^i-1=(b-1) sum b^x
            x=0

so that if b-1 is divisible by d, b^i-1 is also divisible by d.  Then

inf
sum a_i (b^i-1) must also be divisible by d.  Then
 0

inf
sum a_i and n must both be divisible by d or both not be divisible
 0

by d.


Proof of "necessary" (2000)
---------------------------

Suppose that (b-1) is not divisible by d.

Consider the two-digit number n with a_0=1, a_1=d-1.  a_0+a_1=d, but
the value of the number is n=b*a_1+a_0=b(d-1)+1=bd-b+1=bd-(b-1).  Now,
bd is clearly divisible by d.  But since (b-1) is not divisible by d,
bd-(b-1) cannot be divisible by d either.  Therefore, n is not divisible
by d.


Digital root corollaries
------------------------

The digital root test for divisibility by a digit d in a base b is
applicable to all numbers if (b-1) is divisible by d.

The converse is true: if the digital root test for divisibility by a digit
d is applicable for all numbers in a base b, then (b-1) is divisible by d.

This can be summarized:

The digital root test for divisibility by a digit d in a base b is
applicable to all numbers if and only if (b-1) is divisible by d.

All of these are proven using induction on the number of successive
applications of the sum-of-digits process (induction step: divisibility
by d is unchanged after n applications of sum-of-digits implies that
divisibility is unchanged after n+1 applications of sum-of-digits).