Forward | Back | Table of Contents | About this document
a+(b+c) = (a+b)+c and a·(b·c) = (a·b)·c.
a+b = b+a and a·b = b·a.
a·(b+c) = (a·b) + (a·c) and (a+b)·c = (a·c) + (b·c).
a+0 = a and 0+a = a.
The set F also contains a multiplicative identity element, denoted by 1 (and assumed to be different from 0) such that for all a F,a·1 = a and 1·a = a.
a+x = 0 and x+a = 0
have a solution x F, called an
additive inverse
of a, and denoted by -a.
For each nonzero element a F,
the equations
a·x = 1 and x·a = 1
have a solution x F, called a multiplicative inverse of a, and denoted by a^{-1}.a_{m}x^{m} + a_{m-1}x^{m-1} + · · · + a_{1}x + a_{0}
is called a polynomial over F in the indeterminate x with coefficients a_{m}, a_{m-1}, . . . , a_{0}. The set of all polynomials with coefficients in F is denoted by F[x].f(x) = a_{n}x^{n} + · · · + a_{0}
has degree n, written deg(f(x)) = n, and a_{n} is called the leading coefficient of f(x).Two polynomials are equal by definition if they have the same degree and all corresponding coefficients are equal. It is important to distinguish between the polynomial f(x) as an element of F[x] and the corresponding polynomial function from F into F defined by substituting elements of F in place of x. If f(x) = a_{m}x^{m} + · · · + a_{0} and c F, then f(c) = a_{m}c^{m} + · · · + a_{0}. In fact, if F is a finite field, it is possible to have two different polynomials that define the same polynomial function. For example, let F be the field Z_{5} and consider the polynomials x^{5} -2x + 1 and 4x + 1. For any c Z_{5}, by Fermat's theorem we have c^{5} c (mod 5), and so
c^{5} -2c + 1 -c + 1 4c + 1 (mod 5),
which shows that x^{5} -2x + 1 and 4x + 1 are identical, as functions.For the polynomials
f(x) = a_{m}x^{m} + a_{m-1}x^{m-1} + · · · + a_{1}x + a_{0}
and
g(x) = b_{n}x^{n} + b_{n-1}x^{n-1} + · · · + b_{1}x + b_{0},
a_{m}b_{n}x^{n+m} + · · · + (a_{2}b_{0} + a_{1}b_{1} + a_{0}b_{2})x^{2} + (a_{1}b_{0} + a_{0}b_{1})x + a_{0}b_{0}.
The coefficient c_{k} of x^{k} in f(x)g(x) can be described by the formulac_{k} = a_{i} b_{k-i}.
This definition of the product is consistent with what we would expect to obtain using a naive approach: Expand the product using the distributive law repeatedly (this amounts to multiplying each term be every other) and then collect similar terms.4.1.5. Proposition. If f(x) and g(x) are nonzero polynomials in F[x], then f(x)g(x) is nonzero and
deg(f(x)g(x)) = deg(f(x)) + deg(g(x)).
4.1.6. Corollary. If f(x),g(x),h(x) F[x], and f(x) is not the zero polynomial, thenf(x)g(x) = f(x)h(x) implies g(x) = h(x).
4.1.7. Definition. Let f(x),g(x) F[x]. If f(x) = q(x)g(x) for some q(x) F[x], then we say that g(x) is a factor or divisor of f(x), and we write g(x) | f(x).4.1.8. Lemma. For any element c F, and any positive integer k,
(x - c) | (x^{k} - c^{k}).
4.1.9. Theorem. [Remainder Theorem] Let f(x) F[x] be a nonzero polynomial, and let c F. Then there exists a polynomial q(x) F[x] such thatf(x) = q(x)(x - c) + f(c).
Moreover, if f(x) = q_{1}(x)(x - c) + k, where q_{1}(x) F[x] and k F, then q_{1}(x) = q(x) and k = f(c).4.1.10. Definition. Let f(x) = a_{m}x^{m} + · · · + a_{0} F[x]. An element c F is called a root of the polynomial f(x) if f(c) = 0, that is, if c is a solution of the polynomial equation f(x) = 0 .
4.1.11. Corollary. Let f(x) F[x] be a nonzero polynomial, and let c F. Then c is a root of f(x) if and only if x-c is a factor of f(x). That is,
f(c) = 0 if and only if (x-c) | f(x).
4.1.12 Corollary. A polynomial of degree n with coefficients in the field F has at most n distinct roots in F.4.2.1. Theorem. [Division Algorithm] For any polynomials f(x) and g(x) in F[x], with g(x) 0, there exist unique polynomials q(x),r(x) F[x] such that
f(x) = q(x)g(x) + r(x),
where either deg(r(x)) < deg(g(x)) or r(x) = 0.4.2.2. Theorem Let I be a subset of F[x] that satisfies the following conditions:
I = { f(x) F[x] | f(x)=q(x)d(x) for some q(x) F[x] }.
4.2.3. Definition. A monic polynomial d(x) F[x] is called the greatest common divisor of f(x),g(x) F[x] if
4.2.4. Theorem. For any nonzero polynomials f(x),g(x) F[x] the greatest common divisor gcd(f(x),g(x)) exists and can be expressed as a linear combination of f(x) and g(x), in the form
gcd(f(x),g(x)) = a(x)f(x) + b(x)g(x)
for some a(x),b(x) F[x].Example. 4.2.3. (Euclidean algorithm for polynomials) Let f(x),g(x) F[x] be nonzero polynomials. We can use the division algorithm to write
f(x) = q(x)g(x) + r(x),
with deg(r(x))<deg(g(x)) or r(x) = 0.
gcd(f(x),g(x)) = a(x)f(x) + b(x)g(x)
can be found just as for integers (see the Euclidean algorithm for integers).4.2.5. Proposition. Let p(x),f(x),g(x) F[x]. If gcd(p(x),f(x)) = 1 and p(x) | f(x)g(x), then p(x) | g(x).
4.2.6. Definition. A nonconstant polynomial (that is, a polynomial with positive degree) is said to be irreducible over the field F if it cannot be factored in F[x] into a product of polynomials of lower degree. It is said to be reducible over F if such a factorization exists.
4.2.7. Proposition. A polynomial of degree 2 or 3 is irreducible over the field F if and only if it has no roots in F.
4.2.8 Lemma. The nonconstant polynomial p(x) F[x] is irreducible over F if and only if for all f(x),g(x) F[x],
p(x) | (f(x)g(x)) implies p(x) | f(x) or p(x) | g(x).
4.2.9. Theorem. [Unique Factorization] Any nonconstant polynomial with coefficients in the field F can be expressed as an element of F times a product of monic polynomials, each of which is irreducible over the field F . This expression is unique except for the order in which the factors occur.4.2.10. Definition. Let f(x) F[x]. An element c F is said to be a root of multiplicity n 1 of f(x) if
(x - c)^{n} | f(x) but (x - c)^{n+1} f(x).
4.2.11. Proposition. A nonconstant polynomial f(x) over the field R of real numbers has no repeated factors if and only if gcd(f(x),f'(x))=1, where f'(x) is the derivative of f(x).
Example. 4.2.4. (Partial fractions)
Let f(x)/g(x) be a rational function.
The first step in achieving a partial fraction decomposition of f(x)/g(x)
is to use
Theorem 4.2.9
to write g(x) as a product of irreducible polynomials.
If g(x)=p(x)q(x), where p(x) and q(x) are relatively prime, then by
Theorem 4.2.4
there exist polynomials a(x) and b(x) with
a(x)p(x)+b(x)q(x)=1.
Dividing by p(x)q(x) allows us to write1 / p(x)q(x) = a(x)/q(x) + b(x)/p(x),
and sof(x) / g(x) = (f(x)a(x)) / q(x) + (f(x)b(x)) / p(x).
This process can be extended by induction until f(x)/g(x) is written as a sum of rational functions, where in each case the denominator is a power of an irreducible polynomial.The next step in the partial fraction decomposition is to expand the terms of the form h(x)/p(x)^{n}. Using the division algorithm, we can write
h(x) / p(x)^{n} = a(x) + r(x)/p(x)^{n},
where deg(r(x)) < deg(p(x)^{n}). Then we can divide r(x) by p(x)^{n-1} to obtainr(x) = b(x)p(x)^{n-1} + c(x),
where deg(c(x)) < deg(p(x)^{n-1}). This gives usr(x) / p(x)^{n} = b(x)/p(x) + c(x)/p(x)^{n},
in which deg(b(x)) < deg(p(x)). This can be continued by induction, to obtainh(x) / p(x)^{n}= a(x) + b(x)/p(x) + · · · + t(x)/p(x)^{n},
in which the numerators b(x),...,t(x) all have lower degree than that of p(x).4.4.2. Definition. Let F be a field, and let p(x) be a fixed polynomial over F. If a(x),b(x) F[x], then we say that a(x) and b(x) are congruent modulo p(x), written
a(x) b(x) (mod p(x)),
if p(x) | (a(x)-b(x)). The set{ b(x) F[x] | a(x) b(x) (mod p(x)) }
is called the congruence class of a(x), and will be denoted by [a(x)].F[x]/<p(x)>.
4.4.3. Proposition. Let F be a field, and let p(x) be a nonzero polynomial in F[x]. For any a(x) F[x], the congruence class [a(x)] modulo p(x) contains a unique representative r(x) with deg(r(x))<deg(p(x)) or r(x)=0.4.4.4. Proposition. Let F be a field, and let p(x) be a nonzero polynomial in F[x]. For any polynomials a(x),b(x),c(x), and d(x) in F[x], the following conditions hold:
a(x)+b(x) c(x)+d(x) (mod p(x))
anda(x)b(x) c(x)d(x) (mod p(x)).
a(x)b(x) a(x)c(x) (mod p(x))
impliesb(x) c(x) (mod p(x)).
4.4.6. Theorem. Let F be a field, and let p(x) be a nonconstant polynomial over F. Then F[x]/<p(x)> is a field if and only if p(x) is irreducible over F.
4.4.7. Definition. Let F_{1} and F_{2} be fields. A function : F_{1} -> F_{2} is called an isomorphism of fields if
4.4.9 Corollary. Let F be a field, and let f(x) be any nonconstant polynomial in F[x]. Then there exists an extension field E of F over which f(x) can be factored into a product of linear factors.
4.3.2. Definition. A polynomial with integer coefficients is called primitive if the greatest common divisor of all of its coefficients is 1.
4.3.3 Lemma. Let p be a prime number, and let f(x) = g(x)h(x), where
4.3.4. Theorem. [Gauss's Lemma] The product of two primitive polynomials is itself primitive.
4.3.5. Theorem. A polynomial with integer coefficients that can be factored into polynomials with rational coefficients can also be factored into polynomials of the same degree with integer coefficients.
4.3.6. Theorem. [Eisenstein's Irreducibility Criterion] Let
f(x) = a_{n}x^{n} + a_{n-1}x^{n-1} + · · · + a_{0}
be a polynomial with integer coefficients. If there exists a prime number p such thata_{n-1} a_{n-2} . . . a_{0} 0 (mod p) but
a_{n} 0 (mod p) and a_{0} 0 (mod p^{2}),
then f(x) is irreducible over the field of rational numbers.4.3.7 Corollary. If p is prime, then the polynomial
(x) = x^{p-1} + · · · + x + 1
is irreducible over the field of rational numbers.A.5.2 Theorem. [DeMoivre] For any positive integer n,
( cos + i sin)^{n} = cos(n) + i sin(n).
A.5.3. Corollary. For any positive integer n, the equation z^{n} = 1 has n distinct roots in the set of complex numbers.
Definition.
The roots in C of the polynomial
x^{n}-1 are called the complex
nth roots of unity.
A complex nth root of unity is said to be
primitive
if it is a root of the polynomial x^{n}-1,
but is not a root of x^{m}-1
for any positive integer m<n.
Example. A.5.3. If z^{n} = u, then (z)^{n} = u, where is any nth root of unity. Thus if all nth roots of unity are already known, it is easy to find the nth roots of any complex number. In general, the nth roots of r(cos + i sin) are
r^{1/n} (cos ((+ 2k)/n) + i sin ((+ 2k)/n)),
for 1 k n.A.5.4. Theorem. [Fundamental Theorem of Algebra] Any polynomial of positive degree with complex coefficients has a complex root.
A.5.5. Corollary. Any polynomial f(z) of degree n > 0 with complex coefficients can be expressed as a product of linear factors, in the form
f(z) = c (z-z_{1}) (z-z_{2}) · · · (z-z_{n}).
If z = a+bi is a complex number, then its complex conjugate, denoted by z*, is z* = a-bi. Note that zz* = a^{2} + b^{2} and z+z* = 2a are real numbers, whereas z-z* = (2b)i is a purely imaginary number. Furthermore, z = z* if and only if z is a real number ( i.e., b = 0). It can be checked that (z+w)* = z*+w* and (zw)* = z*w*.A.5.6. Proposition. Let f(x) be a polynomial with real coefficients. Then a complex number z is a root of f(x) if and only if z* is a root of f(x).
A.5.7. Theorem. Any polynomial with real coefficients can be factored into a product of linear and quadratic terms with real coefficients.
A.5.8. Corollary. Any polynomial of odd degree that has real coefficients must have a real root.