where
each
is a positive integer and
.
Note that gives us that
for
some positive integer A
(except A = 0 if k
= 0).
The September 15, 2006 PoW (Problem of the Week)*
What is so magical about the number nine? A number is divisible by 9 if and only if the sum of its digits are divisible by 9. Certain 'mental tricks' are done because a number minus the sum of its digits are divisible by 9. Well it turns out that 9 is only magical in base 10.
Show that whenever a number is represented in base b, it is divisible by b-1 if and only if the sum of its digits are divisible by b-1.
For example, if we used a base 9 counting system, then 143 (in base 9) would mean (143)9 = 1×92 + 4×91 + 3×90 = 81 + 36 + 3 (in base 10) = 120. And 120 is divisible by 8 as is the sum of its digits when written in base 9 (1 + 4 + 3 = 8).
Also, a number written in base 9 will be divisible by 4 or 2 if and only if the sum of its digits are divisible by 4 or 2 respectively. For example, (33)9 = 3×91 + 3×90 = 27 + 3 (in base 10) = 30 is divisible by 2 because 3 + 3 = 6 is divisible by 2.
That is, factors of b – 1 share the property that a number represented in base b is divisible by a factor of b-1 if and only if the sum of its digits are divisible by that factor of b-1.
We know in base 10 that a number is divisible by three if and only if the sum of its digits are divisible by 3. This is only because 3 is a factor of 9, which is one less than our base 10.
One more example. If we convert multiples of 7 from base 10 to base 8, the sum of the digits in the base 8 notation will be divisible by 7:
(14)10 = (16)8, {1×81 + 6×80 = 8 + 6 (in base 10) = 14}
(21)10 = (25)8, {2×81 + 5×80 = 16 + 5 (in base 10) = 21}
(28)10 = (34)8, {3×81 + 4×80 = 24 + 4 (in base 10) = 28}
(35)10 = (43)8, (42)10 = (52)8, (49)10 = (61)8, (56)10 = (70)8, (63)10 = (77)8,
The proof uses a
special case of the binomial theorem (see also Pascal's triangle).
Namely
where
each
is a positive integer and
.
Note that gives us thatfor
some positive integer A
(except A = 0 if k
= 0).
Now suppose a number
is written in base b. Then the number can be uniquely
expressed as
where
each
is a nonnegative integer satisfying
and
If
we writeas
where
c = b – 1, then
where A, B,
and D are positive integers. Since the last term
is
divisible by c if and only if
is
divisible by c ( = b – 1), we have our result!
Similarly, the last
term
is
divisible by a factor of c if and only ifis
divisible by that factor of c.