CommeUnJeu · L2 MP

Rings, arithmetic and algebras

⌚ ~115 min ▢ 14 blocks ✓ 24 exercises ➣ Prerequisites : Algebraic structures, Arithmetic in $\mathbb{Z}$, Arithmetic of polynomials, Further group theory

Why this chapter

In MPSI, rings and fields were built as structures, and the arithmetic of $\mathbb{Z}$ and of $\mathbb{K}[X]$ — divisibility, gcd, Bézout — was developed twice, once on each side. This chapter unifies the two around a single idea: the ideal, a subset of a ring that is absorbing under multiplication.
The same three statements are then proved once for $\mathbb{Z}$ and once for $\mathbb{K}[X]$: every ideal is principal (generated by one element), the gcd is exactly the generator of a sum of ideals, and Bézout's relation expresses that generator. The parallel between the two is the lesson — and it is why the chapter treats them in the same language.
The headline results lie in between: $\mathbb{Z}/n\mathbb{Z}$, seen in Further group theory only as an additive group, becomes a ring; it is a field exactly when $n$ is prime; the Chinese remainder theorem splits it into coprime pieces; and Euler's theorem generalises Fermat's little theorem. The chapter closes with algebras, the structures — like $\mathbb{K}[X]$ or $\mathcal{M}_n(\mathbb{K})$ — that are a vector space and a ring at once.

Conventions

The following conventions and recalled notation hold throughout.

Rings. In §§1--4, $A$ denotes a commutative ring; $0_A$, $1_A$ are its neutrals, $A^\times$ its group of units. Rings, sub-rings, ring morphisms (with $\varphi(1_A)=1_B$), kernels and integral rings are used as established in Algebraic structures. § 5 deliberately allows non-commutative rings.
Ideals. $xA$ denotes the principal ideal generated by $x$, also written $(x)$.
Arithmetic. Divisibility, gcd, lcm, Bézout and Gauss in $\mathbb{Z}$ and in $\mathbb{K}[X]$, and congruences modulo $n$, are used as established in Arithmetic in $\mathbb{Z}$ and Arithmetic of polynomials. A gcd is taken non-negative in $\mathbb{Z}$ and monic in $\mathbb{K}[X]$.
Settings. In § 3, $n$ is an integer $\ge 2$. In § 4, $\mathbb{K}$ is a subfield of $\mathbb{C}$.

I Complements on rings

I.1 Finite products of rings

The first construction handles several rings at once: on the cartesian product of finitely many rings, addition and multiplication done coordinate by coordinate again give a ring. This is the ambient ring in which the Chinese remainder theorem of § 3 will live.

Proposition — Product ring

Let $A_1, \dots, A_p$ be rings. The cartesian product $A_1 \times \dots \times A_p$, equipped with the coordinatewise laws $$ (x_1, \dots, x_p) + (y_1, \dots, y_p) = (x_1 + y_1, \dots, x_p + y_p), \qquad (x_1, \dots, x_p) \times (y_1, \dots, y_p) = (x_1 y_1, \dots, x_p y_p), $$ is a ring, with zero $(0_{A_1}, \dots, 0_{A_p})$ and unit $(1_{A_1}, \dots, 1_{A_p})$; it is commutative when each $A_i$ is. Its units are exactly the tuples of units: $(A_1 \times \dots \times A_p)^\times = A_1^\times \times \dots \times A_p^\times$.

Proof

Each ring axiom is an identity between tuples, and a tuple identity holds if and only if it holds in each coordinate; since every $A_i$ is a ring, every axiom holds coordinatewise, hence in the product. For the units: $(x_1, \dots, x_p)$ has inverse $(y_1, \dots, y_p)$ iff $x_i y_i = y_i x_i = 1_{A_i}$ for every $i$, i.e. iff each $x_i$ is a unit of $A_i$.

Example — The product $\mathbb{Z} \times \mathbb{Z}$

The ring $\mathbb{Z} \times \mathbb{Z}$ is commutative but not integral: $(1, 0)$ and $(0, 1)$ are both non-zero, yet $(1, 0) \times (0, 1) = (0, 0)$. A finite product of integral rings (with at least two non-zero factors) always has such zero divisors.

Example — Units of a product

In $\mathbb{Z} \times \mathbb{Z}$, since $\mathbb{Z}^\times = \{-1, 1\}$, the units are the four tuples $(\pm 1, \pm 1)$. The product of the two-element rings $(\mathbb{Z}/2\mathbb{Z})^2$ likewise has units $(\bar 1, \bar 1)$ only, as $\bar 1$ is the sole unit of $\mathbb{Z}/2\mathbb{Z}$.

Skills to practice

Computing in a product ring

I.2 Ideals of a commutative ring

We now meet the central object of the chapter. An ideal of a commutative ring is a subgroup that is moreover absorbing: multiplying any of its elements by any ring element keeps the result inside. The motivating example is the kernel of a ring morphism — and, as in $\mathbb{Z}$, ideals are exactly what is needed to talk about divisibility intrinsically.

Definition — Ideal

Let $A$ be a commutative ring. A subset $I \subseteq A$ is an ideal of $A$ when

$I$ is a subgroup of $(A, +)$;
$I$ is absorbing: for every $x \in I$ and every $a \in A$, $ax \in I$.

Example — The trivial ideals and $n\mathbb{Z}$

In any commutative ring $A$, both $\{0_A\}$ and $A$ itself are ideals. In $\mathbb{Z}$, for each $n \in \mathbb{N}$ the set $n\mathbb{Z}$ of multiples of $n$ is an ideal: it is a subgroup of $(\mathbb{Z}, +)$, and $a \cdot (nk) = n(ak) \in n\mathbb{Z}$ for every $a$.

Proposition — Kernel is an ideal

Let $\varphi : A \to B$ be a ring morphism whose source $A$ is commutative (the target $B$ arbitrary). Then $\operatorname{Ker}\varphi$ is an ideal of $A$.

Proof

Recall from Algebraic structures that $\varphi$ is in particular a group morphism $(A, +) \to (B, +)$, so $\operatorname{Ker}\varphi$ is a subgroup of $(A, +)$. It remains to check absorption. Let $x \in \operatorname{Ker}\varphi$ and $a \in A$. Then $$ \varphi(ax) = \varphi(a)\,\varphi(x) = \varphi(a)\,0_B = 0_B, $$ so $ax \in \operatorname{Ker}\varphi$. Hence $\operatorname{Ker}\varphi$ is an ideal of $A$.

Example — Kernel of an evaluation morphism

For $a \in \mathbb{K}$, the evaluation map $\operatorname{ev}_a : \mathbb{K}[X] \to \mathbb{K}$, $P \mapsto P(a)$, is a ring morphism with commutative source $\mathbb{K}[X]$. Its kernel $$ \operatorname{Ker}(\operatorname{ev}_a) = \{P \in \mathbb{K}[X] \mid P(a) = 0\} $$ is therefore an ideal of $\mathbb{K}[X]$ — the polynomials vanishing at $a$. Its principal generator $X - a$ is identified in §4.1.

Proposition — Stability of ideals

Let $I_1, \dots, I_p$ be ideals of a commutative ring $A$. Then:

the intersection $I_1 \cap \dots \cap I_p$ is an ideal of $A$;
the sum $I_1 + \dots + I_p = \{x_1 + \dots + x_p \mid x_k \in I_k\}$ is an ideal of $A$.

Proof

Intersection. An intersection of subgroups is a subgroup. If $x$ lies in every $I_k$ and $a \in A$, then $ax \in I_k$ for every $k$ (each $I_k$ absorbing), so $ax$ lies in the intersection. The intersection is an ideal.
Sum. It suffices to treat $p = 2$ and induct. $I_1 + I_2$ is a subgroup of $(A,+)$ (sum of two subgroups). For $a \in A$ and $x_1 + x_2$ with $x_k \in I_k$, $a(x_1 + x_2) = ax_1 + ax_2$ with $ax_k \in I_k$, so $a(x_1+x_2) \in I_1 + I_2$. The general case follows by induction on $p$.

Skills to practice

Identifying the ideals of a ring

I.3 Generated ideal and divisibility

Among all ideals, the simplest are those built from a single element. The set of its multiples is already an ideal — the smallest one containing that element. These principal ideals turn divisibility into a statement about inclusion: $a$ divides $b$ exactly when the ideal of $b$ sits inside the ideal of $a$.

Definition — Principal ideal

Let $A$ be a commutative ring and $x \in A$. The principal ideal generated by $x$ is $$ xA = \{xa \mid a \in A\}, $$ also written $(x)$.

Proposition — $xA$ is the smallest ideal containing $x$

For $x$ in a commutative ring $A$, the set $xA$ is an ideal of $A$, it contains $x$, and it is contained in every ideal of $A$ that contains $x$.

Proof

$xA$ is a subgroup: $0_A = x\,0_A \in xA$, and $xa - xb = x(a-b) \in xA$. It is absorbing: for $c \in A$, $c(xa) = x(ca) \in xA$. So $xA$ is an ideal, and $x = x\,1_A \in xA$. Finally, let $I$ be an ideal containing $x$; for every $a \in A$, $xa \in I$ since $I$ is absorbing, so $xA \subseteq I$.

Example — Two principal ideals

In $\mathbb{Z}$, the principal ideal $(n) = n\mathbb{Z}$ is the set of multiples of $n$. In $\mathbb{K}[X]$, the principal ideal $(X - a) = (X - a)\,\mathbb{K}[X]$ is the set of polynomial multiples of $X - a$ — exactly the polynomials vanishing at $a$, the kernel met in §1.2.

Definition — Divisibility in an integral ring

Let $A$ be an integral commutative ring and $a, b \in A$. We say $a$ divides $b$, written $a \mid b$, when $b = ac$ for some $c \in A$. Two elements $a, b$ are associates, written $a \sim b$, when $a = ub$ for some unit $u \in A^\times$.

Example — Associates in two familiar rings

In $\mathbb{Z}$ the units are $\mathbb{Z}^\times = \{1, -1\}$, so each nonzero integer $n$ has exactly one associate besides itself, namely $-n$: $3 \sim -3$, $12 \sim -12$; only $0$ equals its own opposite. In $\mathbb{K}[X]$ the units are the nonzero constants $\mathbb{K}^\times$, so $X - 1 \sim 2(X - 1) \sim -\tfrac{1}{3}(X - 1)$: a polynomial and all its nonzero scalar multiples are associates, which is why one singles out the monic representative.

Proposition — Divisibility through ideals

Let $A$ be an integral commutative ring and $a, b \in A$. Then $$ a \mid b \iff bA \subseteq aA, \qquad\text{and}\qquad a \sim b \iff aA = bA. $$

Proof

$(\Rightarrow)$ for divisibility. If $a \mid b$, write $b = ac$. Then every multiple $bd = a(cd)$ lies in $aA$, so $bA \subseteq aA$.
$(\Leftarrow)$ for divisibility. If $bA \subseteq aA$, then in particular $b = b\,1_A \in aA$, so $b = ac$ for some $c$, i.e. $a \mid b$.
Associates. $a \sim b$ means $a = ub$, $u \in A^\times$; then $b \mid a$, and $b = u^{-1}a$ gives $a \mid b$, so $aA \subseteq bA$ and $bA \subseteq aA$, i.e. $aA = bA$. Conversely $aA = bA$ gives $a \mid b$ and $b \mid a$: write $a = ub$ and $b = va$, so $a = uva$. If $a = 0$ then $b = 0$ and $a \sim b$; if $a \neq 0$, integrality cancels $a$ from $a = (uv)a$, giving $uv = 1_A$, so $u \in A^\times$ and $a \sim b$.

Example — The divisor lattice of an integer

For $\mathbb{Z}$, ideal inclusion reverses divisibility: $d \mid 12 \iff 12\mathbb{Z} \subseteq d\mathbb{Z}$, so a bigger divisor gives a smaller ideal. The six positive divisors of $12$, ordered by divisibility, form the lattice below — read upward it is the divisibility order, read as ideals it is reverse inclusion.

Method — Read divisibility off ideals

To turn a divisibility question in an integral ring into an ideal question: replace « $a \mid b$ » by « $bA \subseteq aA$ », and « $a$ and $b$ associate » by « $aA = bA$ ». Inclusion of ideals is often easier to manipulate — sums and intersections of ideals are again ideals (§1.2), which the elementwise divisibility relation does not directly offer.

Skills to practice

Expressing divisibility through ideals

II Ideals of $\mathbb{Z}$

II.1 The ideals of $\mathbb{Z}$

The first arc — rings and ideals in general — closes; the second begins, where the abstract notion of ideal is tested on $\mathbb{Z}$. Further group theory showed that the subgroups of $(\mathbb{Z}, +)$ are exactly the $n\mathbb{Z}$; an ideal is a subgroup, and in $\mathbb{Z}$ every subgroup turns out to be automatically absorbing — so the ideals of $\mathbb{Z}$ are precisely the $n\mathbb{Z}$, all principal.

Theorem — Ideals of $\mathbb{Z}$

The ideals of $\mathbb{Z}$ are exactly the subsets $n\mathbb{Z}$ for $n \in \mathbb{N}$. Every ideal of $\mathbb{Z}$ is principal: $n\mathbb{Z} = (n)$.

Proof

Each $n\mathbb{Z}$ is an ideal (§1.2). Conversely, let $I$ be an ideal of $\mathbb{Z}$. In particular $I$ is a subgroup of $(\mathbb{Z}, +)$, so by the classification of subgroups of $\mathbb{Z}$ recalled from Further group theory, $I = n\mathbb{Z}$ for a unique $n \in \mathbb{N}$. Thus the ideals of $\mathbb{Z}$ are exactly the $n\mathbb{Z} = (n)$, all principal.

Example — Sums and intersections in $\mathbb{Z}$

Since every ideal of $\mathbb{Z}$ is some $d\mathbb{Z}$, the operations of §1.2 produce ideals of the same form: $2\mathbb{Z} + 3\mathbb{Z} = \mathbb{Z} = 1\mathbb{Z}$ (because $1 = 3 - 2$), while $2\mathbb{Z} \cap 3\mathbb{Z} = 6\mathbb{Z}$ (the common multiples of $2$ and $3$). The next subsection reads $d$ and the intersection index as a gcd and an lcm.

Skills to practice

Determining the ideals of $\mathbb{Z}$

II.2 GCD and Bézout through ideals

A sum $a_1\mathbb{Z} + \dots + a_n\mathbb{Z}$ of principal ideals is an ideal of $\mathbb{Z}$, hence equal to a single $d\mathbb{Z}$. That $d$ is the gcd — and this ideal definition both reproduces the first-year gcd and hands Bézout's relation almost for free.

Definition — GCD of $n$ integers through ideals

Let $a_1, \dots, a_n \in \mathbb{Z}$ with $n \ge 2$. The sum $a_1\mathbb{Z} + \dots + a_n\mathbb{Z}$ is an ideal of $\mathbb{Z}$, equal to a unique $d\mathbb{Z}$ with $d \in \mathbb{N}$; this $d$ is the greatest common divisor $\gcd(a_1, \dots, a_n)$. Likewise the intersection $a_1\mathbb{Z} \cap \dots \cap a_n\mathbb{Z}$ equals a unique $m\mathbb{Z}$, $m \in \mathbb{N}$; this $m$ is the least common multiple.

Proposition — Agreement with the first-year gcd and lcm

The integer $d$ above is exactly the gcd of Arithmetic in $\mathbb{Z}$ — the greatest, for divisibility, of the common divisors of $a_1, \dots, a_n$ — and $m$ is the first-year lcm.

Proof

An integer $c$ divides every $a_i$ iff $a_i \in c\mathbb{Z}$ for every $i$, iff $a_i\mathbb{Z} \subseteq c\mathbb{Z}$ for every $i$, iff $d\mathbb{Z} = \sum a_i\mathbb{Z} \subseteq c\mathbb{Z}$, iff $c \mid d$. So the common divisors of the $a_i$ are exactly the divisors of $d$; $d$ is therefore their greatest element for divisibility — the first-year gcd. Dually, $c$ is a common multiple of the $a_i$ iff $c\mathbb{Z} \subseteq a_i\mathbb{Z}$ for every $i$, iff $c\mathbb{Z} \subseteq \bigcap a_i\mathbb{Z} = m\mathbb{Z}$, iff $m \mid c$; so $m$ is the first-year lcm.

Proposition — Bézout

Let $a_1, \dots, a_n \in \mathbb{Z}$ with $n \ge 2$. There exist integers $u_1, \dots, u_n$ with $$ \gcd(a_1, \dots, a_n) = a_1 u_1 + \dots + a_n u_n. $$ In particular the $a_i$ are coprime as a family — meaning $\gcd(a_1, \dots, a_n) = 1$, not necessarily pairwise — if and only if $a_1 u_1 + \dots + a_n u_n = 1$ for some integers $u_i$.

Proof

By definition $d\mathbb{Z} = a_1\mathbb{Z} + \dots + a_n\mathbb{Z}$, and $d \in d\mathbb{Z}$, so $d$ is a sum $a_1 u_1 + \dots + a_n u_n$ with $u_i \in \mathbb{Z}$. For the equivalence: if $d = 1$ the relation above gives $\sum a_i u_i = 1$; conversely if $\sum a_i u_i = 1$ then $1 \in \sum a_i\mathbb{Z} = d\mathbb{Z}$, so $d \mid 1$, hence $d = 1$.

Proposition — Gauss's lemma

Let $a, b, c \in \mathbb{Z}$. If $a \mid bc$ and $\gcd(a, b) = 1$, then $a \mid c$.

Proof

This result is recalled from Arithmetic in $\mathbb{Z}$; here is its one-line Bézout proof. Since $\gcd(a, b) = 1$, Bézout gives $au + bv = 1$, hence $c = acu + bcv$. Now $a \mid acu$ and $a \mid bcv$ (as $a \mid bc$), so $a \mid c$.

Example — A gcd of three integers

The ideal $6\mathbb{Z} + 10\mathbb{Z} + 15\mathbb{Z}$ equals $\mathbb{Z}$, so $\gcd(6, 10, 15) = 1$: the three integers are coprime as a family. Yet no two of them are coprime — $\gcd(6, 10) = 2$, $\gcd(6, 15) = 3$, $\gcd(10, 15) = 5$ — which is exactly the family-versus-pairwise distinction. A Bézout relation: $1 = 6 \cdot (-14) + 10 \cdot 7 + 15 \cdot 1$.

Method — Compute a gcd and a Bézout relation through ideals

For two integers $a, b$: run the Euclid algorithm of Arithmetic in $\mathbb{Z}$, which at each step replaces $a\mathbb{Z} + b\mathbb{Z}$ by an equal but smaller-data sum of ideals, until the last non-zero remainder $d$ — the generator of $a\mathbb{Z} + b\mathbb{Z}$. Back-substitution through the divisions then writes $d = au + bv$. For $n > 2$ integers, group: $\gcd(a_1, \dots, a_n) = \gcd(\gcd(a_1, \dots, a_{n-1}), a_n)$, since the sum of ideals is associative.

Skills to practice

Computing a gcd through ideals

III The rings $\mathbb{Z}/n\mathbb{Z}$

III.1 The ring $\mathbb{Z}/n\mathbb{Z}$

The third arc is the arithmetic of $\mathbb{Z}/n\mathbb{Z}$. Further group theory gave $\mathbb{Z}/n\mathbb{Z}$ as an additive group; we now add a product of classes and obtain a ring. Throughout § 3, $n$ is an integer $\ge 2$, so $\mathbb{Z}/n\mathbb{Z}$ is a non-trivial ring.

Theorem — $\mathbb{Z}/n\mathbb{Z}$ is a ring

The product $\bar a \times \bar b = \overline{ab}$ is well-defined on $\mathbb{Z}/n\mathbb{Z}$, and makes $(\mathbb{Z}/n\mathbb{Z}, +, \times)$ a commutative ring with unit $\bar 1$.

Proof

Well-definedness: if $\bar a = \bar a'$ and $\bar b = \bar b'$, then $a \equiv a'$ and $b \equiv b' \pmod n$, and the compatibility of congruence with multiplication, recalled from Arithmetic in $\mathbb{Z}$, gives $ab \equiv a'b' \pmod n$, i.e. $\overline{ab} = \overline{a'b'}$; the product of classes does not depend on the chosen representatives. The ring axioms then transfer from $\mathbb{Z}$: associativity, commutativity and distributivity of $\times$, and the neutrality of $\bar 1$, each follow by passing the corresponding identity of $\mathbb{Z}$ to classes. As $(\mathbb{Z}/n\mathbb{Z}, +)$ is already a commutative group, $(\mathbb{Z}/n\mathbb{Z}, +, \times)$ is a commutative ring.

Example — Multiplication in $\mathbb{Z}/4\mathbb{Z}$

The product table of $\mathbb{Z}/4\mathbb{Z}$ reads, on classes $\bar 0, \bar 1, \bar 2, \bar 3$: $$ \bar 2 \times \bar 2 = \bar 0, \qquad \bar 2 \times \bar 3 = \bar 6 = \bar 2, \qquad \bar 3 \times \bar 3 = \bar 9 = \bar 1. $$ Notice $\bar 2 \times \bar 2 = \bar 0$ with $\bar 2 \neq \bar 0$: the ring $\mathbb{Z}/4\mathbb{Z}$ is not integral.

Proposition — The canonical morphism

The map $\pi : \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$, $k \mapsto \bar k$, is a surjective ring morphism, with kernel $\operatorname{Ker}\pi = n\mathbb{Z}$.

Proof

By construction $\pi(k + \ell) = \overline{k+\ell} = \bar k + \bar\ell$, $\pi(k\ell) = \overline{k\ell} = \bar k \times \bar\ell$, and $\pi(1) = \bar 1$, so $\pi$ is a ring morphism; it is surjective since every class has a representative. Finally $\pi(k) = \bar 0$ iff $k \equiv 0 \pmod n$, iff $n \mid k$, iff $k \in n\mathbb{Z}$.

Skills to practice

Computing in $\mathbb{Z}/n\mathbb{Z}$

III.2 Units of $\mathbb{Z}/n\mathbb{Z}$ and the field $\mathbb{F}_p$

Which classes are invertible in the ring $\mathbb{Z}/n\mathbb{Z}$? Bézout answers at once: exactly those whose representative is coprime with $n$. From this follows the cleanest dividing line in the chapter — $\mathbb{Z}/n\mathbb{Z}$ is a field precisely when $n$ is prime.

Proposition — Units of $\mathbb{Z}/n\mathbb{Z}$

A class $\bar k \in \mathbb{Z}/n\mathbb{Z}$ is a unit if and only if $\gcd(k, n) = 1$.

Proof

The class $\bar k$ is a unit iff there is $\bar u$ with $\bar k \times \bar u = \bar 1$, iff there are $u, v \in \mathbb{Z}$ with $ku - 1 = nv$, i.e. $ku - nv = 1$. By Bézout (§2.2) such $u, v$ exist exactly when $\gcd(k, n) = 1$.

Theorem — Field criterion

For $n \ge 2$, the following are equivalent: (i) $\mathbb{Z}/n\mathbb{Z}$ is a field; (ii) $\mathbb{Z}/n\mathbb{Z}$ is integral; (iii) $n$ is prime. When $p$ is prime, the field $\mathbb{Z}/p\mathbb{Z}$ is written $\mathbb{F}_p$.

Proof

(i) $\Rightarrow$ (ii). Every field is integral (recalled from Algebraic structures).
(ii) $\Rightarrow$ (iii). By contraposition: if $n$ is not prime, write $n = ab$ with $a, b \in \llbracket 2, n-1 \rrbracket$. Then $\bar a \times \bar b = \bar n = \bar 0$ while $\bar a \neq \bar 0$ and $\bar b \neq \bar 0$, so $\mathbb{Z}/n\mathbb{Z}$ is not integral.
(iii) $\Rightarrow$ (i). If $n = p$ is prime, then for every $k \in \llbracket 1, p-1 \rrbracket$ we have $\gcd(k, p) = 1$, so $\bar k$ is a unit by the previous Proposition. Every non-zero class is a unit, so $\mathbb{Z}/p\mathbb{Z}$ is a field.

Example — $\mathbb{Z}/6\mathbb{Z}$ versus $\mathbb{F}_5$

$\mathbb{Z}/6\mathbb{Z}$ is not a field: $6$ is composite, and indeed $\bar 2 \times \bar 3 = \bar 0$ exhibits zero divisors; its units are $\bar 1$ and $\bar 5$ only. $\mathbb{Z}/5\mathbb{Z} = \mathbb{F}_5$ is a field: $5$ is prime, so each of $\bar 1, \bar 2, \bar 3, \bar 4$ is invertible — for instance $\bar 2 \times \bar 3 = \bar 6 = \bar 1$.

Method — Invert a class of $\mathbb{Z}/n\mathbb{Z}$

To invert $\bar k$ in $\mathbb{Z}/n\mathbb{Z}$: first check $\gcd(k, n) = 1$ (else $\bar k$ is not a unit). Then run the extended Euclid algorithm to produce a Bézout relation $ku + nv = 1$; reducing modulo $n$ gives $\bar k \times \bar u = \bar 1$, so $\bar u$ is the inverse. For instance in $\mathbb{Z}/7\mathbb{Z}$, $3 \cdot 5 - 7 \cdot 2 = 1$, so $\bar 3^{-1} = \bar 5$.

Skills to practice

Inverting a class

III.3 The Chinese remainder theorem

When $n$ factors into coprime pieces, the ring $\mathbb{Z}/n\mathbb{Z}$ itself splits accordingly. This is the Chinese remainder theorem: an isomorphism that turns one modulus into several independent ones, and a system of congruences into a single tuple.

Theorem — Chinese remainder theorem

Let $m, n \ge 2$ with $\gcd(m, n) = 1$. The map $$ \Phi : \mathbb{Z}/mn\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}, \qquad \overline{x} \mapsto (\hat x, \tilde x) $$ (where $\hat x$, $\tilde x$ are the classes of $x$ modulo $m$ and modulo $n$) is a ring isomorphism. More generally, for pairwise-coprime $n_1, \dots, n_r \ge 2$, $\mathbb{Z}/(n_1 \cdots n_r)\mathbb{Z}$ is isomorphic to $\mathbb{Z}/n_1\mathbb{Z} \times \dots \times \mathbb{Z}/n_r\mathbb{Z}$.

Proof

$\Phi$ is well-defined: if $x + kmn$ is another representative of $\overline{x}$, then it is congruent to $x$ both modulo $m$ and modulo $n$, so $\hat x$ and $\tilde x$ do not depend on the representative. It is a ring morphism, the two components $x \mapsto \hat x$ and $x \mapsto \tilde x$ being ring morphisms. It is injective: a class $\overline{x} \in \operatorname{Ker}\Phi$ means $\hat x = \hat 0$ and $\tilde x = \tilde 0$, i.e. $m \mid x$ and $n \mid x$; with $\gcd(m, n) = 1$, Gauss's lemma gives $mn \mid x$, so $\overline{x} = \bar 0$. Finally the two rings have the same cardinal $mn$, so the injective $\Phi$ is bijective — a ring isomorphism. The general statement follows by induction on $r$, since $n_1 \cdots n_{r-1}$ and $n_r$ are coprime.

Example — $\mathbb{Z}/6\mathbb{Z} \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}$

Since $\gcd(2, 3) = 1$, the map $\overline{x} \mapsto (\hat x, \tilde x)$ identifies the six classes of $\mathbb{Z}/6\mathbb{Z}$ with the six cells of the $2 \times 3$ grid below — each integer $x$ sitting at row $x \bmod 2$, column $x \bmod 3$.

Method — Solve a system of congruences

To solve $x \equiv a \ [m]$ and $x \equiv b \ [n]$ with $\gcd(m, n) = 1$: the pair $(\hat a, \tilde b)$ has, by the Chinese remainder theorem, a unique preimage $\overline{x_0}$ in $\mathbb{Z}/mn\mathbb{Z}$, and the solution set is $x_0 + mn\mathbb{Z}$. Concretely, write a Bézout relation $mu + nv = 1$; then $x_0 = a\,nv + b\,mu$ satisfies both congruences.

Skills to practice

Applying the Chinese remainder theorem

III.4 Euler's totient and Euler's theorem

Counting the units of $\mathbb{Z}/n\mathbb{Z}$ defines Euler's totient $\varphi$. A scope note: the § 3 convention « $n \ge 2$ » concerns the ring $\mathbb{Z}/n\mathbb{Z}$; the totient introduced now is a number-theoretic function on $\mathbb{N}^*$, and its argument is not tied to that convention. The Chinese remainder theorem makes $\varphi$ computable from the prime factorisation, and the group of units yields Euler's theorem.

Definition — Euler's totient

For $n \in \mathbb{N}^*$, Euler's totient is $$ \varphi(n) = \#\{k \in \llbracket 1, n \rrbracket \mid \gcd(k, n) = 1\}, $$ with $\varphi(1) = 1$. For $n \ge 2$, $\varphi(n) = \#(\mathbb{Z}/n\mathbb{Z})^\times$ by the units criterion of §3.2.

Example — Totient of a few small integers

The integers of $\llbracket 1, 12 \rrbracket$ coprime with $12$ are $1, 5, 7, 11$, so $\varphi(12) = 4$. For a prime, every integer of $\llbracket 1, p - 1 \rrbracket$ is coprime with $p$, hence $\varphi(7) = 6$ and, in general, $\varphi(p) = p - 1$. At the other extreme $\varphi(1) = 1$, and the four units of $\mathbb{Z}/12\mathbb{Z}$ are exactly $\overline{1}, \overline{5}, \overline{7}, \overline{11}$ — the count $4$ read off the units, as the Definition announces.

Proposition — Totient of a prime power

For $p$ prime and $k \ge 1$, $\varphi(p^k) = p^k - p^{k-1}$.

Proof

An integer of $\llbracket 1, p^k \rrbracket$ fails to be coprime with $p^k$ exactly when it is divisible by $p$. The multiples of $p$ in $\llbracket 1, p^k \rrbracket$ are $p, 2p, \dots, p^{k-1} \cdot p$, that is $p^{k-1}$ of them. Hence $\varphi(p^k) = p^k - p^{k-1}$.

Proposition — $\varphi$ is multiplicative

For $m, n \in \mathbb{N}^*$ with $\gcd(m, n) = 1$, $\varphi(mn) = \varphi(m)\varphi(n)$.

Proof

If $m = 1$ or $n = 1$ the identity is immediate from $\varphi(1) = 1$. Assume $m, n \ge 2$. The Chinese remainder theorem gives a ring isomorphism $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$, and a ring isomorphism carries units to units, so $(\mathbb{Z}/mn\mathbb{Z})^\times$ is in bijection with $(\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z})^\times = (\mathbb{Z}/m\mathbb{Z})^\times \times (\mathbb{Z}/n\mathbb{Z})^\times$ (units of a product, §1.1). Counting: $\varphi(mn) = \varphi(m)\varphi(n)$.

Proposition — Closed form for $\varphi$

For $n \ge 2$ with prime factorisation $n = p_1^{\alpha_1} \cdots p_r^{\alpha_r}$, $$ \varphi(n) = n \prod_{i=1}^{r} \left(1 - \frac{1}{p_i}\right). $$ The formula also holds for $n = 1$: the product is then empty, so the right-hand side is $1 = \varphi(1)$.

Proof

The prime powers $p_i^{\alpha_i}$ are pairwise coprime, so by multiplicativity and the prime-power formula, $$ \begin{aligned} \varphi(n) &= \varphi(p_1^{\alpha_1}) \cdots \varphi(p_r^{\alpha_r}) && \text{($\varphi$ multiplicative)} \\ &= \prod_{i=1}^{r} \left(p_i^{\alpha_i} - p_i^{\alpha_i - 1}\right) && \text{(prime-power totient)} \\ &= \prod_{i=1}^{r} p_i^{\alpha_i}\left(1 - \tfrac{1}{p_i}\right) && \text{(factor out $p_i^{\alpha_i}$)} \\ &= n \prod_{i=1}^{r} \left(1 - \tfrac{1}{p_i}\right) && \text{($\textstyle\prod p_i^{\alpha_i} = n$).} \end{aligned} $$

Theorem — Euler's theorem

Let $n \ge 2$ and $a \in \mathbb{Z}$ with $\gcd(a, n) = 1$. Then $$ a^{\varphi(n)} \equiv 1 \pmod n. $$

Proof

The units $(\mathbb{Z}/n\mathbb{Z})^\times$ form a group under multiplication: it is closed (a product of units is a unit), contains $\bar 1$, and contains the inverse of each element. Its cardinal is $\varphi(n)$. Since $\gcd(a, n) = 1$, the class $\bar a$ belongs to this group, and the order of an element divides the cardinal of a finite group — Lagrange's theorem, recalled from Further group theory. Hence $\bar a^{\varphi(n)} = \bar 1$, that is $a^{\varphi(n)} \equiv 1 \pmod n$.

Fermat as a special case

When $n = p$ is prime, $\varphi(p) = p - 1$, and Euler's theorem reads $a^{p-1} \equiv 1 \pmod p$ for $\gcd(a, p) = 1$ — Fermat's little theorem, recalled from Arithmetic in $\mathbb{Z}$. Euler's theorem is its extension to a composite modulus.

Method — Compute $\varphi(n)$

To compute $\varphi(n)$ for $n \ge 2$: factor $n = p_1^{\alpha_1} \cdots p_r^{\alpha_r}$, then apply $\varphi(p^k) = p^k - p^{k-1}$ on each prime power and multiply, or use the closed form $\varphi(n) = n \prod (1 - 1/p_i)$. For instance $\varphi(360) = \varphi(2^3)\varphi(3^2)\varphi(5) = 4 \cdot 6 \cdot 4 = 96$.

Skills to practice

Computing with Euler's totient

IV The rings $\mathbb{K}[X]$

IV.1 The ideals of $\mathbb{K}[X]$

Throughout this section $\mathbb{K}$ is a subfield of $\mathbb{C}$. The fourth arc replays § 2 with $\mathbb{K}[X]$ in place of $\mathbb{Z}$: the same theorem, the same proof, with the degree of a polynomial playing the role the absolute value of an integer played. Euclidean division — recalled from Arithmetic of polynomials — is again the engine, and every ideal of $\mathbb{K}[X]$ turns out principal.

Theorem — Ideals of the polynomial ring

Every ideal of $\mathbb{K}[X]$ is principal: it is $(P) = P\,\mathbb{K}[X]$ for some $P$. The zero ideal is $(0)$; a non-zero ideal has a unique monic generator.

Proof

Let $I$ be an ideal of $\mathbb{K}[X]$. If $I = \{0\}$ then $I = (0)$. Otherwise $I$ contains a non-zero polynomial; choose $P \in I$ non-zero of minimal degree. Since $I$ is an ideal, $(P) = P\,\mathbb{K}[X] \subseteq I$. Conversely, let $A \in I$. Euclidean division gives $A = PQ + R$ with $\deg R < \deg P$. Then $R = A - PQ \in I$ ($I$ being an ideal); were $R$ non-zero it would contradict the minimality of $\deg P$, so $R = 0$ and $A = PQ \in (P)$. Hence $I = (P)$. Two generators differ by a non-zero scalar (associates in the integral ring $\mathbb{K}[X]$, by §1.3, and the units of $\mathbb{K}[X]$ are the non-zero constants); dividing $P$ by its leading coefficient gives the unique monic generator.

Example — The ideal of polynomials vanishing at $a$

For $a \in \mathbb{K}$, the ideal $\operatorname{Ker}(\operatorname{ev}_a) = \{P \mid P(a) = 0\}$ of §1.2 is non-zero (it contains $X - a$) and principal, so it has a unique monic generator. As $X - a$ is monic and lies in it, and any element is a multiple of $X - a$ (a root $a$ factors out), that generator is $X - a$: $\operatorname{Ker}(\operatorname{ev}_a) = (X - a)$.

Skills to practice

Determining the ideals of $\mathbb{K}[X]$

IV.2 GCD and Bézout through ideals

With ideals of $\mathbb{K}[X]$ all principal, the gcd of polynomials is defined exactly as in § 2: the generator of a sum of ideals. The agreement with the first-year polynomial gcd, Bézout's relation and Gauss's lemma all carry over word for word.

Definition — GCD of $n$ polynomials through ideals

Let $A_1, \dots, A_n \in \mathbb{K}[X]$ with $n \ge 2$. The sum $(A_1) + \dots + (A_n)$ is an ideal of $\mathbb{K}[X]$; its monic-or-zero generator is the greatest common divisor $D = \gcd(A_1, \dots, A_n)$ — zero exactly when every $A_i = 0$. The monic-or-zero generator $M$ of $(A_1) \cap \dots \cap (A_n)$ is the least common multiple.

Proposition — Agreement with the first-year gcd and lcm

The polynomial $D$ above is exactly the monic gcd of Arithmetic of polynomials — the common divisors of $A_1, \dots, A_n$ are exactly the divisors of $D$ — and the lcm above is the first-year monic lcm. In the degenerate all-zero case both sides agree as $0$, by the monic-or-zero convention fixed in the Definition.

Proof

A polynomial $C$ divides every $A_i$ iff $(A_i) \subseteq (C)$ for every $i$ (§1.3), iff $(D) = \sum (A_i) \subseteq (C)$, iff $C \mid D$. So the common divisors of the $A_i$ are exactly the divisors of $D$, which makes $D$ their gcd in the sense of Arithmetic of polynomials. Dually, $C$ is a common multiple iff $(C) \subseteq (A_i)$ for every $i$, iff $(C) \subseteq \bigcap (A_i) = (M)$, iff $M \mid C$. So the common multiples of the $A_i$ are exactly the multiples of $M$, which makes $M$ their first-year monic lcm.

Proposition — Bézout for polynomials

Let $A_1, \dots, A_n \in \mathbb{K}[X]$ with $n \ge 2$. There exist $U_1, \dots, U_n \in \mathbb{K}[X]$ with $\gcd(A_1, \dots, A_n) = A_1 U_1 + \dots + A_n U_n$. In particular the $A_i$ are coprime as a family if and only if $A_1 U_1 + \dots + A_n U_n = 1$ for some $U_i$.

Proof

The gcd $D$ generates $(A_1) + \dots + (A_n)$, so $D \in (A_1) + \dots + (A_n)$ writes $D = \sum A_i U_i$. If the $A_i$ are coprime as a family, $D = 1$ and $\sum A_i U_i = 1$; conversely if $\sum A_i U_i = 1$ then $1 \in \sum (A_i) = (D)$, so $D \mid 1$, hence $D = 1$.

Proposition — Gauss's lemma for polynomials

Let $A, B, C \in \mathbb{K}[X]$. If $A \mid BC$ and $\gcd(A, B) = 1$, then $A \mid C$.

Proof

Recalled from Arithmetic of polynomials; one-line Bézout proof. As $\gcd(A, B) = 1$, Bézout gives $AU + BV = 1$, so $C = ACU + BCV$. Now $A \mid ACU$ and $A \mid BCV$ (since $A \mid BC$), hence $A \mid C$.

Example — A gcd of two polynomials

With $A = X^2 - 1$ and $B = X^2 - X$, the ideal $(A) + (B)$ is generated by $\gcd(A, B)$. Since $A = (X-1)(X+1)$ and $B = X(X-1)$, the monic generator is $X - 1$: $\gcd(X^2 - 1, X^2 - X) = X - 1$, and $(X^2-1) - (X^2-X) = X - 1$ is a Bézout relation.

Method — Compute a polynomial gcd through ideals

For $A, B \in \mathbb{K}[X]$: run the Euclid algorithm of Arithmetic of polynomials — each Euclidean division keeps the sum of ideals $(A) + (B)$ unchanged while lowering the degree of the data — until the last non-zero remainder; made monic, it is $\gcd(A, B)$. Back-substitution gives a Bézout pair $(U, V)$. For $n > 2$ polynomials, group as in §2.2.

Skills to practice

Computing a polynomial gcd

IV.3 Irreducible factorisation

This last subsection of the arc is, honestly, a recall: the irreducible polynomial, the existence and uniqueness of factorisation, and d'Alembert-Gauss are all material of Polynomials. They are stated here, in the ideal language of the chapter; their proofs are not re-derived. The one short proof reproduced — for consolidation — is the deduction of the irreducibles of $\mathbb{C}[X]$ and $\mathbb{R}[X]$ from d'Alembert-Gauss.

Irreducible polynomial

Recalled from Arithmetic of polynomials: a polynomial $P \in \mathbb{K}[X]$ is irreducible when it is non-constant and its only divisors are the non-zero constants and the associates of $P$ — equivalently, $P = QR$ forces $Q$ or $R$ constant. In the ideal language of this chapter, a non-constant $P$ is irreducible exactly when the only ideals containing $(P)$ are $(P)$ and $\mathbb{K}[X]$.

Proposition — Irreducible factorisation

Every non-constant $P \in \mathbb{K}[X]$ is a non-zero scalar times a product of monic irreducible polynomials, and this writing is unique up to the order of the factors.

Status of this factorisation

The existence and uniqueness of this factorisation are established in Polynomials. Énoncé admis ici — the proof is not reproduced; the chapter uses the result as a known fact.

Theorem — Irreducibles over $\mathbb{C}$ and over $\mathbb{R}$

The irreducible polynomials of $\mathbb{C}[X]$ are exactly the degree-$1$ polynomials. The irreducible polynomials of $\mathbb{R}[X]$ are the degree-$1$ polynomials and the degree-$2$ polynomials with negative discriminant.

Proof

A degree-$1$ polynomial is irreducible in any $\mathbb{K}[X]$. For $\mathbb{C}[X]$: a non-constant $P$ of degree $\ge 2$ has, by d'Alembert-Gauss, a root $\alpha \in \mathbb{C}$, so $P = (X - \alpha)Q$ with $\deg Q \ge 1$, and $P$ is reducible — hence the irreducibles of $\mathbb{C}[X]$ are exactly the degree-$1$ polynomials. La démonstration du théorème de d'Alembert-Gauss est hors programme — it is cited, not proved.
For $\mathbb{R}[X]$: a degree-$2$ polynomial with negative discriminant has no real root, so no degree-$1$ real factor, hence is irreducible. Conversely, let $P \in \mathbb{R}[X]$ be irreducible of degree $\ge 2$. It has a root $\alpha \in \mathbb{C}$ (d'Alembert-Gauss); $\alpha$ is not real (else $X - \alpha$ would be a real factor), and the conjugate $\bar\alpha$ is also a root of $P$ since $P$ has real coefficients. Since $\alpha \neq \bar\alpha$ are two distinct roots of $P$, the coprime factors $X - \alpha$ and $X - \bar\alpha$ each divide $P$ in $\mathbb{C}[X]$, hence so does their product $Q = (X - \alpha)(X - \bar\alpha) = X^2 - 2\operatorname{Re}(\alpha)X + |\alpha|^2$ — a real polynomial of degree $2$ with negative discriminant. The Euclidean division of $P$ by $Q$ in $\mathbb{R}[X]$ gives $P = QS + R$ with $S, R \in \mathbb{R}[X]$; the same division in $\mathbb{C}[X]$ has remainder $0$, and by uniqueness of Euclidean division $R = 0$, so $Q$ divides $P$ in $\mathbb{R}[X]$. As $P$ is irreducible, $P$ is an associate of $Q$, so $\deg P = 2$.

Example — Factor $X^4 + 1$

Factor $X^4 + 1$ into monic irreducibles over $\mathbb{C}$, then over $\mathbb{R}$.

Answer

The roots of $X^4 = -1$ are the fourth roots of $-1$, namely $e^{i\pi/4}, e^{3i\pi/4}, e^{5i\pi/4}, e^{7i\pi/4}$. Over $\mathbb{C}$, the irreducibles being the degree-$1$ polynomials, $$ X^4 + 1 = (X - e^{i\pi/4})(X - e^{3i\pi/4})(X - e^{5i\pi/4})(X - e^{7i\pi/4}). $$ Over $\mathbb{R}$, pair each root with its conjugate: $e^{i\pi/4}$ with $e^{7i\pi/4}$, and $e^{3i\pi/4}$ with $e^{5i\pi/4}$. Each pair gives a real quadratic with negative discriminant: $$ X^4 + 1 = \left(X^2 - \sqrt{2}\,X + 1\right)\left(X^2 + \sqrt{2}\,X + 1\right). $$

Skills to practice

Factoring into irreducibles

V Algebras

V.1 Algebras and subalgebras

The final, short arc names a structure already met many times: $\mathbb{K}[X]$, $\mathcal{M}_n(\mathbb{K})$, $\mathcal{L}(E)$ each carry, at once, a vector-space structure and a ring structure, the two compatible. Such an object is an algebra. Throughout § 5, $\mathbb{K}$ is a field; the concrete examples take $\mathbb{K} = \mathbb{R}$ or $\mathbb{C}$.

Definition — $\mathbb{K}$-algebra

A $\mathbb{K}$-algebra is a set $\mathcal{A}$ carrying three laws $+$, $\times$ and an external law $\cdot$ such that:

$(\mathcal{A}, +, \cdot)$ is a $\mathbb{K}$-vector space;
$(\mathcal{A}, +, \times)$ is a ring (unital, not necessarily commutative);
the product $\times$ is $\mathbb{K}$-bilinear — linear in each variable separately. Additivity in each variable is already the distributivity of the ring; what is required in addition is compatibility with the scalars: $(\lambda \cdot x) \times (\mu \cdot y) = \lambda\mu \cdot (x \times y)$ for all $\lambda, \mu \in \mathbb{K}$ and $x, y \in \mathcal{A}$.

Example — The classical algebras

Each of the following is a $\mathbb{K}$-algebra: the polynomials $\mathbb{K}[X]$ (commutative); the square matrices $\mathcal{M}_n(\mathbb{K})$ and the endomorphisms $\mathcal{L}(E)$ of a $\mathbb{K}$-vector space $E$ (non-commutative for $n \ge 2$, resp. $\dim E \ge 2$); the functions $\mathcal{F}(I, \mathbb{K})$ on a non-empty set $I$, with pointwise operations (commutative).

Definition — Subalgebra

A subalgebra of a $\mathbb{K}$-algebra $\mathcal{A}$ is a subset $\mathcal{B}$ that is at once a sub-ring of $\mathcal{A}$ and a vector subspace of $\mathcal{A}$.

Proposition — Subalgebra characterisation

A subset $\mathcal{B}$ of a $\mathbb{K}$-algebra $\mathcal{A}$ is a subalgebra if and only if it contains $1_{\mathcal{A}}$ and is stable under $+$, under $\times$, and under multiplication by scalars.

Proof

If $\mathcal{B}$ is a subalgebra it is a sub-ring (so contains $1_{\mathcal{A}}$, stable under $+$ and $\times$) and a subspace (stable under scalars). Conversely, the four stated closures make $\mathcal{B}$ a sub-ring (containing $1_{\mathcal{A}}$, stable under $+$, additive inverses — $-x = (-1)\cdot x$ — and $\times$) and a vector subspace (stable under $+$ and scalars, non-empty), hence a subalgebra.

Example — Upper-triangular matrices

The set of upper-triangular matrices of $\mathcal{M}_n(\mathbb{K})$ contains the identity, and is stable under sum, product and scalar multiplication — a sum and a product of upper-triangular matrices stay upper-triangular. It is therefore a subalgebra of $\mathcal{M}_n(\mathbb{K})$.

Skills to practice

Verifying an algebra structure

V.2 Algebra morphisms

A map between algebras that respects both structures at once — the ring structure and the vector-space structure — is an algebra morphism. The example to keep in mind, and the bridge to the next chapter, is the substitution of an endomorphism into a polynomial.

Definition — Algebra morphism

Let $\mathcal{A}$, $\mathcal{B}$ be $\mathbb{K}$-algebras. A map $\varphi : \mathcal{A} \to \mathcal{B}$ is a morphism of $\mathbb{K}$-algebras when it is at once a ring morphism and a linear map.

Example — Evaluation $P \mapsto P(a)$

For $a \in \mathbb{K}$, the evaluation $\operatorname{ev}_a : \mathbb{K}[X] \to \mathbb{K}$, $P \mapsto P(a)$, is a morphism of $\mathbb{K}$-algebras: it is a ring morphism (it respects $+$, $\times$ and sends $1$ to $1$) and a linear map ($(\lambda P + \mu Q)(a) = \lambda P(a) + \mu Q(a)$).

Example — Substitution $P \mapsto P(u)$

Let $E$ be a $\mathbb{K}$-vector space and $u \in \mathcal{L}(E)$. Show that $\Psi_u : \mathbb{K}[X] \to \mathcal{L}(E)$, $P \mapsto P(u)$, is a morphism of $\mathbb{K}$-algebras.

Answer

Write $P = \sum a_k X^k$, so $P(u) = \sum a_k u^k$ (with $u^0 = \operatorname{Id}_E$). The map $\Psi_u$ is linear: $(\lambda P + \mu Q)(u) = \lambda P(u) + \mu Q(u)$, since substitution is coefficientwise. It is a ring morphism: $\Psi_u(1) = \operatorname{Id}_E$; $\Psi_u(P + Q) = \Psi_u(P) + \Psi_u(Q)$; and $\Psi_u(PQ) = \Psi_u(P)\,\Psi_u(Q)$ because, the powers $u^k$ all commuting with one another, the product $P(u)\,Q(u)$ expands by the same rule as the polynomial product $PQ$. Hence $\Psi_u$ is a morphism of $\mathbb{K}$-algebras.

Definition — The algebra generated by an endomorphism

For $u \in \mathcal{L}(E)$, the set $\mathbb{K}[u] = \{P(u) \mid P \in \mathbb{K}[X]\}$ is the image of the morphism $\Psi_u$ of the previous Example; it is therefore a subalgebra of $\mathcal{L}(E)$ — the subalgebra generated by $u$.

Method — Check that a map is an algebra morphism

To prove $\varphi : \mathcal{A} \to \mathcal{B}$ is a morphism of $\mathbb{K}$-algebras, check the two layers: (i) it is linear — $\varphi(\lambda x + \mu y) = \lambda\varphi(x) + \mu\varphi(y)$; (ii) it is a ring morphism — $\varphi(x \times y) = \varphi(x) \times \varphi(y)$ and $\varphi(1_{\mathcal{A}}) = 1_{\mathcal{B}}$. Linearity already covers $\varphi(x + y) = \varphi(x) + \varphi(y)$, so only the product and the unit remain to check for the ring layer.

Going further

The ideal viewpoint returns in Polynomials of an endomorphism: the polynomials annihilating an endomorphism $u$ form an ideal of $\mathbb{K}[X]$, and its monic generator — the minimal polynomial $\pi_u$ — drives the reduction theory of the next chapters. The algebra $\mathbb{K}[u]$ introduced above is the natural home of that study.

Skills to practice

Checking an algebra morphism