# Discrete Mathematics/Polynomials

## Introduction[edit | edit source]

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[edit | edit source]

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

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

## Terminology[edit | edit source]

Given the first nonzero term in the polynomial, i.e. the term *a*_{n}x^{n} above:

*a*_{n}is called the*leading coefficient*- Given 7
*x*^{3}+2*x*+5 , 7 is the leading coefficient

- Given 7
- the polynomial has
*degree**n*- 7
*x*^{3}+2*x*+5 , 3 is the degree

- 7
- if
*a*_{n}=1 the polynomial is termed*monic*- 7
*x*^{3}+2*x*+5 is*not monic*, whereas*x*^{4}and*x*^{5}-3*x*+2 are*monic*.

- 7

In the above, if *a*_{i}=0 for all i, the polynomial is the *zero polynomial*.

## Properties[edit | edit source]

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[edit | edit source]

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*^{3}+*x*+2 by *x*-1. First write:

Note we place a 0 in any polynomial not present. Now *x*^{3}/*x* = *x*^{2}, so we place a 1 in the second column to get

Multiply *x*^{2} throughout the divisor *x*-1 to get *x*^{3}-*x*^{2}, which is (1 -1), so write this below like the following:

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

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

So the quotient is *x*^{2}+*x*+2, and the remainder is 4.

### Euclidean algorithm[edit | edit source]

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

#### Examples[edit | edit source]

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

Proceeding in the normal fashion in the Euclidean algorithm

*x*^{3}+*x*+2=(*x*^{2}+*x*+2)(*x*-1) + 4- gcd(
*x*^{3}+*x*+2,*x*-1) = gcd(*x*-1,4)

and the greatest common divisor of any monomial and an integer is clearly 1, so *x*^{3}+*x*+2 and *x*-1 are coprime.

For a second example, consider gcd(*x*^{2}-1,*x*^{2}+2*x*+1)

*x*^{2}+2*x*+1=__(__*1+*x*^{2}-1)__2__*x*+2*x*^{2}-1=__(2__**x*+2)*x*/2+__-(x+1)__- 2
*x*+2=__-(x+1)__*(-2)+__0__

Since factors of -1 make no difference, gcd(*x*^{2}-1,*x*^{2}+2*x*+1) is -(*x*+1)

### Irreducibles[edit | edit source]

We've seen that *x*^{3}+*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[edit | edit source]

Take p(*x*)=*x*^{3} + *x*^{2} + 2 over **Z**_{3}. 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**_{3}, 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**_{2}. The polynomial then is equivalent to

*x*^{3}+*x*^{2}+0

and thus has root p(0)=0 and thus *is reducible* but *over* **Z**_{2}

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

### Showing irreducibility[edit | edit source]

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*^{4}+*x*+2 in **Z**_{3}. To prove it is irreducible, observe that q(*x*) could be factorized in the following ways:

- linear, irreducible cubic
- linear, linear, irreducible quadratic
- linear, linear, linear, linear
- 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**_{3}, we have the quadratics

- {
*x*^{2},*x*^{2}+1,*x*^{2}+*x*,*x*^{2}+*x*+1,*x*^{2}+*x*+2,*x*^{2}+2,*x*^{2}+2*x*,*x*^{2}+2*x*+1,*x*^{2}+2*x*+2}

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

- {
*x*^{2}+1,*x*^{2}+*x*+2,*x*^{2}+2*x*+2}

If we can show that neither of these polynomials divide q(*x*)=*x*^{4}+*x*+2, we have shown q(*x*) is irreducible.

Let us try *x*^{2}+1 first.

We have a remainder, so *x*^{2}+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**_{3}.

## Modular arithmetic and polynomials[edit | edit source]

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.