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

Divisibility, Quotients and Remainders
for Polynomials over a Commutative Ring


This material is to extend results found for decimal numbers (which are simply polynomials in powers of ten) to polynomials over as general an algebraic structure as possible. Here is that result for ordinary decimal numbers. Take the number 4321. Its digit sum is 10. This means that 4321−10=4311 is exactly divisible by 10-1=9. In fact 4311=9*479. The cumulative sums of the digits of 432 are 4, 7, 9. Thus the quotient should be 479 and it is.

A ring 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 additive identity element. Also there exist an additive inverse for every element. Multiplication distirbutes over addition; i.e., a(b+c)=ab+ac. For rings in general multiplication is not necessarily commutative but there does exist a multiplicative identity. However, for the following it is necessary the multiplication function to be commutative.

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

A polynomial over R 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 Commutative Ring

Consider a polynomial

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

where C is the sequence of coefficients in R, cncn-1…c1c0, and k is an element of R. 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 Commutative Ring

Let h be any element of R 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 + c01

and form P(C, h) and then [ 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).

A Lemma Concerning
the above 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 the quotient property that holds concerning decimal numbers and division by 9 also holds holds for polynomials over a commutative ring and division by the base of the polynomial less the multiplicative identity of the ring.

HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins