Back to the on-screen lesson ·
Polynomials over a field behave like the integers because they can be divided with a remainder of lower degree — which gives Euclid's algorithm, principal ideals and the whole parallel.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to use the degree rule for products and quotients, carry out polynomial long division and say why it terminates, identify the units of a polynomial ring, state where the coefficients being a field is needed, run Euclid's algorithm on two polynomials, and prove that every ideal of a polynomial ring in one variable is principal.
The integers were the running example of unit 5: a domain that is not a field, with every ideal the multiples of one number, and primes at the bottom of every factorisation. The polynomials over a field have every one of those properties, for one reason — they can be divided with a remainder — and the parallel is exact enough to be worth following deliberately.
The degree of a non-zero polynomial is the exponent of its highest term; the zero polynomial is given no degree. A polynomial is monic when its leading coefficient is $1$. The division algorithm in $F[x]$ writes $f = qg + r$ with $r = 0$ or $\deg r < \deg g$. A principal ideal domain is an integral domain in which every ideal is generated by one element.
$F[x]$ is the ring of polynomials in one variable with coefficients in a field $F$, added and multiplied as usual. Three facts, and the third does all the work.
Degrees add. $\deg(fg) = \deg f + \deg g$, because the top coefficient of the product is the product of the top coefficients, which is non-zero because $F$ is a field. Consequences: $F[x]$ is an integral domain, and its units are exactly the non-zero constants, since $fg = 1$ forces both degrees to be zero.
The division algorithm. For $g \ne 0$ there are unique $q$ and $r$ with
$$f = qg + r, \qquad r = 0 \text{ or } \deg r < \deg g.$$
The algorithm is long division: kill the leading term of $f$ by subtracting $\frac{\text{lead } f}{\text{lead } g} x^{\deg f - \deg g} g$, and repeat. Each step lowers the degree, so it stops. $F$ must be a field: that fraction is where an inverse is needed.
Every ideal is principal. Take the non-zero element of least degree in the ideal and divide everything else by it; the remainder is in the ideal and of lower degree, so it is zero. So $F[x]$ is a principal ideal domain.
From there the parallel with $\mathbb{Z}$ runs as far as anyone needs:
| In the integers | In $F[x]$ |
|---|---|
| size of a remainder | degree of a remainder |
| Euclid's algorithm | Euclid's algorithm |
| $\gcd(a, b) = ax + by$ | $\gcd(f, g) = fu + gv$ |
| prime numbers | irreducible polynomials |
| unique factorisation | unique factorisation |
| $\mathbb{Z}/(p)$ is a field | $F[x]/(p)$ is a field |
The last row is the construction of the finite fields, three lessons away.
Another way: picture
Long division of numbers works because each step leaves a smaller remainder, and there is no infinite descent through the positive integers. Long division of polynomials works because each step leaves a remainder of lower degree, and there is no infinite descent through the non-negative integers either. The two algorithms are the same algorithm with a different measure of smaller, and every theorem that follows from one follows from the other.
Another way: steps
To divide $f$ by $g$: 1. If $\deg f < \deg g$, stop: the quotient is $0$ and the remainder is $f$. 2. Otherwise divide the leading terms to get the next term of the quotient. 3. Multiply $g$ by that term and subtract; the degree drops. 4. Repeat until the degree falls below $\deg g$. 5. What is left is the remainder.
Because remainders get smaller, Euclid's algorithm runs in $F[x]$: to find $\gcd(f, g)$, replace the pair by $(g, r)$ and repeat until the remainder is zero; the last non-zero remainder is the highest common factor, defined up to a constant multiple and usually taken monic.
Run backwards it gives Bézout for polynomials: $\gcd(f, g) = fu + gv$ for some $u, v \in F[x]$. That identity is what inverts elements in $F[x]/(p)$, exactly as the integer version inverted elements modulo $p$ — so the last lesson of this course is a rerun of the proof that $\mathbb{Z}_p$ is a field.
Two places where the parallel needs care.
The coefficients must form a field. Over $\mathbb{Z}$, dividing $x^{2}$ by $2x$ leaves the ring, and $\mathbb{Z}[x]$ is not a principal ideal domain — the ideal generated by $2$ and $x$ needs both. It is still a unique factorisation domain, by a harder theorem.
One variable only. $F[x, y]$ is not a principal ideal domain either: the ideal generated by $x$ and $y$ needs both generators. The division algorithm has no straightforward analogue in two variables, and what replaces it — Gröbner bases — is a subject of its own.
So the clean statement is: $F[x]$ for a field $F$, in one variable, behaves like $\mathbb{Z}$. Both hypotheses are doing work, and knowing which theorems fail without them is most of what it means to understand the parallel rather than to recite it.
Dividing over a ring that is not a field. The algorithm needs the leading coefficient of the divisor to be invertible. Over $\mathbb{Z}$ it works only when that coefficient is $\pm 1$.
Giving the zero polynomial a degree. It has none. Conventions that assign it $-\infty$ exist to make the degree rule $\deg(fg) = \deg f + \deg g$ hold without exceptions; this course simply excludes it.
Thinking a polynomial of positive degree could be a unit. Degrees add, so an inverse would need degree $-\deg f$. The units are the non-zero constants and nothing else.
Confusing a polynomial with the function it defines. Over a finite field they differ: $x^{p} - x$ is a non-zero polynomial over $\mathbb{Z}_p$ that vanishes at every element. Everything here is about polynomials as formal expressions.
Expecting the results in two variables. $F[x, y]$ has non-principal ideals, and the division algorithm does not transfer.
Divide $x^{3} - 2x + 5$ by $x - 2$. First step: $x^{3}/x = x^{2}$, and subtracting $x^{2}(x - 2)$ leaves $2x^{2} - 2x + 5$.
Kill the leading term.
Next: $2x^{2}/x = 2x$, and subtracting $2x(x - 2)$ leaves $2x + 5$. Then $2x/x = 2$, and subtracting $2(x - 2)$ leaves $9$.
Two more steps.
So $x^{3} - 2x + 5 = (x^{2} + 2x + 2)(x - 2) + 9$. Check: the value at $x = 2$ is $8 - 4 + 5 = 9$, the remainder.
Quotient and remainder, verified.
Find $\gcd(x^{3} - 1, x^{2} - 1)$ over $\mathbb{Q}$. Divide: $x^{3} - 1 = x(x^{2} - 1) + (x - 1)$.
First remainder.
Now divide $x^{2} - 1$ by $x - 1$: it goes exactly, $x^{2} - 1 = (x + 1)(x - 1)$, remainder $0$.
Second step, and it terminates.
So the highest common factor is $x - 1$, the last non-zero remainder. As with integers, two steps and no factorising.
Euclid, unchanged.
Suppose $fg = 1$. Degrees add, so $\deg f + \deg g = \deg 1 = 0$.
Use the degree rule.
Both degrees are non-negative, so both are $0$: $f$ and $g$ are non-zero constants.
And every non-zero constant does have an inverse.
So the units are exactly the non-zero rationals, viewed as constant polynomials. In particular $x$ has no inverse, so the ring is a domain and not a field.
Over a field, $f$ has degree $8$ and $g$ has degree $2$. Fill in the degrees.
| Its degree | |
|---|---|
| the product of f and g | |
| the quotient on dividing f by g | |
| the remainder, at most |
Divide a polynomial over a field by one of degree $2$. At most what degree can the remainder have?
Answer:
Put the steps of dividing $x^{3} + 2x + 1$ by $x + 1$ over the rationals into order.
Number the steps in order (write the number in the box):
Divide $x^{2} + 1$ by each of these over the rationals, and match it to the remainder.
| remainder $1$ | remainder $2$ | remainder $5$ | remainder $10$ | remainder $0$ | |
|---|---|---|---|---|---|
| $x - 1$ | |||||
| $x - 2$ | |||||
| $x - 3$ | |||||
| $x$ |
Select every statement that is true of the polynomials over a field.
This task has no paper form; do it on a device.
Build the proof that every ideal of the polynomials over a field is generated by a single polynomial.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Over a field, $f$ has degree $7$ and $g$ has degree $2$. Fill in the degrees.
| Its degree | |
|---|---|
| the product of f and g | |
| the quotient on dividing f by g | |
| the remainder, at most |
You can divide one polynomial by another and say what the algorithm guarantees about the remainder. Say in your own words why the coefficients have to form a field. Next: roots, and the theorem that turns a remainder into a factor.
9. Your turn: what are the units of the polynomials over the rationals?, step 3