Discrete Mathematics/Polynomials

Introduction

In this section we look at the polynomial in some commutative ring with identity. What is interesting is that studying polynomials over some commutative ring with identity acts very much like numbers; the same rules often are obeyed by both.

Definitions

A polynomial over some commutative ring with identity R is an expression in the form

$\sum _{j=0}^{n}a_{j}x^{j};\forall a_{j}\in R,a_{n}\not =0$

and n ∈ N, and x is some indeterminate (not a variable).

Terminology

Given the first nonzero term in the polynomial, i.e. the term a_nxⁿ above:

• a_n is called the leading coefficient
  • Given 7x³+2x+5 , 7 is the leading coefficient
• the polynomial has degree n
  • 7x³+2x+5 , 3 is the degree
• if a_n=1 the polynomial is termed monic
  • 7x³+2x+5 is not monic, whereas x⁴ and x⁵-3x+2 are monic.

In the above, if a_i=0 for all i, the polynomial is the zero polynomial.

Properties

Let R[x] be the set of all polynomials of all degrees. Clearly R is closed under addition and multiplication (although in a non-straightforward way), and thus we have that R[x] is itself a commutative ring with identity.

Assume now R is a field F; we do this so we can define some useful actions on polynomials

Division algorithm

Firstly recall the division algorithm for numbers, that each number can be decomposed into the form

n = qk+r

where q is the quotient and r the remainder and r<n.

Now, since we have that F is a field, we can do something similar with the polynomials over F, F[x].

If f(x), g(x) ∈ F[x], with g(x) nonzero:

f(x) = q(x)g(x)+r(x)

Again, q(x) is known as the quotient polynomial and r(x) the remainder polynomial. Furthermore, we have the degree of r(x) ≤ degree of f(x)

We perform divisions by polynomial long division. For brevity we omit the x^k terms. Here's an example. We divide x³+x+2 by x-1. First write:

${\begin{matrix}&&&&&&&\\1&-1&|&1&0&1&2&\\\end{matrix}}$

Note we place a 0 in any polynomial not present. Now x³/x = x², so we place a 1 in the second column to get

${\begin{matrix}&&&&1&&&\\1&-1&|&1&0&1&2&\\\end{matrix}}$

Multiply x² throughout the divisor x-1 to get x³-x², which is (1 -1), so write this below like the following:

${\begin{matrix}&&&&1&&&\\1&-1&|&1&0&1&2&\\&&|&1&-1&&&\\\end{matrix}}$

Now subtract (1 0) and (1 -1), drop the third 1 to get:

${\begin{matrix}&&&&1&&&\\1&-1&|&1&0&1&2&\\&&|&1&-1&&&\\&&|&&1&1&&\\\end{matrix}}$

Now repeat, but divide by x² now (since we have subtracted and gotten (1 1) - x² + x), and continue in the same fashion, to get:

${\begin{matrix}&&&&1&1&2&\\1&-1&|&1&0&1&2&\\&&|&1&-1&&&\\&&|&&1&1&&\\&&|&&1&-1&&\\&&|&&&2&2&\\&&|&&&2&-2&\\&&|&&&&4&\\\end{matrix}}$

So the quotient is x²+x+2, and the remainder is 4.

Euclidean algorithm

Now we have a working division algorithm for polynomials, the Euclidean algorithm, and hence the gcd of two polynomials can readily be found.

Examples

Let's use a similar example above: what is gcd(x³+x+2, x-1)? We've shown already above that x³+x+2=(x²+x+2)(x-1) + 4

Proceeding in the normal fashion in the Euclidean algorithm

x³+x+2=(x²+x+2)(x-1) + 4

gcd(x³+x+2, x-1) = gcd(x-1,4)

and the greatest common divisor of any monomial and an integer is clearly 1, so x³+x+2 and x-1 are coprime.

For a second example, consider gcd(x²-1,x²+2x+1)

x²+2x+1=(x²-1)*1+2x+2

x²-1=(2x+2)*x/2+ -(x+1)

2x+2=-(x+1)*(-2)+0

Since factors of -1 make no difference, gcd(x²-1,x²+2x+1) is -(x+1)

Irreducibles

We've seen that x³+x+2 and x-1 are coprime; they have no factors in common. So, are we able to determine "prime" polynomials? Indeed we can - depending on the field that the polynomial lies in. We call these irreducibles instead of primes.

Example

Take p(x)=x³ + x² + 2 over Z₃. Now we can factor this polynomial if it has a root - from the factor theorem (which also holds for polynomials over any commutative ring with identity) p(k)=0 means k is a root. So, let's look at the following: Since we're in Z₃, we luckily only need to check three values p(0)=2 p(1)=1 p(2)=2 So we have p(x) having no roots - it is irreducible ("prime").

Now observe an interesting fact. Take the exact same polynomial but instead over Z₂. The polynomial then is equivalent to

x³+x²+0

and thus has root p(0)=0 and thus is reducible but over Z₂

So the reducibility of the polynomial depends on the field it is in.

Showing irreducibility

The general procedure to show a polynomial is irreducible is:

• observe its degree
• identify possible factorizations
• eliminate these factorizations

effectively a proof by cases.

For example, consider the polynomial q(x)=x⁴+x+2 in Z₃. To prove it is irreducible, observe that q(x) could be factorized in the following ways:

1. linear, irreducible cubic
2. linear, linear, irreducible quadratic
3. linear, linear, linear, linear
4. irreducible quadratic, irreducible quadratic

So we can prove 1, 2, 3 by showing it has no linear factors. 4 is a little more difficult. Let us proceed to show it has no linear factors: Observe

q(0)=2

q(1)=1

q(2)=2

So q has no linear factors. Now, we need to show that q is not the product of two irreducible quadratics.

In Z₃, we have the quadratics

{x²,x²+1,x²+x,x²+x+1,x²+x+2,x²+2,x²+2x,x²+2x+1,x²+2x+2}

We can identify the irreducible quadratics easily by inspection. We then obtain

{x²+1, x²+x+2, x²+2x+2}

If we can show that neither of these polynomials divide q(x)=x⁴+x+2, we have shown q(x) is irreducible.

Let us try x²+1 first.

${\begin{matrix}&&&&&&1&0&2\\1&0&1&|&1&0&0&1&2\\&&&&1&0&1&&\\&&&&&&2&1&2\\&&&&&&2&0&2\\&&&&&&&1&0\\\end{matrix}}$

We have a remainder, so x²+1 doesn't divide q. On dividing the other polynomials, we all get a remainder. (Verify this for yourself as practice).

So q(x) is irreducible in Z₃.

Modular arithmetic and polynomials

Since we have a working polynomial division and factor theorem, and that polynomials appear to mimic the behaviour of the integers - can we reasonably define some sort of modular arithmetic with polynomials?

We can indeed. If we have a field Z_p[x] and we wish to find all the remainders (remember, these remainders are polynomials) on dividing by some polynomial m(x), we can do so by polynomial long division.

If m(x) is irreducible, then the set of remainders as above forms a field.