San José State University |
---|
applet-magic.com Thayer Watkins Silicon Valley & Tornado Alley USA |
---|
Divisibility and Remainders for the Division of Polynomials |
---|
It was found first that the sum of the digits of a decimal number is essentially equal to its remainder upon division by 9. Furthermore the remainder modulo 9 of the product of two numbers is equal to the remainder modulo 9 of the product of the remainders of the two numbers. This is a property of remainder arithmetic. Later it was found that the net sum of the digits of a decimal number created by alternately adding and subtracting its digits is equal its remainder upon division by 11.
A decimal representation of a number is a polynomial in powers of ten. The above relationships generalize, as shown below, to the representations of numbers to any other integer base beside ten. They further generalize to polynomials with coefficients and base of any real numbers or any other mathematical field, but that is a different story that will be dealt with elsewhere.
Consider a polynomial
where C is the sequence of coefficients c_{n}c_{n-1}…c_{1}c_{0}, which 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.
The sum of the coefficient can be represented as the value of P(C, k) with k set equal to 1; i.e.,
Likewise the alternating net sum of the digits of a number is equal to the value of P(C, k) with k set equal to −1; i.e.,
There is also the trivial special case of the remainders modulo k, [P(C, k) mod k] which is equal to c_{0}. This is the value of P(C, k) with k set equal to zero.
Note that
This is established by representing the two terms created from the LHS as
Thus the lemma:
Now 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
Thus 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.
Note the special cases
Let N, M and p be three numbers. The remainders r and s of N and M, respectively, with respect to p are numbers 0≤r<p and 0≤s<p such that there exist two integers K and L such that
Let Rem(Q, p) denote the remainder function, the remainder of q with respect to p. Then
And
The proofs consist of noting that Kp and Lp, the multiples of p in N and M are irrelevant in determining the remainders.
Now consider two polynomials in k, P(C , k) and P(D, k) and form their sum S(C+D, k)=P(C, k)+P(D, k) and their product Q(E, k)=P(C, k)*P(D, k). Then
and
Restated these are:
HOME PAGE OF Thayer Watkins |