San José State University
Thayer Watkins
Silicon Valley
& Tornado Alley

Quotients in
Digit Sum Arithmetic
for Any Base


This material is to extend results found for the division of decimal numbers by 9 and 11. Decimal numbers are simply polynomials in powers of ten. In the following are the results for numbers for any base B and division is by any digit D..

A cumulative weighted sum sequence for any number S=snBn+sn-1Bn-1+…+s0 is defined as follows:

w0 = sn
wi = wi-1h + sn-i

where the weight h is (B−D).

The weighted sum of the digits of any number S is the value of wn, the final term of the sequence. When this process is repeated until the result is a single digit that single digit is known as the weighted digit sum. In what follows such an iterated summation is not involved.

The sequence {wi for i=0 to n} can be expressed as

w0 = sn
w1 = w0h + sn-1
w2 = w1h + sn-2
= w0h² + sn-1h + sn-2
= snh² + sn-1h + sn-2

And ultimately

wn = snhn + sn-1hn-1 + … + s0

Illustrations of the
Theorem to be Formulated

For an example take the number 4321 to the base B=10 and let the digit D be 9. This means the weight h=10−9=1. The weighted sum sequence for 4321 is {4, 7, 9, 10] . Thus the weighted sum of its digits is 10. This means, as will be shown, that 4321−10=4311 is exactly divisible by 9=10-1. In fact 4311=9*479. The cumulative sums of the digits of 432 are 4, 7, 9. These form the quotient which should be 479 and it is.

Now consider D=8 and the number 102 to the base 10. The weight h=B−D=10-8=2. The weighted sum sequence is {1, 2·1+0=2, 2·2+2=6}. Thus 102−6=96 should be exactly divisible by 8, and it is; i.e., 96=12·8. Note that the first two terms of the weighted sum sequence are {1, 2) which form the quotient of 96 divided by 8 as 1·10+2=12.

Again consider D=8, B=10 and hence h=2, but let the number be 132. The weighted sum sequence is {1, 2·1+3=5, 2·5+2=12}. So the weighted digit sum is 12. Thus 132−12=120 should be exactly divisible by 8 and it is; i.e., 120=15·8. The first two terms of the sequence are 1 and 5 corresponding to the quotient of 15.

Now let the number 1326. The weighted sum sequence is {1, 2·1+3=5, 2·5+2=12, 2·12+6=30}. This means 1326−30=1296 should be exactly divisible by 8, and it is; i.e., 1296=162·8. The first three terms of the weighted sum sequence are {1, 5, 12}. The quotient 162 is equal to 1·10²+5·10+12, but it is appropriate to add the tens digit of 12 to the 5 to get the sequence {1, 6, 2}.

Polynomials over the Integers

A polynomial over the integers is of the form

cnkn + cn-1kn-1 + … + c1k + c01

where the coefficients cj and the base k of the polynomial are integers and n is a nonnegative integer.

The largest power n in a polynomial is called its degree.

It is convenient to use the following notation for polynomials

P(C, k) = cnkn + cn-1kn-1 + … + c1k + c01

where C stands for the sequence of coefficients {cn, cn-1, …, c1, c0}.

Two Divisibility Lemmas
for Polynomials

Let h be any integer except k. Note that

(kn-1 + kn-2h + kn-3h² + … + khn-2 + hn-1)(k−h)
= kn − hn

This is established by representing the two terms created from the LHS as

kn + kn-1h + kn-2h² + … + k²hn-2 +khn-1
               − (kn-1h + kn-2h² + kn-3h³ + … + khn-1 + hn)
kn − hn

Thus the lemma:

Lemma1: For all n, (k−h) is a factor of (kn−hn).

Now consider the polynomial

P(C, k) = cnkn + cn-1kn-1 + … + c1k + c0

and form P(C, h) and then [ P(C, k) − P(C, h)]

[ P(C, k) − P(C, h)] = cn(kn−hn) + cn-1(kn-1−hn) + … + c1)(k−h)

Note that (k−h) is a factor of each term of the above and therefore is a factor of the sum. Consequently

Lemma 2: For any polynomial P(C, k),
[P(C, k) − P(C, h)]
is exactly divisible by (k−h).

This means that

[P(C, k) − P(C, h)] = (k−h)Q

where Q is a polynomial in k and h. Hence

P(C, k) = P(C, h) mod (k−h)

Thus P(C, h) is in the nature of a remainder upon the division of P(C, k) by (k−h).

Weights and Quotients

In the notation established above for polynomials the weighted sum of the digits of a number with S as its sequence of coefficients is

wn = P(S, h)

The number N to the base B is P(S, B). Consider a digit D. Its weight h is (B−D). Therefore N−wn is P(S, B)−P(S, h) which is equal to Q(B−h)=QD.

Now consider the number U which can be constructed from the first (n-1) terms of the weighted digit sum sequence; i.e.,

U = Bn-1w0 + Bn-2w1 + … + Bwn-2 + wn-1

Now consider the numbers UB and Uh.

UB = Bnw0 + Bn-1w1 + … + B²wn-2 + Bwn-1

On the other hand

Uh = Bn-1w0h + Bn-2w1h + … + Bwn-2h + wn-1h

Since wi = wi-1h + sn-i

w0h = w1 − sn-1
w1h = w2 − sn-2

… … …
wn-2h = wn-1 − s1
wn-1h = wn − s0

This means that

Uh = Bn-1(w1 − sn-1) + Bn-2(w2 − sn-2) + … + B(wn-1 − s1) + (wn − s0)

Then UB−Uh is equal to

Bnw0 + Bn-1sn-1 + Bn-2sn-2 + … + Bs1 + s0 − wn

But w0=sn and wn=P(S, h). Thus

UB−Uh = P(S, B) − P(S, h) = QD
and hence
U is the quotient of the division
of P(S, B) − P(S, h) by D=B−h

Theorem: Let N be any number and S be its coefficient sequence for base B. Let D be a digit and h=B−D its weight for generating the cumulative weighted digit sequence {w0, w1, … wn}. Then N−wn is an exact muliple of D and the quotient of N−wn divided by D is the number to base B having a coefficient sequence composed of the first (n-1) terms of the cumulative weighted digit sequence.

HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins