San José State University
Thayer Watkins
Silicon Valley
& Tornado Alley

Divisibility, Quotients and Remainders
for Polynomials over a Commutative Field


This material is to extend a result found for decimal numbers (which are simply polynomials in powers of ten) to polynomials over fields in general. Here is that result for ordinary decimal numbers. Take the number 1234. Its digit sum is 10. This means that 1234−10=1224 is exactly divisible by 10-1=9. In fact 1224=9*136. The cumulative sums of the digits of 123 are 1, 3, 6. Thus the quotient should be 136 and it is.

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 commutative and there exists an identity element. Also there exist an additive inverse for every element. Multiplication is not necessarily commutative but there does exist a multiplicative identity. There exist muliplicative inverves for all elements except the additive identity. However, for the following it is necessary the multiplication function to be commutative.

Let F be a commutative 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.

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)

Two Divisibility Lemmas
for Polynomials over a Commutt

Let h be any element of F except k and let (k+(−h)) be denoted as (k&ninus;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).

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

A Lemma Concerning the Quotient

For typographic convenience let (k+(−1)) be denoted as q. Then the number (km+(−1)) is the number qq…qq in the base k with the number of q's being m. This number is equal to q(1111). This means that in the quotient Q=dn-1kn-1…d1k+d01 of (P(C, k)−P(C, 1)) divided by q the coefficients are given by

dn-1 = cn
dn-2 = cn + cn-1
dn-3 = cn + cn-1 + cn-2
… …
d1 = cn + cn-1 + … + c2
d0 = cn + cn-1 + … + c2 + c1

In words, this means that the coefficients in the quotient are the cumulative sums from the left (the highest power of the base of the polynomial) of the coefficients of the polynomial excluding the coefficient of the multiplicative identity on the right. Thus quotient property that holds concerning decimal numbers and division by 9 holds holds for polynomials over a field and division by the base of the polynomial less the multiplicative identity of the field.

HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins