# 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$_n$x$^n$ above:
* a$_n$ is called the leading coefficient
** Given 7x$^3$+2x+5 , 7 is the leading coefficient
* the polynomial has degree n
** 7x$^3$+2x+5 , 3 is the degree
* if a$_n$=1 the polynomial is termed monic
** 7x$^3$+2x+5 is not monic, whereas x$^4$ and x$^5$-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$^3$+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$^3$/x = x$^2$, so we place a 1 in the second column to get
    ${\begin{matrix}&&&&1&&&\\1&-1&|&1&0&1&2&\\\end{matrix}}$
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:
    ${\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$^2$ now (since we have subtracted and gotten (1 1) - x$^2$ + 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$^2$+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$^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$+2x+1)
    x$^2$+2x+1=(x$^2$-1)*1+2x+2
    x$^2$-1=(2x+2)*x/2+ -(x+1)
    2x+2=-(x+1)*(-2)+0
Since factors of -1 make no difference, gcd(x$^2$-1,x$^2$+2x+1) is -(x+1)

### Irreducibles

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

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

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$+2x,x$^2$+2x+1,x$^2$+2x+2}
We can identify the irreducible quadratics easily by inspection. We then obtain
    {x$^2$+1, x$^2$+x+2, x$^2$+2x+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.
    ${\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$^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

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.