Background

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=s_nBⁿ+s_n-1B^n-1+…+s₀ to be divided by any divisor D is defined as follows:

w₀ = s_n
and
w_i = w_i-1h + s_n-i

where the weight h is (B−D).

The weighted sum of the digits of any number S is the value of w_n, 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 {w_i for i=0 to n} can be expressed as

w₀ = s_n
w₁ = w₀h + s_n-1
w₂ = w₁h + s_n-2
= w₀h² + s_n-1h + s_n-2
= s_nh² + s_n-1h + s_n-2

And ultimately

w_n = s_nhⁿ + s_n-1h^n-1 + … + s₀

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

c_nkⁿ + c_n-1k^n-1 + … + c₁k + c₀1

where the coefficients c_j 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) = c_nkⁿ + c_n-1k^n-1 + … + c₁k + c₀1

where C stands for the sequence of coefficients {c_n, c_n-1, …, c₁, c₀}.

Two Divisibility Lemmas
for Polynomials

Let h be any integer except k. Note that

(k^n-1 + k^n-2h + k^n-3h² + … + kh^n-2 + h^n-1)(k−h)
= kⁿ − hⁿ

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

kⁿ + k^n-1h + k^n-2h² + … + k²h^n-2 +kh^n-1
               − (k^n-1h + k^n-2h² + k^n-3h³ + … + kh^n-1 + hⁿ)
        
__________________________________________
kⁿ − hⁿ

Thus the lemma:

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

Now consider the polynomial

P(C, k) = c_nkⁿ + c_n-1k^n-1 + … + c₁k + c₀

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

[ P(C, k) − P(C, h)] = c_n(kⁿ−hⁿ) + c_n-1(k^n-1−hⁿ) + … + c₁)(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

w_n = 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−w_n 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 = B^n-1w₀ + B^n-2w₁ + … + Bw_n-2 + w_n-1

Now consider the numbers UB and Uh.

UB = Bⁿw₀ + B^n-1w₁ + … + B²w_n-2 + Bw_n-1

On the other hand

Uh = B^n-1w₀h + B^n-2w₁h + … + Bw_n-2h + w_n-1h

Since w_i = w_i-1h + s_n-i

w₀h = w₁ − s_n-1
w₁h = w₂ − s_n-2

… … …
w_n-2h = w_n-1 − s₁
w_n-1h = w_n − s₀

This means that

Uh = B^n-1(w₁ − s_n-1) + B^n-2(w₂ − s_n-2) + … + B(w_n-1 − s₁) + (w_n − s₀)

Then UB−Uh is equal to

Bⁿw₀ + B^n-1s_n-1 + B^n-2s_n-2 + … + Bs₁ + s₀ − w_n

But w₀=s_n and w_n=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 {w₀, w₁, … w_n}. Then N−w_n is an exact muliple of D and the quotient of N−w_n 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.