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

Quotients in
Digit Sum Arithmetic for
Any Base and Any Divisor


This material is to extend results found for the division of decimal numbers by 9 and 11. It was found that the cumulative sums of digits of a number generate the digits of the quotients of that number divided by 9 or 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 number as a divisor D.

A cumulative weighted sum sequence for any number S=snBn+sn-1Bn-1+…+s0 to be divided by any divisor D 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 a Theorem
to be Formulated

For an example take the number 4321 to the base B=10 and let the divisor D be 9. This means the weight h=10−9=1. The weighted sum sequence is just the cumulative sums. For 4321 these cumulative sums are {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. In fact 4311=9*479. The cumulative sums of the first three digits from the left of 432 are 4, 7, 9. These indicate that the quotient which should be 479 and it is.

Similar properties prevail for 11=10+1 as do for 9=10−1 but involve more complex operations. The weight h for D=11 is (B-D)=10−11=−1. For example. if N=125 then the cumulative weighted sums are {1, (-1)1+2=1, (-1)1=5=4}. The weighted digit sum for 125 is 4. This means 125−4=121 should be exactly divisible by 11 and it is since 121=11·11. Note the first two cumulative sum are 1 and 1 so the quotient of 121 divided by 11 should be 1·10+1=11, 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.

The process for some numbers may involve a bit more than occurred in the above illustrations. The cumulative weighted sums may involve two-digit numbers or negative numbers. These are resolved by modifying the sums for higher order terms.

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 divisor 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 divisor 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