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=s_nBⁿ+s_n-1B^n-1+…+s₀ 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 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

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 digit 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 digit 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.

The remainder for N divided by D isthe same as the remainder of w_n divided by D, Then quotient of N divided by D is the quorient of N−w_n divided by D plus the quotient of w_n 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.