San José State University |
---|
applet-magic.com Thayer Watkins Silicon Valley & Tornado Alley USA |
---|
Weighted Summations of the Coefficients of a Polynomial and its Remainders up on Division |
---|
This is to call attention to a result proven elsewhere concerning the relationship of sums involving the coefficients of a polynomial and the remainder for that polynomial up on division by a difference of the base of that polynomial and some term. Let the polynomial be
where C is the sequence of coefficients c_{n}c_{n-1}…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 (k-1). The results however are far more general.
Let h be another integer less than k in magnitude. The theorem is then
which means that [P(C, k) − P(C, h)] is exactly divisible by (k-h). In other words, P(C, h) is the remainder for the division of P(C, k) by (k-h) or a term differing from that remainder by an integral multiple of (k-h). P(C, h) is, as are all polynomials, a weighted sum of its coefficients in which the weights are the powers of h.
Decimal numbers, numbers to the base 10, are polynomials in powers of 10. So k=10. Let h=1 and hence (k-h) is 9. P(C, 1) is just the sum of the digits of the number. Take C to be 125. Then P(125, 1)=8 and 125=14*9+8. Thus P(C, 1) is equal to the remainder for 125 divided by 9.
Now take h=−1. P(C, −1) is the net sum of the coefficients alternately adding and subtracting the digits starting from the right. Thus P(125, −1)=5−2+1=4. Now divide 125 by (10−(−1)=(10+1)=11. The result is 125=11*11+4. In this case the remainder is the same as P(125, −1). In other cases P(C, −1) may not be equal to the remainder, but is equal to a number which is equivalent to the remainder modulo 11. For example, P(97, −1=7−9)=−2. The remainder for 97 divided by 11 is 9 because 97=8*11+9. However −2=9 mod 11 because (−2−9) is exactly divisible by 11.
There is the trivial example of h=0. The remainder for the division of P(C, 10) by 10 is c_{0}, but that is the same as P(C, 0).
When |h|>1 the computation is more cumbersome but still confirms the theorem. Let h=2 so (k-h)=(10-2)=8. Let C=111 so P(111, 2) = 4*1+2*1+1=7. However 111=13*8+7. In this case P(111, 2) is equal to the remainder for the division of 111 by 8.
Now let C=105. Then P(105, 2)=1*4+0*2+5=9. But 9=1 (mod 8) and 105=13*8+1. Thus if P(C, h) is a single digit which is greater than (k-h) then the remainder is P(C, h)−(k−h).
Now consider h=−2 so 10−(−2)=12. P(137, −2)=1*4−3*2+7=5. But 137=11*12+5.
Again let h=2 and now let C=125. Then P(125, 2)=1*4+2*2+5=13. Applying the same operation to 13, P(13, 2)=1*2+3=5. On the other hand, 125=15*8+5.
Thus if P(C, k) = P(C, h) mod (k-h) and P(C, h) = P(D, k) then P(D, k) = P(D, h) (mod (k-h)). Modular equivalence is a transitive relation so P(C, k) = P(D, h) (mod (k-h)) where P(D, k)=P(C, h). This says the weighted summation of the coefficients of a polynomial should be repeated until the value is a single digit. If that digit is positive then it is the remainder. If it is negative then the remainder is (k-h) plus that digit. As noted above if the single digit is greater than (k-h) then the remainder is that single digit less (k−h). For (k-h) greater than 10 the multi-digit numbers beween 10 and (k-h) are effectively digits.
Suppose h=5 and k=10. Then (k−h)=5. Consider N=137. Then 25*1+5*3+7=47 and 5*4+7=27 and 5*2+7=17 and 5*1+7=12 and 5*1+2=7. Since 7>5 the remainder should be 7−5=2 and sure enough 137=27*8+2. ,
HOME PAGE OF Thayer Watkins |