San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
& Tornado Alley
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 = sn
and
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.

The remainder for N divided by D isthe same as the remainder of wn divided by D, Then quotient of N divided by D is the quorient of N−wn divided by D plus the quotient of wn divided by D.

These results are not limited to digits. For the extension to divisors which are any number see Digits of quotients for any divisors.


HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins