It will be very important to be able to work with polynomials in certain parts of linear algebra to be
presented later.
Definition 1.11.1A polynomial is an expression of the form a_{n}λ^{n}+a_{n−1}λ^{n−1}+
⋅⋅⋅
+a_{1}λ+a_{0}, a_{n}≠0
where the a_{i}come from a field of scalars. Two polynomials are equal means that the coefficientsmatch for each power of λ. The degree of a polynomial is the largest power of λ. Thus the degreeof the above polynomial is n. Addition of polynomials is defined in the usual way as ismultiplicationof two polynomials.The leading term in the above polynomial is a_{n}λ^{n}. The coefficient of the leadingterm is called the leading coefficient.It is called a monicpolynomial if a_{n} = 1.
Note that the degree of the zero polynomial is not defined in the above.
Lemma 1.11.2Let f
(λ )
and g
(λ)
≠0 be polynomials.Then there exist polynomials, q
(λ)
and r
(λ)
suchthat
f (λ) = q(λ)g (λ) + r(λ)
where the degree of r
(λ)
is less than the degree of g
(λ)
or r
(λ)
= 0. These polynomials q
(λ)
and r
(λ )
areunique.
Proof:Suppose that f
(λ)
− q
(λ)
g
(λ)
is never equal to 0 for any q
(λ)
. If it is, then the conclusion
follows. Now suppose
r(λ) = f (λ)− q (λ)g (λ )
and the degree of r
(λ )
is m ≥ n where n is the degree of g
(λ)
. Say the leading term of r
(λ)
is
bλ^{m} while the leading term of g
(λ)
is
ˆb
λ^{n}. Then letting a = b∕
ˆb
, aλ^{m−n}g
(λ)
has the same
leading term as r
(λ)
. Thus the degree of r_{1}
(λ)
≡ r
(λ )
− aλ^{m−n}g
(λ )
is no more than m − 1.
Then
( )
◜---q1◞(λ◟)---◝
r1(λ) = f (λ)− (q(λ)g(λ)+ aλm− ng(λ)) = f (λ)− |( q(λ)+ aλm −n|) g(λ)
Denote by S the set of polynomials f
(λ)
− g
(λ )
l
(λ)
. Out of all these polynomials, there exists one
which has smallest degree r
(λ)
. Let this take place when l
(λ)
= q
(λ)
. Then by the above argument, the
degree of r
(λ)
is less than the degree of g
(λ)
. Otherwise, there is one which has smaller degree. Thus
f
(λ )
= g
(λ)
q
(λ)
+ r
(λ)
.
As to uniqueness, if you have r
(λ)
,
ˆr
(λ)
,q
(λ)
,
ˆq
(λ)
which work, then you would have
(ˆq(λ)− q(λ))g(λ) = r(λ)− ˆr(λ)
Now if the polynomial on the right is not zero, then neither is the one on the left. Hence this would involve
two polynomials which are equal although their degrees are different. This is impossible. Hence r
(λ)
=
ˆr
(λ)
and so, matching coefficients implies that
qˆ
(λ)
= q
(λ)
. ■
Definition 1.11.3A polynomial f is said to dividea polynomial g if g
(λ)
= f
(λ)
r
(λ)
for somepolynomial r
(λ)
. Let
{ϕ (λ)}
i
be a finite set of polynomials. The greatest common divisorwill bethe monic polynomial q
(λ )
such that q
(λ)
divides each ϕ_{i}
(λ)
and if p
(λ)
divides each ϕ_{i}
(λ)
, thenp
(λ)
divides q
(λ)
. The finite set of polynomials
{ϕ }
i
is said to be relatively primeif their greatestcommon divisor is 1. A polynomial f
(λ)
is irreducibleif there is no polynomial with coefficients inF which divides it except nonzero scalar multiples of f
(λ)
and constants. In other words, it is notpossible to write f
(λ)
= a
(λ)
b
(λ)
where each of a
(λ)
,b
(λ)
have degree less than the degree of f
(λ )
.
Proposition 1.11.4The greatest common divisor is unique.
Proof: Suppose both q
(λ)
and q^{′}
(λ)
work. Then q
(λ)
divides q^{′}
(λ)
and the other way around and
so
q′(λ) = q (λ) l(λ),q(λ) = l′(λ)q′(λ )
Therefore, the two must have the same degree. Hence l^{′}
(λ)
,l
(λ )
are both constants. However, this
constant must be 1 because both q
(λ)
and q^{′}
(λ)
are monic. ■
Theorem 1.11.5Let
{ϕi(λ)}
be polynomials, not all of which are zero polynomials. Then there exists agreatest common divisor and it equals the monic polynomial ψ
(λ)
of smallest degree such that there existpolynomials r_{i}
(λ)
satisfying
p
ψ (λ ) = ∑ ri(λ )ϕi(λ ).
i=1
Proof: Let S denote the set of monic polynomials which are of the form
p
∑ ri(λ)ϕi (λ)
i=1
where r_{i}
(λ)
is a polynomial. Then S≠∅ because some ϕ_{i}
(λ)
≠0. Then let the r_{i} be chosen such that the
degree of the expression ∑_{i=1}^{p}r_{i}
(λ)
ϕ_{i}
(λ)
is as small as possible. Letting ψ
(λ)
equal this sum, it remains
to verify it is the greatest common divisor. First, does it divide each ϕ_{i}
by the leading coefficient if necessary
and denoting the result by ψ_{1}
(λ)
, it follows the degree of ψ_{1}
(λ)
is less than the degree of ψ
(λ)
and ψ_{1}
(λ)
equals for some a ∈ F
ψ1 (λ ) = (ϕ1(λ)− ψ(λ)l(λ))a
( )
∑p
= ϕ1(λ)− ri(λ)ϕi(λ)l(λ) a
( i=1 p )
∑
= (1− r1(λ))ϕ1(λ)+ (− ri(λ)l(λ))ϕi (λ) a
i=2
This is one of the polynomials in S. Therefore, ψ
(λ)
does not have the smallest degree after all because the
degree of ψ_{1}
(λ)
is smaller. This is a contradiction. Therefore, ψ
(λ)
divides ϕ_{1}
(λ)
. Similarly it divides all
the other ϕ_{i}
(λ)
.
If p
(λ)
divides all the ϕ_{i}
(λ)
, then it divides ψ
(λ)
because of the formula for ψ
(λ)
which equals
∑_{i=1}^{p}r_{i}
(λ)
ϕ_{i}
(λ)
. Thus ψ
(λ)
satisfies the condition to be the greatest common divisor. This shows the
greatest common divisor exists and equals the above description of it. ■
Lemma 1.11.6Suppose ϕ
(λ)
and ψ
(λ)
are monic polynomials which areirreducible and not equal.Then they are relatively prime.
Proof:Suppose η
(λ)
is a nonconstant polynomial. If η
(λ)
divides ϕ
(λ)
, then since ϕ
(λ)
is irreducible,
η
(λ)
equals aϕ
(λ)
for some a ∈ F. If η
(λ )
divides ψ
(λ)
then it must be of the form bψ
(λ)
for some b ∈ F
and so it follows
a-
ψ(λ) = bϕ(λ)
but both ψ
(λ)
and ϕ
(λ)
are monic polynomials which implies a = b and so ψ
(λ)
= ϕ
(λ)
. This is assumed
not to happen. It follows the only polynomials which divide both ψ
(λ )
and ϕ
(λ)
are constants and so
the two polynomials are relatively prime. Thus a polynomial which divides them both must
be a constant, and if it is monic, then it must be 1. Thus 1 is the greatest common divisor.
■
Lemma 1.11.7Let ψ
(λ)
be anirreducible monic polynomial not equal to 1 which divides
p∏ ki
ϕi(λ) ,ki a positive integer,
i=1
where each ϕ_{i}
(λ)
is an irreducible monic polynomial not equal to 1. Then ψ
(λ)
equals someϕ_{i}
(λ)
.
Proof :Say ψ
(λ)
l
(λ)
= ∏_{i=1}^{p}ϕ_{i}
(λ )
^{ki}. Suppose ψ
(λ)
≠ϕ_{i}
(λ)
for all i. Then by Lemma 1.11.6, there
exist polynomials m_{i}
(λ)
,n_{i}
(λ)
such that
1 = ψ(λ)mi (λ )+ ϕi(λ )ni(λ )
ϕ (λ) n (λ) = 1− ψ(λ)m (λ)
i i i
Hence,
(ϕi(λ) ni(λ))
^{ki} =
(1 − ψ(λ)mi (λ))
^{ki} and so letting n
(λ)
= ∏_{i}n_{i}
(λ)
^{ki},
∏p ki ∏p ki
n(λ)l(λ)ψ (λ) = (ni(λ) ϕi(λ)) = (1− ψ(λ)mi (λ))
i=1 i=1
= 1+ g (λ) ψ(λ)
for a suitable polynomial g
(λ)
. You just separate out the term 1^{ki} = 1 in that product and then all terms
that are left have a ψ
(λ)
as a factor. Hence
(n(λ)l(λ)− g (λ))ψ (λ) = 1
which is impossible because ψ
(λ)
is not equal to 1. ■
Of course, since coefficients are in a field, you can drop the stipulation that the polynomials are monic
and replace the conclusion with: ψ
(λ)
is a multiple of some ϕ_{i}
(λ)
.
Now here is a simple lemma about canceling monic polynomials.
Lemma 1.11.8Suppose p
(λ)
is a monic polynomial and q
(λ)
is a polynomial such that
p(λ)q (λ) = 0.
Then q
(λ)
= 0. Also if
p(λ)q1(λ) = p (λ)q2(λ)
then q_{1}
(λ)
= q_{2}
(λ)
.
Proof: Let
∑k j ∑n i
p (λ) = pjλ ,q (λ) = qiλ ,pk = 1.
j=1 i=1
Then the product equals
k n
∑ ∑ pjqiλi+j.
j=1 i=1
If not all q_{i} = 0, let q_{m} be the last coefficient which is nonzero. Then the above is of the form
∑k ∑m
pjqiλi+j = 0
j=1i=1
Consider the λ^{m+k} term. There is only one and it is p_{k}q_{m}λ^{m+k}. Since p_{k} = 1,q_{m} = 0 after all. The second
part follows from
p (λ )(q1(λ)− q2(λ)) = 0.■
The following is the analog of the fundamental theorem of arithmetic for polynomials.
Theorem 1.11.9Let f
(λ)
be a nonconstantpolynomial with coefficients in F. Then there is somea ∈ F such that f
(λ)
= a∏_{i=1}^{n}ϕ_{i}
(λ)
where ϕ_{i}
(λ)
is an irreducible nonconstant monic polynomialand repeats are allowed. Furthermore, this factorization is unique in the sense that any two of thesefactorizations have the same nonconstant factors in the product, possibly in different order and thesame constant a.
Proof:That such a factorization exists is obvious. If f
(λ)
is irreducible, you are done.
Factor out the leading coefficient. If not, then f
(λ)
= aϕ_{1}
(λ)
ϕ_{2}
(λ )
where these are monic
polynomials. Continue doing this with the ϕ_{i} and eventually arrive at a factorization of the desired
form.
It remains to argue the factorization is unique except for order of the factors. Suppose
n m
a∏ ϕ (λ) = b∏ ψ (λ)
i=1 i i=1 i
where the ϕ_{i}
(λ)
and the ψ_{i}
(λ)
are all irreducible monic nonconstant polynomials and a,b ∈ F. If n > m,
then by Lemma 1.11.7, each ψ_{i}
(λ)
equals one of the ϕ_{j}
(λ )
. By the above cancellation lemma, Lemma
1.11.8, you can cancel all these ψ_{i}
(λ)
with appropriate ϕ_{j}
(λ)
and obtain a contradiction because the
resulting polynomials on either side would have different degrees. Similarly, it cannot happen that n < m.
It follows n = m and the two products consist of the same polynomials. Then it follows a = b.
■
The following corollary will be well used. This corollary seems rather believable but does require a
proof.
Corollary 1.11.10Let q
(λ)
= ∏_{i=1}^{p}ϕ_{i}
(λ)
^{ki}where the k_{i}are positive integers and the ϕ_{i}
(λ)
areirreducible distinct monic polynomials. Suppose also that p
(λ)
is a monic polynomial which divides q
(λ)
.Then
p
p (λ) = ∏ ϕi(λ)ri
i=1
where r_{i}is a nonnegative integer no larger than k_{i}.