Consider the polynomial

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

where C is the sequence of coefficients c_nc_n-1…c₁c₀. This is the representation of the number N=P(C, k) to the base k if all of the coefficients are nonnegative and less than k. Here it is presumed for the simplicity of the presentation that k is a positive integer and the coefficients { c_j for j= 0 to n} are integers in the range from 0 to (k-1). The results however are far more general.

Note that

(k−h)(k^n-1 + k^n-2h + k^n-3h² + … + kh^n-2 + h^n-1)
= 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:

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

Again consider the polynomial

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

Now form P(C, h) and [ 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 1: For any coefficient sequence C,
the polynomial [ P(C, k) − P(C, h)]
is exactly divisible by (k−h).
In other notation
P(C, k) = P(C, h) mod (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, h) is in the nature of a remainder upon the division of P(C, k) by (k−h). If 0≤P(C, h)<(k−h) then it is the remainder. If not, the remainder is easily obtained by a simple operation such as [(k−h)+P(C, h)] when P(C, k) is negative.

The representation of Q as a polynomial in powers of k is

Q = d_n-1(h)k^n-1 + d_n-2(h)k^n-2+ … + d₁(h)k+ d₀(h)

where the d_j's are polynomials in h. Since (k^m−h^m)/(k−h) is equal to (k^m-1 + k^m-2h + k^m-3h² + … + kh^m-2 + h^m-1) therefore c_m shows up in the sum for d_j for j<m with a coefficient h^m-j. Specifically the relations are:

d_n-1 = c_n
d_n-2 = c_nh + c_n-1
d_n-3 = c_nh² + c_n-1h + c_n-2
… …
d₁ = c_nh^n-2 + c_n-1h^n-1 + … + c₂
d₀ = c_nh^n-1 + c_n-1h^n-2 + … + c₂h + c₁

These relations can be expressed by the iterative scheme

d_j = d_j-1h + c_j+1

When h=1 the iterative scheme just produces the cumulative sums of the digits from the left. Let k=10 and consider the number 1421. The cumulative sums are {1, 5, 7, 8}. The sum of all of the digits is thus 8. If 8 isubtracted from 1421 the result, 1413, should be exactly divisible by 10-1=9. And it is; 1413=9×157. But where do we see 157? It is the first three cumulative sums represented as a decimal number; i.e., 1×100+5×10+7=157.

Another way to interpret the 8, the sum of the digits of 1421, is as the remainder when 1421 is divided by 9. Thus 1421=9×157 + 8.

Let us take the same number and use h=−1. The iterative scheme produces

1
(-1)1 + 4 = 3
(-1)3 + 2 = -1
(-1)(-1) +1 = 2

Subtract 2 from 1421 to get 1419. This number should be divisible by 10−(−1)=11. And indeed it is because 1419=11×129. The first three iterative sequence was {1, 3, −1). This represents the number 1×100+3×10−1=130−1=129. Another way of deriving 129 is to resolve the negative digit by borrowing one unit from 3, the coefficient of the next higher power of 10. That 10 is added to the (−1) to get 9. So the quotient of 1419 divided by 11 is 129.

Now let h=2 so 10−2=8. The iterative scheme for 1421 is now

1
2(1)+4 = 6
2(6) + 2 = 14
2(14)+1 = 29

When 29 is subtracted from 1421 the result is 1392. This should be exactly divisible by 8 and it is. The quotient of 1392 divided by 8 is 174. This quotient should be 1×100+6×10+14 which is the same as 1×100+7×10+4=174. The double digits of 14 are resolved by carrying the 1 to the next higher power of 10.

In other words, the quotient has digits equal to the cumulative weighted sums from the left of the digits of the number up to, but not including, the unit digit on the right.

The last illustration is for division by 12=10−(−2). Again 1421 will be used. The iterative scheme yields:

1
(-2)1 +4 = 2
(-2)2 + 2 = -2
(-2)(-2) +1 = 5

Subtracting 5 from 1421 yields 1416. The -2 in the iterative scheme is resolved by borrowing 1 from the 2 which makes the sequence from the iterative scheme 118. And indeed 1421=12×118+5.

(To be continued.)