Algebraic Numbers

Antonio Caminha M. Neto

December 13, 2017

Estas notas são um extrato dos capı́tulos 19 e 20 de [2].

1 Algebraic numbers over Q

A complex number α is said to be algebraic over Q if there exists a polynomial
f ∈ Q[X] \ {0} such that f (α) = 0. A complex number which is not algebraic
over Q is said to be transcendental over Q. In this section and the next one
we stick to the case of algebraic numbers.
Obviously, every rational number r, being a root of the polynomial X − r ∈
Q[X] \ {0}, is algebraic over Q. In turn, the coming example collects less trivial
instances of algebraic numbers over Q.
√
Example 1.1. Let r ∈ Q∗+ and n ∈ N. If ω is an n−th root of unity, then n rω
is algebraic over Q, for such a number is a root of the nonzero polynomial with
rational coefficients X n − r.
Example 1.2. If α 6= 0 is algebraic, then so are α−1 and α2 .
If a complex number α is algebraic, the set

Aα = {f ∈ Q[X] \ {0}; f (α) = 0}

is nonempty by definition. Then, it is also nonempty the set of nonnegative

integers {∂f ; f ∈ Aα }, so that there exists pα ∈ Aα , monic and of minimum
degree. We thus have the following
Definition 1.3. Given a complex number α algebraic over Q, a polynomial
pα ∈ Q[X] \ {0}, monic, of minimum degree and having α as a root is called a
minimal polynomial for α.
The coming proposition and its corollaries collect the most important prop-
erties of minimal polynomials of algebraic numbers.
Proposition 1.4. If α ∈ C is algebraic over Q and pα is the minimal polynomial
of α, then:
(a) pα is irreducible over Q.
Antonio Caminha M. Neto - Semana Olı́mpica 2018 2

(b) If f ∈ Q[X] is such that f (α) = 0, then pα | f in Q[X].

In particular, pα is uniquely determined by α.
Proof.
(a) If we had pα = f g, with f and g being nonconstant and of rational coeffi-
cients, then the degrees of f and g would be less than that of pα and at least one
of them would have α as a root. In turn, this would contradict the minimality
of the degree of pα . Therefore, pα is irreducible over Q.

(b) By the division algorithm, there exist polynomials q, r ∈ Q[X] such that

f (X) = pα (X)q(X) + r(X),

with r = 0 or 0 ≤ ∂r < ∂pα . If r 6= 0, then

r(α) = f (α) − pα (α)q(α) = 0,

with ∂r < ∂pα , and this would again be a contradiction to the minimality of
the degree of pα . Thus, r = 0 and, hence, pα | f in Q[X].
Finally, if pα and qα were minimal polynomials for α, then item (b) would
give pα | qα in Q[X]. However, since pα and qα are both monic and of the same
degree, it would come that pα = qα .
Thanks to the former proposition, given α ∈ C algebraic, we can refer to pα
as being the minimal polynomial of α.
Corollary 1.5. If α ∈ C is algebraic and f ∈ Q[X] \ {0} is a monic, irreducible
polynomial such that f (α) = 0, then f = pα .
Proof. By the previous result, pα divides f in Q[X]. However, since f is
irreducible, there must exist a nonzero rational number c such that f = cpα .
Finally, since f and pα are both monic, we must have c = 1.
Corollary 1.6. If f ∈ Q[X] \ Q is irreducible, then f has no multiple roots.
Proof. We can assume, without any loss of generality, that f is monic. If some
α ∈ C is a multiple root of f , then α is also a root of the derivative f ′ of f .
However, since f ∈ Q[X] \ {0} is monic and irreducible, Corollary 1.5 assures
that it is the minimal polynomial of α. Therefore, Proposition 1.4 gives f | f ′
in Q[X], which is a contradiction to the inequality ∂f > ∂f ′ .
Example 1.7 (IMO shortlist). Let f be a nonconstant polynomial of rational
coefficients and α a real number such that α3 −3α = f (α)3 −3f (α) = −1. Prove
that, for every positive integer n, one has

f (n) (α)3 − 3f (n) (α) = −1,

where f (n) stands for the composite of f with itself, n times.

Antonio Caminha M. Neto - Semana Olı́mpica 2018 3

In the next example we shall use the fact (to be proved later) that if p is
prime and ω = cis 2π
p , then the minimal polynomial of ω is

pω (X) = X p−1 + X p−2 + · · · + X + 1.

Example 1.8 (IMO). Let p be an odd prime. Compute how many are the
p−element subsets of the set {1, 2, . . . , 2p} such that the sum of its elements is
divisible by p.
Example 1.9 (Romania). Let f ∈ Z[X] be a monic polynomial, of odd degree
greater than 1 and irreducible over Q. Suppose also that:
(a) f (0) is square-free.
(b) The complex roots of f have modulus greater than or equal to 1.
Prove that the polynomial F ∈ Z[X], given by F (X) = f (X 3 ), is also irreducible
over Q.

Problems – Section 1
1. Given k, n ∈ N, prove that cos 2kπ 2kπ
n and sin n are algebraic.

2. Let α ∈ C be algebraic. If there exists f ∈ Z[X] \ Z monic and such that

f (α) = 0, prove that pα ∈ Z[X].
3. (Brazil) Prove that the polynomial f (X)
√ = X 5 − X 4 − 4X 3 + 4X 2 + 2
does not admit any roots of the form r, with r ∈ Q and n ∈ N, n > 1.
n

4. Let α ∈ C be algebraic, with ∂pα = n, and define

Q(α) = {a0 + a1 α + · · · + an−1 αn−1 ; a0 , a1 , . . . , an−1 ∈ Q}
= {f (α); f ∈ Q[X], with f = 0 or ∂f ≤ n − 1}.
The purpose of this problem is to show that Q(α) is a subfield of C. To
this end, do the following items:
(a) Show that Q(α) is closed for addition, subtraction and multiplication.
(b) Given β ∈ Q(α), show that there exists a single f ∈ Q[X] such that
β = f (α), with f = 0 or ∂f ≤ n − 1.
(c) For β = f (α) ∈ Q(α) \ {0}, with f ∈ Q[X] such that ∂f ≤ n − 1,
show that gcd(f, pα ) = 1. Then, conclude that β1 ∈ Q(α).
√ √
5. Given a, b, c ∈ Q such that a + b 3 2 + c 3 4 6= 0, show that there exist
x, y, z ∈ Q for which
1 √
3
√
3
√3
√
3
= x + y 2 + z 4.
a+b 2+c 4
Then, find x, y and z if a = b = 1, c = 2.
Antonio Caminha M. Neto - Semana Olı́mpica 2018 4

6. Let α ∈ C be algebraic, with ∂pα = n, and Q(α) be as in problem 4.

Find all functions φ : Q(α) → C satisfying the following conditions, for all
u, v ∈ Q(α):
(i) φ(u + v) = φ(u) + φ(v).
(ii) φ(uv) = φ(u)φ(v).
7. If r is a nonzero rational and α ∈ C \ {0} is algebraic, prove that rα is
also algebraic.
8. If α, β ∈ C \ {0} are algebraic, prove that so are α + β, αβ and α/β.
√ √ √
9. Let a1 , a2 , . . . , an be natural numbers, and α = a1 + a2 + · · · + an .
If α ∈/ Z, prove that it is irrational.

2 Polynomials over Zp
It is a well known fact that for a prime p ∈ Z, the set Zp of congruence classes
modulo p can be furnished with operations of addition, subtraction, multiplica-
tion and division quite similar to those of C. In turn, thanks to such a resem-
blance, essentially all of the concepts and results on polynomials studied so far
remain true within the set Zp [X] of polynomials with coefficients in Zp . Our
purpose here is to make explicit comments on some similarities and differences
between polynomials over Zp and over K, with K = Q, R or C.
Given f (X) = an X n + · · · + a1 X + a0 ∈ Z[X], we define Zp [X] to be the set
of formal expressions f of the form

f (X) = an X n + · · · + a1 X + a0 , (1)

where a0 , a1 , . . . , an respectively denote the congruence classes of a0 , a1 , . . . , an

modulo p. As before, such an f is called a polynomial over Zp .
The correspondence f 7→ f defines a map

πp : Z[X] −→ Zp [X]
f 7−→ f

which is obviously surjective and is called the canonical projection of Z[X]

onto Zp [X]. For f, g ∈ Z[X], it is immediate to verify that

f (X) = g(X) in Zp [X]

m
∃h ∈ Z[X]; f (X) = g(X) + ph(X) in Z[X].

Equivalently, letting
p Z[X] = {ph; h ∈ Z[X]},
we have
f = 0 ⇔ f ∈ pZ[X].
Antonio Caminha M. Neto - Semana Olı́mpica 2018 5

We extend the operations of addition and multiplication in Zp to homony-

mous operations +, · : Zp [X] × Zp [X] → Zp [X] by setting, for f, g ∈ Z[X],

f + g = f + g and f · g = f g.

As in Z[X], we say that a polynomial f ∈ Zp [X] \ {0} as in (1) has degree

n if an 6= 0, i.e., if p ∤ an . More generally, if f ∈ Z[X] \ pZ[X], then f 6= 0 and
∂f ≤ ∂f .
k

Example 2.1. If p ∈ Z is a prime number and k ∈ N, prove that pj is a
multiple of p, for every integer 1 ≤ j < pk .
Example 2.2 (Romania). Prove that the number of odd binomial coefficients
in the n−th line of Pascal’s triangle is a power of 2.
In order to define the polynomial function associated to a polynomial f ∈
Zp [X], we have to take some care. Firstly, note that if f ∈ Z[X] and a, b ∈ Z
satisfy a ≡ b (mod p), then

f (a) ≡ f (b) (mod p);

on the other hand, if f = g in Zp [X], we saw above that there exists h ∈ Z[X]
such that f (X) = g(X) + ph(X). Hence, for a ∈ Z we have

f (a) = g(a) + ph(a) ≡ g(a) (mod p).

Given f ∈ Zp [X], the above comments allow us to define the polynomial

function associated to f˜ : Zp → Zp by setting, for a ∈ Z,

f˜(a) = g(a), (2)

where g ∈ Z[X] is any polynomial for which f = g. Obviously, the image of f˜

is a finite set, for Zp itself is finite. From now on, whenever there is no danger
of confusion, we shall write (2) simply as

f (a) = f (a).

The coming example shows that, contrary to what happens with polynomials
over Q, R or C, the polynomial function associated to a nonzero polynomial
over Zp [X] can vanish identically. In other words, it is no longer valid that two
distinct polynomials over Zp have distinct polynomial functions.
Example 2.3. The polynomial f (X) = X p − X ∈ Zp [X] is clearly a nonzero
element of Zp [X]. On the other hand, letting f : Zp → Zp denote its associated
polynomial function, Fermat’s little theorem gives

f (a) = ap − a = ap − a = 0

for every a ∈ Zp . Thus, f vanishes identically.

Antonio Caminha M. Neto - Semana Olı́mpica 2018 6

Let f ∈ Z[X] and a ∈ Z be given. We say that a ∈ Zp is a root of f provided

f (a) = 0. An easy review of the proof of the root test shows that it continues
to hold in Zp [X]. In particular, from the above example we obtain the following
important result.
Proposition 2.4. In Zp [X], we have

X p−1 − 1 = (X − 1)(X − 2) . . . (X − (p − 1)).

Proof. Since 1, 2, . . . , p − 1 are roots of X p−1 −1 in Zp (from the last example),

we conclude that the polynomial X p−1 − 1 is divisible by (X − 1)(X − 2) . . . (X −
(p − 1)) in Zp [X]. However, since both such polynomials are monic and have
degree p − 1, they are actually equal.
In Zp [X] the following theorem is valid.

Teorema 2.5. If p ∈ Z is prime, then every polynomial f ∈ Zp [X] \ Zp can

be written as a product of a finite number of irreducible polynomials over Zp .
Moreover, such a decomposition of f is unique up to association and reordering
of the irreducible factors.
Example 2.6. If p ∈ Z is an odd prime and d is a positive divisor of p − 1,
then the algebraic congruence

xp−1 − 1 ≡ 0 (mod p) (3)

has exactly ϕ(d) roots of order d, pairwise incongruent modulo p. In particular,

p has exactly ϕ(p − 1) primitive roots pairwise incongruent modulo p.
Example 2.7 (Miklós-Schweitzer). If p > 3 is a prime number satisfying p ≡
3 (mod 4), prove that
Y
(x2 + y 2 ) ≡ 1 (mod p).
1≤x6=y≤ p−1
2

Problems – Section 2

1. Let p > 2 be a given prime. Find, if any, the roots of X p−1 + 1 ∈ Zp [X].
2. Given f ∈ Z[X] and an integer root a of f , prove that a ∈ Zp is a root of
f ∈ Zp [X]. In particular, conclude that if a1 , . . . , ak ∈ Zp are the roots of
f , then there exists 1 ≤ j ≤ k such that a ≡ aj (mod p).
3. Show that f (X) = X 3 − 15X 2 + 10X − 84 ∈ Z[X] has no rational roots.
4. If p ∈ Z is prime and f ∈ Z[X], prove that f (X p ) = f (X)p .
Antonio Caminha M. Neto - Semana Olı́mpica 2018 7

5. A polynomial f ∈ Z[X] \ {0} is primitive if the gcd of its nonzero coeffi-

cients is equal to 1. Prove that if f, g ∈ Z[X]\Z are primitive polynomials,
then so is f g.
6. Let p > 2 be a prime number and 1 ≤ d ≤ p − 1 be an integer.
(a) If d ∤ (p − 1), show that X d − 1 has no roots in Zp [X].
(b) If d | (p − 1), factorise X d − 1 in Zp [X].
7. Let p ≥ 3 be a prime number and, for 1 ≤ j ≤ p − 1, let sj (1, 2, . . . , p −
1) denote the j−th elementary symmetric sum of the natural numbers
1, 2, . . . , p − 1. Prove that:
(a) For 1 ≤ j ≤ p − 2, we have sj (1, 2, . . . , p − 1) ≡ 0 (mod p).
(b) sp−1 (1, 2, . . . , p − 1) ≡ −1 (mod p).
8. If a, b and c are the complex roots of the polynomial X 3 − 3X 2 + 1, show
that an + bn + cn ∈ Z for every n ∈ N, and that such a sum is always
congruent to 1 modulo 17.
9. (France) For a given n ∈ N, let In denote the number of odd coefficients
of the polynomial (X 2 + X + 1)n .
(a) Compute I2m , for m ∈ Z+ .
(b) Show that, for m ∈ N, we have
2m+1 + (−1)m+1
I2m −1 = .
3
10. Prove Lucas’ theorem: given natural numbers m ≥ n and a prime
number p, if
Xk Xk
m= mj pj and nj pj
j=0 j=0

are the representations of m and n in base p, then

  Y k  
m mj
≡ (mod p).
n j=0
nj

In particular, conclude that:

(a) p | mn if and only if mj < nj for some 0 ≤ j ≤ k.
(b) Exactly

(m0 + 1)(m1 + 1) . . . (mk + 1) binomial numbers of the form
m
n are not divisible by p.
k+1

(c) No binomial number of the form p n −1 is divisible by p.
11. Let p be a prime number and k ∈ N. Prove that
 k  
p (p − 1) (−1)q (mod p), if l = pk q; 0 ≤ q ≤ p − 1, q ∈ Z
≡ .
l 0 (mod p), otherwise.
Antonio Caminha M. Neto - Semana Olı́mpica 2018 8

3 Cyclotomic polynomials
The theory of polynomials over Zp , p prime, allows us to present some of the
most elementary properties of the so-called cyclotomic polynomials; in particu-
lar, we will show that such polynomials are precisely the minimal polynomials
of the complex roots of unity. As a byproduct of our study, we will use cyclo-
tomic polynomials to prove a particular case of Dirichlet’s theorem on primes
in arithmetic progressions.
Given n ∈ N, recall that the primitive n−th roots of unity are the complex
numbers of the form ωnk , with ωn = cis 2π
n and 1 ≤ k ≤ n being relatively prime
with n. In particular, there are exactly ϕ(n) primitive n−th roots of unity,
where ϕ : N → N stands for the Euler function. Given m, n ∈ N, whenever
there is no danger of confusion we shall write simply (m, n) to denote the gcd
of m and n.
Definition 3.1. For n ∈ N, the n−th cyclotomic polynomial is the polyno-
mial Y
Φn (X) = (X − ωnk ). (4)
1≤k≤n
(k,n)=1

It follows from the above definition that Φn is monic with degree ∂Φn =
ϕ(n). The coming proposition collects other elementary properties of Φn .
Proposition 3.2. For n ∈ N, we have:
Q
(a) X n − 1 = 0<d|n Φd (X).

(b) Φn ∈ Z[X].
(c) Φn (0) = 1 for n > 1.
Proof.
(a) First of all, we have
Y Y Y Y
k
Φd (X) = Φn/d (X) = (X − ωn/d )
0<d|n 0<d|n 0<d|n 1≤k≤n/d
(k,n/d)=1
Y Y
= (X − ωndk ).
0<d|n 1≤k≤n/d
(k,n/d)=1

Now, note that each integer 1 ≤ m ≤ n can
be uniquely written as m = dk,

with d, k ∈ N such that 0 < d | n and k, nd = 1 (d is exactly d = gcd(m, n)).
Therefore, the last sum above is clearly equal to
n
Y
(X − ωnj ) = X n − 1.
j=1
Antonio Caminha M. Neto - Semana Olı́mpica 2018 9

(b) Let us make induction on n ∈ N, beginning with Φ1 (X) = X − 1 ∈ Z[X].

Given a natural number n > 1, assume, by induction hypothesis, that Φm ∈
Z[X] for every integer 1 ≤ m < n. Then, if
Y
g(X) = Φd (X),
1≤d<n
d|n

we have g ∈ Z[X] and, by (a), X n − 1 = Φn (X)g(X). Since g is monic (for we

already know that each Φm is monic), the division algorithm guarantees that
Φn ∈ Z[X].

(c) For n = 2 this is a direct computation. For n > 2, arguing once more by
induction, start by noticing that

X 2 − 1 = Φ1 (X)Φ2 (X) = (X − 1)Φ2 (X);

hence, Φ2 (X) = X + 1 and Φ2 (0) = 1. Let n > 1 and suppose, as induction

hypothesis, that Φm (0) = 1 for every integer 2 ≤ m < n. Then, in the notations
of the proof of (b), we have
Y Y
g(0) = Φ1 (0) Φd (0) = (−1) Φd (0) = −1,
1<d<n 1<d<n
d|n d|n

and it follows from X n − 1 = Φn (X)g(X) that

−1 = Φn (0)g(0) = −Φn (0),

as wished.
Corollary 3.3. If p ∈ Z is prime, then

Φp (X) = X p−1 + X p−2 + · · · + X + 1.

Proof. Item (a) of the previous proposition gives

X p − 1 = Φ1 (X)Φp (X) = (X − 1)Φp (X),

so that
Φp (X) = X p−1 + X p−2 + · · · + X + 1.

We now need to establish a simple auxiliary result.

Lemma 3.4. Let f, g ∈ Z[X] and p ∈ Z be a prime number. If g ∈ Zp [X] \ Zp
and g 2 | f in Zp [X], then g | f ′ in Zp [X].
Antonio Caminha M. Neto - Semana Olı́mpica 2018 10

Proof. If h ∈ Z[X] is such that f = g 2 h in Zp [X], we know that there exists a

polynomial l ∈ Z[X] such that

f (X) = g(X)2 h(X) + pl(X)

in Z[X]. Computing derivatives at both sides of this equality, we obtain

f ′ (X) = 2g(X)g ′ (X)h(X) + g(X)2 h′ (X) + pl′ (X)

in Z[X], and hence

f ′ (X) = g(X) 2 g ′ (X)h(X) + g(X)h′ (X)

in Zp [X]. Therefore, g | f ′ in Zp [X].

For our next result, recall that if ω is an n−th root of unity, then Proposition
1.4 guarantees that its minimal polynomial pω divides X n − 1 in Q[X]. Then,
problem 2, page 3, assures that pω ∈ Z[X].
Proposition 3.5. Let n, p ∈ N be such that p is prime and p ∤ n. If ω is an
n−th root of unity, then pω (X) = pωp (X).
Proof. Let ζ = ω p . Since both ω and ζ are roots of X n − 1, item (b) of
Proposition 1.4 shows that both pω and pζ divide X n − 1. By contradiction,
assume that pω 6= pζ . Then, the irreducibility of these polynomials assures, via
Gauss’ theorem, that pω pζ divides X n − 1 in Z[X], say

X n − 1 = pω (X)pζ (X)u(X) (5)

for some u ∈ Z[X].

If g(X) = pζ (X p ), then

g(w) = pζ (ω p ) = pζ (ζ) = 0

so that (once more by Proposition 1.4) pω divides g in Z[X]. Let v ∈ Z[X] be

such that pω v = g. In Zp [X], problem 4, page 6 gives

p
pω (X)v(X) = g(X) = pζ (X p ) = pζ (X) ,

and Theorem 2.5 guarantees the existence of a monic and irreducible polynomial
h ∈ Zp [X] such that h | pω , pζ in Zp [X]. It follows from (5) that h(X)2 | (X n −1)
in Zp [X], and the previous lemma gives that h(X) | nX n−1 in Zp [X]. However,
since h is monic and n 6= 0, by applying once again Theorem 2.5 we obtain
1 ≤ l ≤ n − 1 such that h(X) = X l in Zp [X]. Hence, h(X) ∤ (X n − 1) in Zp [X],
which is a contradiction.
We can finally state and prove the desired result.
Teorema 3.6. If ωn = cis 2π
n , then pωn = Φn . In particular, Φn ∈ Z[X] is
irreducible in Q[X].
Antonio Caminha M. Neto - Semana Olı́mpica 2018 11

Proof. Take k ∈ N such that k > 1 and gcd(k, n) = 1, and let k = p1 . . . pl , with
p1 , . . . , pl being primes not dividing n. Repeated applications of the previous
proposition give us

pωn = pωnp1 = pωnp1 p2 = · · · = pωnp1 ...pl = pωnk .

In particular, the ϕ(n) complex numbers ωnk , with 1 ≤ k ≤ n and gcd(k, n) = 1,

are distinct roots of pωn , so that

∂pωn ≥ ϕ(n) = ∂Φn .

However, since Φn is monic, has integer (thus rational) coefficients and ωn as a

root, the definition of minimal polynomial assures that pωn = Φn .
Example 3.7 (Dirichlet). If n ∈ N, then the arithmetic progression 1, 1 + n, 1 +
2n, . . . contains infinitely many primes.
Example 3.8. For each prime number p, let g(p) ∈ N denote the least positive
prime root modulo p. Then, the function p 7→ g(p) is unbounded.

Problems – Section 3

1. Let p, k ∈ N be given, with p being prime. Compute Φpk explicitly.

2. If m and n are distinct naturals, prove that Φm and Φn have no noncon-
stant common factors in C[X]. In particular, Φm 6= Φn .
3. Let n > 1 be a natural number and d be the
product of the distinct prime
factors of n. Show that Φn (X) = Φd X n/d .

4. (England) The set 1, 21 , 13 , 14 , . . . contains several arithmetic progres-
sions. Given an integer k > 2, prove that it contains an arithmetic pro-
gression of k terms which is not contained in any arithmetic progression
of k + 1 terms of the same set.
5. Let a, n ∈ N, with a > 1 and n odd. Prove that the algebraic congruence
xn ≡ a (mod p) has a solution for infinitely many primes p.

6. Let a be a natural number which is not a perfect square. Prove that there
are infinitely many prime numbers p for which a is a non-quadratic residue
modulo p.
7. Let a, b ∈ Z be such that for each n ∈ N there exists c ∈ Z for which
n | (c2 + ac + b). Prove that the equation x2 + ax + b = 0 has integer roots.
Antonio Caminha M. Neto - Semana Olı́mpica 2018 12

4 Algebraic numbers over Zp

This section is somewhat more abstract that the previous ones, for we extend
the concept of algebraic number to consider algebraic numbers over Zp , for some
prime number p. However, the payoff will be worth the effort, for, given n ∈ N,
we will be able to compute the exact number of irreducible polynomials over Zp
and having degree n.
We depart from a naive though profitable idea, namely, that there exists a
number set Ωp containing Zp that plays, for Zp , the same role as C plays for Q.
We start by formalizing the concept of field.
Definition 4.1. A field is a nonempty set K, furnished with operations +, · :
K × K → K having the following properties:
(a) + and · are commutative and associative, and · is distributive with respect
to +.
(b) There exist elements 0, 1 ∈ K, with 0 6= 1, such that a + 0 = a and a · 1 = a,
for every a ∈ K.
(c) For every a ∈ K, there exists an element −a ∈ K such that a + (−a) = 0.
(d) For every a ∈ K \ {0}, there exists an element a−1 ∈ K such that a·a−1 = 1.
The reader has certainly realized what we mean by commutative, associative
and distributive from his/her previous experience. Nevertheless, let us explain
all that from first principles. Commutativity in item (a) means that

a + b = b + a and a · b = b · a,

whereas associativity stands for

(a + b) + c = a + (b + c) and (a · b) · c = a · (b · c),

for all a, b, c ∈ K. In turn, the distributivity of · with respect to + is exactly

what one expects:
a · (b + c) = a · b + a · c,
with the right hand side being a shorthand for the more precise (though some-
what cumbersome) expression (a · b) + (a · c).
Thus, we surely have that Q, R and C are fields, and problem 4, page 3
shows that so is Q(α), for every α ∈ C algebraic over C. Moreover, in all of
these cases, the elements 0 and 1 of item (b) in the above definition are the
usual complex numbers 0 and 1, and this is the reason why, for a general field
K, we also denote them by 0 and 1. A similar remark holds for −a and a−1 ,
i.e., we are simply adopting the same notation we use for the additive (resp.
multiplicative) inverses of elements of C (resp. of C \ {0}).
Another class of examples of fields we have been dealing with is that of the
finite fields Zp , with p ∈ Z prime. In this case, however, we shall stick to the
Antonio Caminha M. Neto - Semana Olı́mpica 2018 13

usage of writing 0 and 1 whenever convenient, in order to avoid any possibility

of confusion with 0, 1 ∈ Z.
Back to a general field K, the cancellation laws for addition and multiplica-
tion hold:

a + c = b + c ⇒ a = b and a · c = b · c, c 6= 0 ⇒ a = b.

Indeed,

a + c = b + c ⇒ (a + c) + (−c) = (b + c) + (−c)
⇒ a + (c + (−c)) = b + (c + (−c))
⇒ a + 0 = b + 0 ⇒ a = b,

and likewise for the multiplication.

As it happens within C, whenever there is no danger of confusion we shall
write ab instead of a · b, to denote the product of elements a and b of a general
field K.
We could have developed most of the theory of polynomials by considering
the set K[X] of polynomials over (or with coefficients in) an arbitrary field K,
with operations +, · : K[X] × K[X] → K[X] extending those of K. Taking for
granted the (harmless) assumption that we have done that, we now have at our
disposal the following concepts and facts, whose validities the reader can easily
check:
1. If f, g ∈ K[X] are such that f g = 0 (the identically zero polynomial), then
f = 0 or g = 0.
2. The notions of degree (for nonzero polynomials) and roots for polynomials
over K remain true, unchanged. Likewise, ∂(f g) = ∂f + ∂g if f, g 6= 0 and
∂(f + g) ≤ max{∂f, ∂g} if f + g 6= 0.
3. The division algorithm, the root test and Lagrange’s theorem on the num-
ber of distinct roots of a nonzero polynomial also continue to hold, with
identical proofs.
4. The concept of greatest common divisor for nonzero polynomials over K is
a direct extension from that for polynomials over Q, and Bézout’s theorem
is also true, with exactly the same proof.
5. Another concept that extends in a likewise manner from Q[X] is that of
irreducible polynomial f ∈ K[X]. We also have unique factorisation.
A major gap on extending the theory for polynomials over arbitrary fields
is fulfilled by the coming result, which will be assumed without proof (we refer
the interested reader to [1] or [3]).
Teorema 4.2. Given an arbitrary field K, there exists another field Ω contain-
ing K, whose operations extend those of K and such that every f ∈ K[X] has at
least one root in Ω.
Antonio Caminha M. Neto - Semana Olı́mpica 2018 14

The field Ω plays the role of C for K. We refer to the property of Theorem
4.2 by saying that Ω is an algebraically closed field containing K. Also as
with C, one now proves that if f ∈ K[X] \ {0} has degree n, then there exists
a ∈ K (the leading coefficient of f ) and α1 , . . . , αn ∈ Ω such that

f (X) = a(X − α1 )(X − α2 ) . . . (X − αn ).

The equality above is the factorised form of f over Ω.

We can now define, exactly as was done in Section 1, what one means for
an element α ∈ Ω to be algebraic over K, and consider its minimal polynomial
pα ∈ K[X] \ {0} as was done for α ∈ C algebraic over Q. This way, Proposition
1.4 and Corollary 1.5 remain true, unchanged.
We now restrict our attention to K = Zp , and write Ωp to denote the field Ω
of Theorem 4.2. We first recall the result of problem 4, page 6, which we write
in the following form:

f (X p ) = f (X)p , ∀ f ∈ Zp [X]. (6)

We shall also need the following auxiliary result.

Lemma 4.3. Let f ∈ Ωp [X] \ {0} be given. If α ∈ Ωp is a root of f , then:
(a) αp is also a root of f .
m
(b) There exists a natural number m ≤ ∂f such that α is a root of X p − X.
Proof.
p
(a) It follows from (6) that f (αp ) = f (α)p = 0 = 0.
2
(b) Iterating the result of (a), we conclude that α, αp , αp , . . . are roots of f .
Since it has at most ∂f distinct roots, we conclude that there exist integers
k l
0 ≤ k < l ≤ ∂f for which αp = αp . Therefore,
l k l−k
pk k l−k
pk
0 = αp − αp = αp − αp = αp −α ,

where we have used the result of Example 2.1 in the last equality above. It
l−k m
comes that αp − α = 0, and α is a root of X p − X, with m = l − k ≤ ∂f .
We are now in position to prove the following
Proposition 4.4. Let p be prime and α ∈ Ωp be algebraic over Zp . If ∂pα = n,
then:
n
(a) α is a root of X p − X.
m
(b) α is not a root of X p − X, for any positive integer m < n.
Antonio Caminha M. Neto - Semana Olı́mpica 2018 15

m
Proof. We already know, from the previous lemma, that α is a root of X p −X,
for any positive integer m ≤ n. Now, let

Φ : Zp × Zp × . . . × Zp −→ Ωp
| {z }
n times

be defined by

Φ(a0 , a1 , . . . , an−1 ) = a0 + a1 α + · · · + an−1 αn−1 .

m
We claim that Φ is injective and each β ∈ Im(Φ) is a root of X p − X.
Indeed, if
Φ(a0 , a1 , . . . , an−1 ) = Φ(b0 , b1 , . . . , bn−1 ),
for distinct n−tuples (a0 , a1 , . . . , an−1 ) and (b0 , b1 , . . . , bn−1 ) in the domain of
Φ, then
(a0 − b0 ) + (a1 − b1 )α + · · · + (an−1 − bn−1 )αn−1 = 0,
so that α would be a root of the nonzero polynomial (a0 − b0 ) + (a1 − b1 )X +
· · · + (an−1 − bn−1 )X n−1 of Zp [X]. Since ∂pα = n, this is a contradiction.
For the second part, let β = a0 + a1 α + · · · + an−1 αn−1 . The result of
m
Example 2.1 gives, together with Fermat’s little theorem and αp = α, gives
m
pm
βp = a0 + a1 α + · · · + an−1 αn−1
m m m m m
= ap0 + ap1 αp + · · · + apn−1 α(n−1)p
= a0 + a1 α + · · · + an−1 αn−1
=β
m
Let Rm stand for the set of roots of X p − X in Ωp . The above claims then
assure that |Rm | ≥ pn , so that pm ≥ pn and, hence, m ≥ n. Since m ≤ n, we
then get m = n, and items (a) and (b) follow at once.
A direct consequence of this proposition is the coming
Corollary 4.5. Let
p be prime and α ∈ Ωp be algebraic over Zp . If ∂pα = n,
n
then pα | X p − X in Zp [X].
Proof. This follows from the previous result, together with the analogue of
Proposition 1.4 in our setting.
Another consequence is collected as the next result.
n
Lemma 4.6. Let f ∈ Zp [X]\Zp be irreducible and of degree d. If f | (X p −X),
then d | n.
Proof. If α ∈ Ωp is a root of f , then f = pα , and the previous corollary
d k
guarantees that f | (X p − X) and f ∤ (X p − X), for every positive integer
n
k < d. Since f | (X p − X), we conclude that d ≤ n.
Antonio Caminha M. Neto - Semana Olı́mpica 2018 16

Now, let n = d + t and write

n d+t d
pt t t
Xp − X = Xp − X = Xp − Xp + Xp − X
d
pt t
= Xp −X + X p − X.

It readily follows from this equality that

n d
t d

gcd X p − X, X p − X = gcd X p − X, X p − X .

Assume that n = dq + r, with 0 < r < d. Iterating the gcd equality above,
we get
n d
r d

gcd X p − X, X p − X = gcd X p − X, X p − X . (7)
Since f divides the left hand side, it also divides the right hand side. In partic-
r
ular, f | (X p − X), which is a contradiction.
We can finally state and prove our main result, for which we let

an = #{monic, pairwise distinct irreducible polynomials of degree n in Zp [X]}.

Also, if an > 0, we write fn1 , fn2 , . . . , fnan to denote such polynomials.

Teorema 4.7. Let p be prime and n ∈ N. Then,
n Y
Xp − X = fd1 (X) . . . fdad (X), (8)
0<d|n

with the product fd1 . . . fdad taken as 1 if ad = 0.

n
Proof. Unique factorisation assures that X p − X is the product of finitely
many irreducible polynomials, which can all be assumed to be monic.
If f is one such polynomial, with ∂f = d, the previous lemma shows that
d | n, so that f is one of the polynomials in the right hand side of (8). Conversely,
if 0 < d | n, 1 ≤ j ≤ ad and α ∈ Ωp is a root of fdj , then fdj = pα , and
d

Corollary 4.5 guarantees that fdj | X p − X in Zp [X]. However, since d | n,
the argument in the proof of the previous lemma leading to (7) shows that
d
n
n

X p − X | X p − X in Zp [X]. Therefore, fdj | X p − X in Zp [X].
P

Example 4.8. If p is prime and n ∈ N, show that an = n1 0<d|n µ nd pd > 0.

Problems – Section 4
n
1. Let p be prime and n ∈ N. If 0 < d | n, then X p − X has an irreducible
factor of degree d.
Antonio Caminha M. Neto - Semana Olı́mpica 2018 17

n
2. Let p be prime and, for n ∈ N, let Rn denote the set of roots of X p − X
in Ωp . Show that Rn is a subfield of Ωp containing Zp .


3. In the notations of the statement of Theorem 4.7, show that a2 = p2 and

f21 (X) . . . f2a2 (X) = (X p − X)p−1 + 1.

4. Let K be any field. Prove that K[X] has infinitely many irreducible poly-
nomials.

References
[1] R. Ash. Basic Abstract Algebra: for Graduate Students and Advances Un-
dergraduates. Mineola, Dover, 2006.
[2] A. Caminha. An Excursion Through Elementary Mathematics III. Springer
Nature, Cham, 2018.
[3] C. R. Hadlock. Field Theory and its Classical Problems. Washington, MAA,
2000.