San José State University 

appletmagic.com Thayer Watkins Silicon Valley & Tornado Alley USA 



Consider the polynomial
where C is the sequence of coefficients c_{n}c_{n1}…c_{1}c_{0}. 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 (k1). The results however are far more general.
Note that
This is established by representing the two terms created from the LHS as
Thus the lemma:
Again consider the polynomial
Now form P(C, h) and [ P(C, k) − P(C, 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
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
where the d_{j}'s are polynomials in h. Since (k^{m}−h^{m})/(k−h) is equal to (k^{m1} + k^{m2}h + k^{m3}h² + … + kh^{m2} + h^{m1}) therefore c_{m} shows up in the sum for d_{j} for j<m with a coefficient h^{mj}. Specifically the relations are:
These relations can be expressed by the iterative scheme
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 101=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.)
HOME PAGE OF Thayer Watkins 