Polynomials

Chapter IV: The ring of polynomials

HIS - L1 Informatique

W. DJELLADJ

9 janvier 2026

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Polynomials

Teaching content

1 Polynomials
Definitions, notations
Basics operations
Roots and factorization
Roots and factorization

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Introduction

Here, (K, +, ×) is a commutative field witch can represent :

• The field Q,
• The field R,
• The field C,

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Definitions, notations
Polynomial function, formal polynomial
• A polynomial function with coefficient in K is :
i=n
X
P(X ) = ai X i = a0 X 0 + a1 X 1 + · · · + an X n
i=0

• A formal polynomial with a coefficient in K is a sequence

(an )n∈N on K, where ∃N ∈ N : ∀n ∈ N (n > N =⇒ an = 0).
With n ∈ N and a0 , a1 , . . . , an ∈ K. Polynomials set is : K[X ].

3
X 3 − 5X + 4 is a polynomial of degree 3
Xn + 1 is a polynomial of degree n.
2 is constant polynomial of degree 0.
W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique
 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Basics notations

Basics notations
The ai are coefficients of the polynomial.
If ai = 0, ∀i, P is called the zero polynomial, it is denoted 0K .
We call the degree of P the largest integer i such that ai 6= 0 ;
we denote it deg P.
By convention, the zero polynomial has : deg(0) = −∞.
P = a0 with a0 ∈ K is a constant polynomial. If a0 6= 0, its
degree is 0.
If deg (P) = n, then (an ) is the dominant coefficient. If
(an ) = 1, then P is unitary.

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Basics operations
Equality
Let P = an X n + an−1 X n−1 + · · · + a1 X + a0 and
Q = bn X n + bn−1 X n−1 + · · · + b1 X + b0 two polynomials on K.

P=Q ⇐⇒ ∀i ai = bi

we say that P are Q equal.

Addition
Let P = an X n + an−1 X n−1 + · · · + a1 X + a0 and
Q = bn X n + bn−1 X n−1 + · · · + b1 X + b0 .
We define :

P+Q = (an +bn )X n +(an−1 +bn−1 )X n−1 +· · ·+(a1 +b1 )X +(a0 +b0 )
W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique
 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Basics operations

Multiplication
Let P = an X n + an−1 X n−1 + · · · + a1 X + a0 and
Q = bm X m + bm−1 X m−1 + · · · + b1 X + b0 . We define

P × Q = cr X r + cr −1 X r −1 + · · · + c1 X + c0
X
with r = n + m and ck = ai bj pour k ∈ {0, . . . , r }.
i+j=k

Multiplication by scalar
If λ ∈ K then λ · P is the polynomial with the i-the coefficient is
λai .

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Basics operations-example

Basics operations-example
Consider the two polynomials P = aX 3 + bX 2 + cX + d and
Q = αX 2 + βX + γ.
P + Q = aX 3 + (b + α)X 2 + (c + β)X + (d + γ) ;
P × Q = (aα)X 5 + (aβ + bα)X 4 + (aγ + bβ + cα)X 3 +
(bγ + cβ + d α)X 2 + (cγ + d β)X + d γ.
P = Q if and only of a = 0, b = α, c = β and d = γ.
The multiplication by scalar λ · P is equivalent to multiply the
constant polynomial λ by the polynomial P.

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Basics Operations

Proposition
If P, Q, R ∈ K[X ] then
0 + P = P, P + Q = Q + P, (P + Q) + R = P + (Q + R) ;
1 · P = P, P × Q = Q × P, (P × Q) × R = P × (Q × R) ;
P × (Q + R) = P × Q + P × R.
deg (P × Q) = degP + degQ
deg (P + Q) 6 max(degP, degQ)

We note Rn [X ] = P ∈ R[X ] | deg P 6 n . If P, Q ∈ Rn [X ] then
P + Q ∈ Rn [X ].

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Basics Operations

Division
Let A, B ∈ K[X ], we say that B divides A if there exist Q ∈ K[X ]
such that A = BQ. We note B|A.

Others evident properties as A|A, 1|A and A|0 we have : for

A, B, C ∈ K[X ].
1 if A|B et B|A, then there exists λ ∈ K∗ such that A = λB.
2 If A|B and B|C then A|C .
3 If C |A and C |B then C |(AU + BV ), for all U, V ∈ K[X ].

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Basics Operations

Euclidean Division theorem

Let A, B ∈ K[X ], where B 6= 0, there exists a unique polynomial Q
and a unique polynomial R such that :

A = BQ + R and deg R < deg B

• Q is the quotient and R is the remainder of the euclidean

division of A by B.
• The condition deg R < deg B means that R = 0 or
0 6 deg R < deg B.
• R = 0 if and only if B|A.

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Euclidean Division example

A(X ) = X 3 +X 2 −1, B(X ) = X −1, Q(X ) = X 2 +2X +2, R(X ) = 1

x 3 +x 2 −1 x −1
3
−x +x 2 x 2 +2x +2
2x 2
−2x 2 +2x
2x
−2x +2
+1

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Euclidean Division example

A(X ) = X n − 1, B(X ) = X − 1, Q(X ) =

X n−1 + X n−2 + · · · + 1, R(X ) = 0

xn −1 x −1
−x n +x n−1 x n−1 +x n−2 ··· + 1
x n−1 −1
−x n−1 +x n−2
x n−2 −1
..
.
x −1
−x + 1
0
W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique
 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

GCD

Greatest common divisor

Let A, B ∈ K[X ], where A 6= 0 or B 6= 0. There exists a unique unit
polynomial of greatest degree which divides both A and B. This
unique polynomial is called the GCD (greatest common divisor) of
A and B which we note gcd (A, B).

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Euclide’s algorithm
Euclide’s algorithm
Let A and B two polynomials, B 6= 0. We calculate the successive
Euclidean divisions.
A = BQ1 + R1 deg R1 < deg B
B = R1 Q2 + R2 deg R2 < deg R1
R1 = R2 Q3 + R3 deg R3 < deg R2
..
.
Rk−2 = Rk−1 Qk + Rk deg Rk < deg Rk−1
Rk−1 = Rk Qk+1

The degree of the remainder decreases with each division. We stop

the algorithm when the remainder is zero. The gcd is the last
non-zero remainder Rk (unitary rendering).
W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique
 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Example

Euclide’s algorithm application

The gcd of A = X 5 + X 4 + 2X 3 + X 2 + X + 2 and
B = X 4 + 2X 3 + X 2 − 4.
X 5 + X 4 + 2X 3 + X 2 + X + 2 =
(X 4 + 2X 3 + X 2 − 4) × (X − 1) + 3X 3 + 2X 2 + 5X − 2
X 4 +2X 3 +X 2 −4 = (3X 3 +2X 2 +5X −2)× 19 (3X +4)− 14 2
9 (X +X +2)
3X 3 + 2X 2 + 5X − 2 = (X 2 + X + 2) × (3X − 1) + 0
Thus gcd (A, B) = X 2 + X + 2.

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Prim polynomials
Prim polynomials
Let A, B ∈ K[X ]. A and B are prim if gcd (A, B) = 1.

Bezout’s theorem
Let A, B ∈ K[X ] two polynomials with A 6= 0 or B 6= 0. We note
D = gcd(A, B). There exist U, V ∈ K[X ] such that AU + BV = D.

corollary
Let A, B ∈ K[X ] two polynomials. A and B are prim if and only if
there exist two polynomials U and V such that AU + BV = 1.

corollary
Let A, B, C ∈ K[X ] with A 6= 0 or B 6= 0. Si C |A et C |B then
C | gcd(A, B).
W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique
 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Example

Euclide’s algorithm application

The gcd of A = X 4 − 1 and B = X 3 − 1.
X 4 − 1 = (X 3 − 1) × X + (X − 1)
X 3 − 1 = (X − 1) × (X 2 + X + 1) + 0
Thus gcd (A, B) = X − 1.
In addition, we have :
X − 1 = (X 4 − 1).1 + (X 3 − 1).(−X ).
Therefore, we put : U = 1 and V = −X , we have
gcd (A, B) = AU + BV .

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Roots and factorization

Roots
Let P ∈ K[X ] and α ∈ K. We say that α is a root (or a zero) of P
if P(α) = 0. P(α) = 0 ⇐⇒ (X − α) divides P

Proof
There exist 2 polynomials Q and R ∈ K[X ] such that

P = Q.(X − α) + R where deg R < 1

Thus, R is a constant. Evaluating the following expression in α, we

find P(α) = R(α). In the other hand, α is a root of
P ⇐⇒ P(α) = 0 ⇐⇒ R = 0 ⇐⇒ (X − α) divides P

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Examples
• Roots of P(x) = x 4 + 2x 3 + x 2 − 2x − 2 in C4 [X ] ?
• Roots of P(x) = x 3 + x 2 + x + 1 in Z3 [X ] ?

The remainder example

Find the remainder when P(x) = x 4 − 2x 2 + x + 5 is divided by
x + 3.

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Roots and factorization

Multiple roots
Let k ∈ N∗ . α is a root of multiplicity k of P if (X − α)k divides P
and (X − α)k+1 does not divide P. We say that α is a root of order
k.

These statements are equivalent :

(i) α is a root of multiplicity k of P.
(ii) There exist Q ∈ K[X ] such that P = (X − α)k Q, with
Q(α) 6= 0.
(iii) P(α) = P 0 (α) = · · · = P (k−1) (α) = 0 and P (k) (α) 6= 0.

• Multiplicity of roots of P(X ) = X 5 − 2X 4 + 2X 3 − 3X 2 + 3X − 1 ?

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Roots and factorization

D’Alembert-Gauss’s theorem
Any polynomial with complex coefficients of degree n > 1 has at
least one root in C. It has exactly n roots if we count each root
with multiplicity.

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Reducible and irreducible polynomials

Reducible polynomials
Let P ∈ K[X ] a polynomial of degree > 1, we say that P is
irreducible if for all Q ∈ K[X ] dividing P,then either Q ∈ K∗ , or
there exists λ ∈ K∗ such that Q = λP.

An irreducible polynomial P is therefore a non-constant

polynomial whose only divisors of P are the constants or P
itself (except for one multiplicative constant).
The notion of an irreducible polynomial for the arithmetic of
K[X ] corresponds to the notion of prime number for Z
arithmetic.
Otherwise, P is said to be reducible ; then there exists
polynomials A, B of K[X ] such that P = AB, with deg A > 1
and deg B > 1.
W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique
 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Reducible and irreducible polynomials

Reducible and irreducible polynomials

All polynomials of degree 1 are irreducible. Therefore there are
infinitely many irreducible polynomials.
X 2 − 1 = (X − 1)(X + 1) ∈ R[X ] is reducible.
X 2 + 1 = (X − i)(X + i) is reducible on C[X ] but irreducible
on R[X ].
√ √
X 2 − 2 = (X − 2)(X + 2) is reducible on R[X ] but
irreducible on Q[X ].

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Factorization of polynomials

Factorization’s theorem
Any non-constant polynomial A ∈ K[X ] can be written as a
product of unitary irreducible polynomials :

A = λP1k1 P2k2 · · · Prkr

where λ ∈ K∗ , r ∈ N∗ , ki ∈ N∗ and Pi are distinct irreducible

polynomials. Moreover, this decomposition is unique to the nearest
order of factors.

X 6 −1 = (X 3 +1)(X 3 −1) = (X +1)(X 2 −X +1)(X −1)(X 2 +X +1)

X6 − 1 = √ √ √ √
(X + 1)(X − 1)(X − 1−i2 3 )(X − 1+i2 3 )(X + 1+i2 3 )(X + 1−i2 3 )

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique

 Definitions, notations
Basics operations
Polynomials
Roots and factorization
Roots and factorization

Factorization of polynomials

Factorization of polynomials examples

P(X ) = 2X 4 (X − 1)3 (X 2 + 1)2 (X 2 + X + 1) is already
decomposed into irreducible factors in R[X ]. The
decomposition in C[X ] is √ √
P(X ) = 2X 4 (X − 1)3 (X − i)2 (X + i)2 (X + 1+i2 3 )(X + 1−i2 3 )

W. DJELLADJ Chapter IV: The ring of polynomials HIS - L1 Informatique