San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
& Tornado Alley
USA

The Relationship between the
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

P(C, k) = cnkn + cn-1kn-1 + … + c1k + c0

where C is the sequence of coefficients cncn-1…c1c0. 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 { cj 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

P(C, k) = P(C, h) modulo (k-h)

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.

Illustrations for Decimal Numbers

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 c0, 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 applet-magic
HOME PAGE OF Thayer Watkins