San José State University

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

Divisibility and Remainders
for Polynomials over a Field

Background

A field is a mathematical structure consisting of a set of elements and two binary functions called addition and multiplication, both of which are associative. Addition is communicative and there exists an identity element. Also there exist an additive inverse for every element. Multiplication is not necessarily communicative but there does exist a multiplicative identity. There exist muliplicative inverves for all elements except the additive identity.

Let F be a field with S the set of its elements and its two operation denoted by + and juxtaposition for addition and multiplication, respectively. The additive and multiplicative identities are denoted as 0 and1, respectively . The additive inverse of an element x is denoted as −x. The multiplicative inverse of x is denoted as x−1.

A polynomial over F is of the form

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

where the coefficients cj and the base of the polynomical k belong to S and n is a nonnegative integer.

The largest power n in a polynomial is called its degree and the smallest power m with a nonzero coefficient will be called its minimum power, The difference (n−m) will be called the degree span of the polynomial.

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. The concept of a remainder requires an order relation, which is not part of the structure of a field. Later it was found that the net sum of the digits of a decimal number created a alternately adding and subtracting its digits is equal its remainder upon division by 11.

Polynomials over a Field

Consider a polynomial

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

where C is the sequence of coefficients in F, cncn-1…c1c0, and k is an element of F. The sequence C. can be considered a representation of the element N=P(C, k) to the base k..

The sum of the coefficients can be represented as the value of P(C, k) with k set equal to the multiplicative identity 1; i.e.,

[cn+cn-1+…+c1+c0] = P(C, 1)

Likewise an alternating net sum of the coefficients of a polynomial is equal to the value of P(C, k) with k set equal to the additive inverse of the multiplicative identity, −1; i.e.,

[(−1)ncn+(−1)n-1cn-1+…−1c1+c0] = P(C, −1)

There is also the trivial special case of the constant term c0, which. is the value of P(C, k) with k set equal to the additive identity 0.

Two Divisibility Lemmas

For the following it is necessary to assume that the multiplication function for the field is commutative. Let h be any element of the commutative field F except k and let (k+(−h)) be denoted as (k−h). Note that

(kn-1 + kn-2h + kn-3h² + … + khn-2 + hn-1)(k−h)
= kn − hn

This is established by representing the two terms created from the LHS as

kn + kn-1h + kn-2h² + … + k²hn-2 +khn-1
               − (kn-1h + kn-2h² + kn-3h³ + … + khn-1 + hn)
        __________________________________________
kn − hn

Thus the lemma:

Lemma1: For all n, (k−h) is a factor of kn−hn.

Now consider the polynomial

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

and form P(C, h) and [ P(C, k) − P(C, h)]

[ P(C, k) − P(C, h)] = cn(kn−hn) + cn-1(kn-1−hn) + … + c1(k−h)

Note that (k−h) is a factor of each term of the above and therefore is a factor of the sum. Consequently

Lemma 2: For any polynomial P(C, k), [P(C, k) − P(C, h)] is divisible by (k−h).

This means that

[P(C, k) − P(C, h)] = Q(k−h)

where Q is a polynomial in k and h. Hence

P(C, k) = P(C, h) mod (k−h)

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 mentioned previously

P(C, k) = P(C, 1) mod (k− 1)
P(C, k) = P(C, −1) mod (k+1)
because (k−(−1))=(k+1)
P(C, k) = P(C, 0) mod k

Defining a Remainder
for Polynomial Division

Let N and P be two polynomials over F with degrees respectively of n and p, where p<n. The remainder R of N with respect to P is a polynomial of degree r such that r is less than the minimum power of N and 0≤r<p and such that there exist a polynomial Q such that the degree q of Q is (n-p) and

N = QP + R

Two Lemmas Concerning the
Sum and Product of Two Polynomials

Let Rem(Q, L) denote the remainder function, the remainder of Q with respect to L. Then

Lemma 3:
Rem(N+M, L) = Rem(Rem(N, L)+Rem(M, L), L)

And

Lemma 4:
Rem(N*M, L= Rem(Rem(N, L)*Rem(M, L), L)

The proofs consist of noting that the multiples of L in N and M are irrelevant in determining the remainders.

Remainders for Sums and
Products of Polynomials

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

S(C+D, h) = P(C, h) + P(D, h)
which is the same as
[S(C+D, k) mod (k−h)] = [P(C, k) mod (k−h)] + [P(D, k) mod (k−h)]

and

Q(E, h) = P(C, h)*P(D, h)
which is the same as
[Q(E, k) mod (k−h)] = [P(C, k) mod (k−h)]*[P(D, k) mod (k−h)]

Restated these are:

Lemma 5:
Rem(P(C, k) + P(D, k), (k−h)) = Rem(Rem(P(C, k), (k−h))+P(D, k), (k−h))) = Rem(P(C, h)+P(D, h), (k−h))

Lemma 6:
Rem(P(C, k)*P(D, k), (k−h)) = Rem(Rem(P(C, k), (k−h))*P(D, k), (k−h))) = Rem(P(C, h)*P(D, h), (k−h))


HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins