San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
USA

Quotients in
Digit Sum Arithmetic
for Any Base

## Background

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 = snand 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

And ultimately

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

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

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

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