San José State University

applet-magic.com
Thayer Watkins
Silicon Valley,
& the Gateway
to the Rockies
USA

The Remainder for the Division of a
Polynomial by a Quantity in Relation to
the Corresponding Weighted Sum
with Respect that Quantity

## Conditions and Definitions

Let PB be a polynomial in base B with integral coefficients, The base may be any positive integer. Let m be any positive integer. The weighted sum of a linear term aB + b is wa+b where the weight w is (B−m). The weighted summation is applied to the coeffcients of the highest power and next highest power in B. Itis denoted as SB(n, m). It is reapplied until the result is a constant term not involving the base B. That result is called the weighted sum of the polynomial. and denoted as DB(n, m).

## Theorem

The remainder of a polynomial PB with respect to division by m is the same as the remainder of the divsion by m of the weighted sum with respect to m of the polynomial. In symbols

## Proof

Let n be aB+b and n=km+r. Then

#### Sm(n) = (B−m)a + b = Ba + b −ma = km +r −ma = (k−a)m + r

So Sm(n) is a new number n' with new coefficients a' and b' with new multiple k'=k−a of m, but the same remainder r with respect to division by m. The major problem is the computation of the new cefficients a' and b'. The conditions to be satisfied are:

#### n' = a'B + b' = (k - a)m + r = (B−m)a + b

So Sm(n) is less than n and has the same remainder as n upon division by m. If n is a multiple of m the first single term value that is encountered in the successive weighted sums is the largest multiple of m less thsn B.

If n is not a multiple of m the first single digit value that is encountered in the successive weighted sums is the remainder r upon division of n by m.

## Illustrations

Consider n=125 as a decimal numer (powers of 10) and m=8. The weight for 8 is 10−8=2. Weighted summation is applied to the first two digits of 125. That results in 4. The third digit of 125 is appended to the 4 to give 45. The weighted sum of 45 is 2*4+5=13 and the weighted sum 13 is 2*1+3=5. The remainder after division of 125 by 8 is indeed 5.

Now consider n=128, a multiple of 8. Thus the remainder for 128 divided by 8 is 0. As in the above the weighted summation of the first two digits of 128 is 4. The third digit appended to 4 gives 48. The weighted summation of 48 is 16 and the weighted summation of 16 is 8. Thus the weighted digit sum of 128 with respect to 8 is 8, as the theorem says. But 8 is equivalent to 0 with respect to remainders for division by 8.

Consider again 128 but with m=4 and thus a weight of 6. The remainder for the division of 128 by 4 is 0. The weighted summation of the first two digits of 128 is 8. This with the third digit appended is 88. The weighted summation of 88 with respect to 4 is 48+8=56. The weighted summation of 56 is 36 and the weighted summation of that is 24. The next successive weighted sums are 16, 12 and finally 8. Thus the weighted digit sum of 128 with respect to 4 is 8, which is 2(4)as the theorem says.

## A Bizaare Illustration

The base B of a polynomial doesn't have to be limited to a positive integer and neither does the divisor m

For an illustration let

Let m=√2

Then

#### n/m =5.2501 and so5 n = 5m + 0.3537 and thus Rem(n, m) = 0.3537

The weight for √2 is 1.7274. Thus

## Conclusions

The well known fact that the digit sums of the multiples of 9 are all equal to 9 can be marvelously generalized. The less well known fact that the digit sum of any number that is not a multiple of 9 is equal to its positive remainder upon division by 9 also can be generalized.

If Rem(n, m) is the remainder function for the division of n by m the general relationship is

#### Rem(n, m) = Rem(Dm(n))

where Dm(n) is the weighted sum of the coefficients of n with respect to m.