University Mathematics — Year 3 · Bachelor Year 3

2Rings and Arithmetic

Ordinary integers factor uniquely into primes; so do polynomials over a field. Are these two facts one theorem? This chapter answers yes, and finds the exact hypotheses that make an “arithmetic” possible in a commutative ring: the chain

\text{Euclidean} \;\Longrightarrow\; \text{principal} \;\Longrightarrow\; \text{factorial (UFD)},

with all implications proved and all converses refuted. The theory is then tested where it earns its keep: the Gaussian integers $\Z[\iu]$ (which will crack Fermat’s two-squares theorem in the weekend problem), polynomial rings in several variables (Gauss’s lemma, Eisenstein’s criterion), and Noetherian rings, culminating in Hilbert’s basis theorem. Throughout, ring means commutative ring with unit $1 \neq 0$ ; the Year 2 volume’s ideals of $\Z$ and $K[X]$ are our two guiding examples.

2.1 Ideals, quotients, and the isomorphism theorem

Definition 2.1

An ideal $I$ of a ring $A$ is an additive subgroup such that $AI \subseteq I$ . The quotient ring $A/I$ is the quotient group $(A, +)/I$ with the multiplication $(a + I)(b + I) = ab + I$ : well defined, since changing $a$ to $a + x$ , $b$ to $b + y$ ( $x, y \in I$ ) changes $ab$ by $ay + xb + xy \in I$ . The projection $\pi \colon A \to A/I$ is a surjective ring morphism with kernel $I$ , and kernels of ring morphisms are exactly the ideals.

Theorem 2.2 (First isomorphism theorem)

If $f \colon A \to B$ is a ring morphism, then $\bar f\colon A/\ker f \to \operatorname{im} f$ , $a + \ker f \mapsto f(a)$ , is a ring isomorphism. More generally $f$ factors through $A/I$ for any ideal $I \subseteq \ker f$ . The ideals of $A/I$ are the $J/I$ for $J \supseteq I$ an ideal of $A$ (correspondence theorem).

Proof. As for groups (Theorems 1.3 and 1.5), noting that all maps in sight also respect products: $\bar f$ is well defined, bijective onto the image, and multiplicative; the correspondence $J \mapsto J/I$ , $\bar J \mapsto \pi^{-1}(\bar J)$ preserves ideals in both directions because $\pi$ is a surjective ring morphism. ∎

Definition 2.3

Let $I \subsetneq A$ be a proper ideal. $I$ is prime if $ab \in I \Rightarrow a \in I$ or $b \in I$ ; $I$ is maximal if no ideal lies strictly between $I$ and $A$ .

Proposition 2.4

$I$ is prime $\iff$ $A/I$ is an integral domain; $I$ is maximal $\iff$ $A/I$ is a field. In particular maximal ideals are prime.

Proof. Write $\bar a$ for classes in $A/I$ . “ $I$ prime” translates verbatim to “ $\bar a\bar b = 0 \Rightarrow \bar a = 0$ or $\bar b = 0$ ”, and $A/I \neq 0$ to $I \neq A$ : that is the definition of a domain. For maximality, use the correspondence theorem: no ideal strictly between $I$ and $A$ $\iff$ $A/I$ has no ideal other than $0$ and itself $\iff$ $A/I$ is a field — for the last step: in a field the only ideals are $0$ and everything (an ideal containing $x \ne 0$ contains $x^{-1}x = 1$ ); conversely if every nonzero $x$ generates the unit ideal, then $xy = 1$ for some $y$ . Fields are domains, so maximal ideals are prime. ∎

Example 2.5

In $\Z$ : the prime ideals are $(0)$ and the $(p)$ , $p$ prime; the maximal ones are the $(p)$ ( $\Z/p\Z = \mathbb F_p$ is a field, $\Z/(0) = \Z$ is not). In $K[X, Y]$ : $(X) \subsetneq (X, Y)$ are both prime ( $K[X,Y]/(X) \cong K[Y]$ , a domain; $K[X,Y]/(X,Y) \cong K$ , a field), so $(X)$ is prime but not maximal.

To guarantee that maximal ideals exist in full generality, we need a set-theoretic principle. A partially ordered set is inductive if every totally ordered subset (chain) has an upper bound.

Theorem 2.6 (Zorn’s lemma)

Every nonempty inductive partially ordered set has a maximal element.

Proof. Admitted at this level. ∎

Remark 2.7

This is not a theorem of ordinary mathematics but an axiom: it is equivalent, over the basic Zermelo–Fraenkel axioms of set theory, to the axiom of choice (“every product of nonempty sets is nonempty”), which we accept throughout this book. We flag each use. Analysis will invoke it again (Hahn–Banach, Chapter 8).

Theorem 2.8 (Krull)

Every proper ideal $I \subsetneq A$ is contained in a maximal ideal.

Proof. Order by inclusion the set $\mathcal E$ of proper ideals containing $I$ ; it is nonempty ( $I \in \mathcal E$ ). A chain $(J_\lambda)$ in $\mathcal E$ has upper bound $J = \bigcup J_\lambda$ : an ideal (any $a, b \in J$ lie in a common $J_\lambda$ by totality), proper ( $1 \notin J_\lambda$ for all $\lambda$ ), containing $I$ . Zorn’s lemma yields a maximal element of $\mathcal E$ , which is a maximal ideal containing $I$ (an ideal strictly above it and proper would lie in $\mathcal E$ ). ∎

Theorem 2.9 (Chinese remainder theorem)

Let $I_1, \dots, I_n$ be pairwise comaximal ideals of $A$ ( $I_k + I_l = A$ for $k \neq l$ ). Then

A\Big/\bigcap_{k=1}^n I_k \;\xrightarrow{\;\sim\;}\; \prod_{k=1}^n A/I_k, \qquad a \longmapsto (a + I_1, \dots, a + I_n),

and moreover $\bigcap_k I_k = I_1 I_2 \cdots I_n$ (the ideal generated by products).

Proof. The map $f(a) = (a + I_k)_k$ is a ring morphism with kernel $\bigcap I_k$ ; by Theorem 2.2 it suffices to prove surjectivity. Fix $k$ ; for each $l \neq k$ write $1 = u_l + v_l$ with $u_l \in I_k$ , $v_l \in I_l$ (comaximality). Then

e_k = \prod_{l \neq k} v_l = \prod_{l\neq k}(1 - u_l) \equiv 1 \pmod{I_k}, \qquad e_k \in I_l \ (l \neq k),

so $f(e_k) = (0, \dots, 1, \dots, 0)$ ; given a target $(a_k + I_k)_k$ , the element $\sum_k a_k e_k$ maps to it.

Products vs intersection: $I_1\cdots I_n \subseteq \bigcap I_k$ always. Conversely, by induction it suffices to treat $n = 2$ (one checks $I_1$ and $I_2\cdots I_n$ are comaximal: multiplying $1 = u_l + v_l$ over $l \geq 2$ gives $1 \in I_1 + I_2\cdots I_n$ ). For $n = 2$ : write $1 = u + v$ , $u \in I_1$ , $v \in I_2$ ; for $x \in I_1 \cap I_2$ , $x = xu + xv \in I_2I_1 + I_1I_2 = I_1I_2$ . ∎

Example 2.10

In $\Z$ with $I_k = (m_k)$ , $m_k$ pairwise coprime: $\Z/(m_1\cdots m_n)\Z \cong \prod \Z/m_k\Z$ — the Year 2 volume’s Chinese remainder theorem. Restricting to units: $(\Z/mn\Z)^\times \cong (\Z/m\Z)^\times \times (\Z/n\Z)^\times$ for $\gcd(m,n)=1$ , whence the multiplicativity of Euler’s $\varphi$ (Exercise 2.8).

2.2 Divisibility: Euclidean, principal, factorial

Definition 2.11

Let $A$ be an integral domain, $a, b \in A$ . We say $a$ divides $b$ ( $a \mid b$ ) if $b \in (a) = aA$ . Elements $a, b$ are associates if $a = ub$ with $u \in A^\times$ (equivalently $(a) = (b)$ ). A nonzero nonunit $p$ is:

irreducible if $p = ab$ forces $a \in A^\times$ or $b \in A^\times$ ;
prime if $p \mid ab$ forces $p \mid a$ or $p \mid b$ (i.e. the ideal $(p)$ is prime).

Proposition 2.12

In any domain, prime $\Rightarrow$ irreducible. The converse is false in general: in $\Z[\iu\sqrt 5] = \{a + \iu b\sqrt5 : a, b \in \Z\}$ , the element $2$ is irreducible but not prime.

Proof. Let $p$ be prime and $p = ab$ . Then $p \mid ab$ , say $p \mid a$ : $a = pc$ , so $p = pcb$ , and cancelling $p$ (domain!) gives $cb = 1$ : $b \in A^\times$ .

In $\Z[\iu\sqrt5]$ , use the norm $N(x + \iu y\sqrt 5) = x^2 + 5y^2$ , which is multiplicative (it is $\abs z^2$ ). If $2 = ab$ with $a, b$ nonunits, then $4 = N(a)N(b)$ with $N(a), N(b) \neq 1$ (norm- $1$ elements are $\pm1$ , the units), so $N(a) = 2$ : impossible, $x^2 + 5y^2 = 2$ has no integer solution. So $2$ is irreducible. But $2 \mid 6 = (1 + \iu\sqrt5)(1 - \iu\sqrt5)$ while $2$ divides neither factor ( $\frac12 \pm \frac{\iu\sqrt5}2 \notin \Z[\iu\sqrt5]$ ): not prime. ∎

Definition 2.13

An integral domain $A$ is:

Euclidean if there is a map $\nu \colon A \setminus \{0\} \to \N$ (a Euclidean function) such that for all $a, b$ with $b \ne 0$ there exist $q, r$ with $a = bq + r$ and ( $r = 0$ or $\nu(r) < \nu(b)$ );
principal (a PID) if every ideal is of the form $(a)$ ;
factorial (a UFD) if every nonzero nonunit is a product of irreducibles, uniquely up to order and associates.

Theorem 2.14

Euclidean $\Rightarrow$ principal.

Proof. Let $I \neq (0)$ be an ideal and $b \in I \setminus\{0\}$ with $\nu(b)$ minimal. For $a \in I$ , divide: $a = bq + r$ ; then $r = a - bq \in I$ , and $\nu(r) < \nu(b)$ would contradict minimality, so $r = 0$ and $a \in (b)$ : $I = (b)$ . ∎

Example 2.15

$\Z$ (with $\nu = \abs\cdot$ ) and $K[X]$ (with $\nu = \deg$ ) are Euclidean — the Year 2 volume proved both divisions. So is $\Z[\iu]$ , with $\nu = N$ the square norm (Exercise 2.4); the geometry of the proof is in the figure below. A PID that is not Euclidean exists but is delicate to certify (the standard example is $\Z\bigl[\frac{1+\iu\sqrt{19}}2\bigr]$ ); a UFD that is not a PID is easy: $K[X, Y]$ (Exercise 2.6), or $\Z[X]$ .

Division in the Gaussian integers: the exact quotient a/b ∈ ℂ lies within distance ≤ √2/2 < 1 of some lattice point q ∈ ℤ[ ]; then r = a - bq has N(r) = N(b)\,|a/b - q|2 < N(b). One Euclidean division, hence a whole arithmetic. — Division in the Gaussian integers: the exact quotient $a/b \in \C$ lies within distance $\leq \frac{\sqrt2}{2} < 1$ of some lattice point $q \in \Z[\iu]$ ; then $r = a - bq$ has $N(r) = N(b)\,\abs{a/b - q}^2 < N(b)$ . One Euclidean division, hence a whole arithmetic.

Lemma 2.16 (Ascending chains of principal ideals)

In a PID, every increasing sequence of ideals $I_1 \subseteq I_2 \subseteq \cdots$ is eventually constant.

Proof. $I = \bigcup_n I_n$ is an ideal (the union is increasing), so $I = (a)$ ; the element $a$ lies in some $I_N$ , and then $I = (a) \subseteq I_N \subseteq I_n \subseteq I$ for $n \geq N$ . ∎

Lemma 2.17 (Bézout; Euclid’s lemma)

Let $A$ be a PID and $a, b \in A$ . Then $(a) + (b) = (d)$ for some $d$ , a greatest common divisor: $d \mid a$ , $d \mid b$ , and every common divisor of $a, b$ divides $d$ ; moreover $d = au + bv$ for some $u, v$ (Bézout). Consequently every irreducible element of a PID is prime.

Proof. $(a) + (b)$ is an ideal, hence $(d)$ ; $a, b \in (d)$ gives $d \mid a, b$ ; and $d = au + bv \in (a) + (b)$ . A common divisor $c$ of $a, b$ divides $au + bv = d$ .

Euclid: let $p$ be irreducible, $p \mid ab$ , $p \nmid a$ . A gcd $d$ of $p$ and $a$ divides $p$ , so $d$ is a unit or an associate of $p$ (irreducibility); associate is excluded by $p \nmid a$ . So $1 = pu + av$ , whence $b = pub + abv$ , and $p$ divides both terms: $p \mid b$ . ∎

Theorem 2.18

Principal $\Rightarrow$ factorial.

Proof. Existence. Suppose some nonzero nonunit $a$ has no factorization into irreducibles. Then $a$ is not irreducible: $a = a_1b_1$ with both factors nonunits; at least one of them, say $a_1$ , again has no factorization (a product of two factorizable elements is factorizable). Iterating, we get $a = a_0, a_1, a_2, \dots$ , each a proper divisor of the last with no factorization, so $(a_0) \subsetneq (a_1) \subsetneq (a_2) \subsetneq \cdots$ — the inclusions are strict because $a_n = a_{n+1}c$ with $c$ a nonunit means $(a_n) = (a_{n+1})$ would force $c \in A^\times$ (cancel in a domain). This contradicts Lemma 2.16.

Uniqueness. Let $p_1 \cdots p_r = q_1 \cdots q_s$ with all factors irreducible, $r \leq s$ , by induction on $r$ . The prime (Lemma 2.17) $p_1$ divides the right-hand side, so divides some $q_j$ ; renumber $j = 1$ . As $q_1$ is irreducible and $p_1$ is not a unit, $q_1 = u p_1$ with $u \in A^\times$ : $p_1, q_1$ are associates. Cancel $p_1$ : $p_2 \cdots p_r = (u q_2) q_3\cdots q_s$ and conclude by induction ( $r = 1$ forces $s = 1$ : a unit times irreducibles cannot be $1$ ). ∎

Remark 2.19

In a UFD, gcds exist (take minimal exponents in the factorizations) and Euclid’s lemma holds — irreducible $=$ prime (Exercise 2.2) — but Bézout may fail: in $\Z[X]$ , $\gcd(2, X) = 1$ yet $1 \neq 2U + XV$ (evaluate at $X = 0$ : $1 = 2U(0)$ , impossible). Bézout identities are the exclusive property of PIDs.

Example 2.20 (A ring without unique factorization)

None of the implications Euclidean $\Rightarrow$ PID $\Rightarrow$ UFD is an equivalence, and the failure of the last is worth seeing once in complete detail. In

A = \Z[\iu\sqrt5] = \{a + \iu b\sqrt5 : a, b \in \Z\}, \qquad N(a + \iu b\sqrt5) = a^2 + 5b^2,

the norm is multiplicative and $N(z) = 1$ iff $z \in A^\times = \{\pm1\}$ . Consider

6 = 2 \cdot 3 = (1 + \iu\sqrt5)(1 - \iu\sqrt5).

All four factors are irreducible: their norms are $4, 9, 6, 6$ , and a proper factorization $z = z_1z_2$ would force $N(z_1) \in \{2, 3\}$ — but $a^2 + 5b^2$ never equals $2$ or $3$ ( $b = 0$ leaves the non-squares $2, 3$ ; $\abs b \geq 1$ gives $\geq 5$ ). Yet $2$ is associate to neither $1 \pm \iu\sqrt5$ (norms $4 \neq 6$ ): two genuinely different factorizations of $6$ into irreducibles. Equivalently, irreducible $\neq$ prime here: $2$ divides the product $(1 + \iu\sqrt5)(1 - \iu\sqrt5) = 6$ but neither factor (norms again). The ideal-theoretic repair of this failure — factorizing ideals rather than elements — is the birth of algebraic number theory; at our level, the example calibrates how special the Euclidean rings $\Z$ , $K[X]$ , $\Z[\iu]$ of this chapter really are.

Method 2.21

To identify a quotient ring $A/I$ , hunt for a surjective morphism $f \colon A \to B$ with kernel $I$ and invoke Theorem 2.2; when $A = C[X]$ is a polynomial ring, $f$ is usually an evaluation. Thus $\Z[X]/(X^2+1) \cong \Z[\iu]$ (evaluate at $\iu$ ), $K[X,Y]/(Y - X^2) \cong K[X]$ (evaluate $Y$ at $X^2$ ), $\R[X]/(X^2+1) \cong \C$ . To show $I$ prime or maximal, show the quotient is a domain or a field (Proposition 2.4).

2.3 Polynomials over a UFD: Gauss and Eisenstein

Throughout this section $A$ is a UFD with fraction field $K$ (constructed as the field of formal quotients $a/b$ , $b \neq 0$ , exactly like $\Q$ from $\Z$ ; the Year 2 volume did this construction for $\Q$ , and it transfers verbatim). Our goal: factoriality passes from $A$ to $A[X]$ , and irreducibility over $A$ is essentially irreducibility over the bigger field $K$ .

Definition 2.22

The content $c(P)$ of a nonzero $P \in A[X]$ is a gcd of its coefficients (defined up to a unit); $P$ is primitive if $c(P) \in A^\times$ . Every $P \in A[X]$ writes $P = c(P)\,P_1$ with $P_1$ primitive, and every $P \in K[X]\setminus\{0\}$ writes $P = \lambda P_1$ with $\lambda \in K^\times$ and $P_1 \in A[X]$ primitive (clear denominators, then factor out the content).

Lemma 2.23 (Gauss)

The product of two primitive polynomials of $A[X]$ is primitive; consequently $c(PQ) = c(P)c(Q)$ up to units.

Proof. Let $P, Q$ be primitive and suppose some irreducible (= prime, UFD) $p$ divides all coefficients of $PQ$ . Reduce modulo $p$ : in $(A/(p))[X]$ , $\bar P \bar Q = 0$ . But $A/(p)$ is a domain ( $(p)$ prime), so $(A/(p))[X]$ is a domain (leading coefficients multiply), forcing $\bar P = 0$ or $\bar Q = 0$ : $p$ divides all coefficients of $P$ or all of $Q$ , contradicting primitivity. For the consequence, write $P = c(P)P_1$ , $Q = c(Q)Q_1$ : $PQ = c(P)c(Q) P_1Q_1$ with $P_1Q_1$ primitive. ∎

Theorem 2.24

Let $A$ be a UFD with fraction field $K$ .

A primitive $P \in A[X]$ of degree $\geq 1$ is irreducible in $A[X]$ iff it is irreducible in $K[X]$ .
$A[X]$ is a UFD; its irreducibles are the irreducibles of $A$ and the primitive polynomials irreducible over $K$ . In particular $\Z[X]$ , and by induction $K[X_1, \dots, X_n]$ and $\Z[X_1, \dots, X_n]$ , are UFDs.

Proof. (1) ( $\Leftarrow$ ) If $P = QR$ in $A[X]$ with $Q, R$ nonunits, then neither factor is constant (a constant factor of a primitive polynomial is a unit), so the factorization is proper in $K[X]$ . ( $\Rightarrow$ ) Suppose $P = QR$ with $Q, R \in K[X]$ of degrees $\geq 1$ . Write $Q = \lambda Q_1$ , $R = \mu R_1$ with $Q_1, R_1 \in A[X]$ primitive: $P = \lambda\mu\, Q_1R_1$ , and $Q_1R_1$ is primitive by Gauss. Taking contents, $\lambda\mu \in A^\times$ (both sides have unit content; formally, $\lambda\mu = c(P) \in A^\times$ up to units, and in particular $\lambda \mu \in A$ ): $P = (\lambda\mu Q_1) R_1$ is a proper factorization in $A[X]$ .

(2) Existence: given $P \neq 0$ nonunit, factor $P = c(P)P_1$ , factor $c(P)$ into irreducibles of $A$ , and factor $P_1$ in the UFD $K[X]$ as $\prod Q_i$ with $Q_i \in K[X]$ irreducible; writing $Q_i = \lambda_i R_i$ with $R_i \in A[X]$ primitive (hence irreducible over $K$ , hence in $A[X]$ by (1)), the product $\prod \lambda_i$ is a unit of $A$ as before, and $P_1 = u\prod R_i$ . Uniqueness: compare a factorization’s constant part and polynomial part; the constants multiply to $c(P)$ (Gauss), unique by factoriality of $A$ ; the polynomial parts give two factorizations in $K[X]$ of the same polynomial, so they match up to constants of $K^\times$ (factoriality of $K[X]$ , Theorem 2.18), and matching primitive polynomials associated in $K[X]$ are associated in $A[X]$ : if $R = \lambda R'$ with $R, R'$ primitive and $\lambda \in K^\times$ , then taking contents forces $\lambda \in A^\times$ . ∎

Theorem 2.25 (Irreducibility criteria)

Let $A$ be a UFD, $K$ its fraction field, and $P = a_nX^n + \dots + a_0 \in A[X]$ primitive of degree $n \geq 1$ .

(Reduction) If $p \in A$ is prime, $p \nmid a_n$ , and the reduction $\bar P$ is irreducible in $(A/(p))[X]$ , then $P$ is irreducible in $K[X]$ (hence in $A[X]$ ).
(Eisenstein) If some prime $p$ satisfies $p \nmid a_n$ , $p \mid a_i$ for $0 \leq i < n$ , and $p^2 \nmid a_0$ , then $P$ is irreducible in $K[X]$ (hence in $A[X]$ ).

Proof. By Theorem 2.24(1), a proper factorization over $K$ yields $P = QR$ with $Q, R \in A[X]$ , $\deg Q, \deg R \geq 1$ (constants are excluded: they would be units or spoil primitivity).

(1) Reduce mod $p$ : $\bar P = \bar Q\bar R$ in $(A/(p))[X]$ . Since $p \nmid a_n$ and $\deg$ can only drop under reduction, $\deg \bar Q = \deg Q \geq 1$ and $\deg\bar R = \deg R \geq 1$ (their leading coefficients multiply to $\bar a_n \neq 0$ , so neither drops): $\bar P$ factors properly — contradiction.

(2) Reduce mod $p$ : $\bar Q \bar R = \bar P = \bar a_n X^n$ (all lower coefficients die). In the domain $(A/(p))[X]$ , the factorizations of $cX^n$ ( $c \ne 0$ ) are into constants and pure powers $c'X^k$ : indeed if $\bar Q\bar R = \bar a_nX^n$ , and say $\bar Q$ had a nonzero coefficient in degree $< \deg\bar Q$ , take lowest nonzero terms: $\operatorname{val}(\bar Q\bar R) = \operatorname{val}\bar Q + \operatorname{val}\bar R$ (domain), which must equal $n = \deg\bar Q + \deg\bar R$ , forcing $\operatorname{val} = \deg$ for both: both are monomials. As above, degrees do not drop, so $Q$ and $R$ have their constant terms $Q(0), R(0)$ divisible by $p$ — both, since both reductions are monomials of degree $\geq 1$ . Then $p^2 \mid Q(0)R(0) = a_0$ : contradiction. ∎

Example 2.26

$X^n - p$ is irreducible over $\Q$ for every prime $p$ and $n \geq 1$ (Eisenstein at $p$ ): there are irreducible polynomials of every degree over $\Q$ — in stark contrast with $\C$ (degree $1$ , d’Alembert–Gauss, proved in Chapter 16) and $\R$ (degrees $1, 2$ ). The trick of shifting enlarges Eisenstein’s reach: the $p$ -th cyclotomic polynomial $\Phi_p = X^{p-1} + \dots + X + 1 = \frac{X^p - 1}{X - 1}$ has

\Phi_p(X + 1) = \frac{(X+1)^p - 1}{X} = X^{p-1} + \binom{p}{1}X^{p-2} + \dots + \binom{p}{p-1},

Eisenstein at $p$ ( $p \mid \binom pk$ for $0 < k < p$ , and $\binom{p}{p-1} = p \not\equiv 0 \bmod p^2$ ): $\Phi_p(X+1)$ , hence $\Phi_p$ , is irreducible over $\Q$ . This is the algebraic heart of the $17$ -gon story told in Chapter 4.

Method 2.27

To prove $P \in \Z[X]$ irreducible over $\Q$ : (i) make $P$ primitive; (ii) try Eisenstein, on $P(X)$ and on shifts $P(X \pm 1)$ ; (iii) try reduction modulo small primes not dividing the leading coefficient — irreducibility mod one $p$ suffices, and over $\mathbb F_p$ irreducibility is a finite check (no roots excludes degree- $1$ factors; then test the finitely many factors of each degree $\leq \deg P/2$ ); (iv) if all else fails, undetermined coefficients. Beware: reducibility mod every $p$ does not imply reducibility over $\Q$ (Exercise 2.11).

2.4 Noetherian rings

Definition 2.28

A ring $A$ is Noetherian if every ideal of $A$ is finitely generated.

Proposition 2.29

$A$ is Noetherian iff every increasing sequence of ideals is eventually constant (ascending chain condition), iff every nonempty family of ideals has a maximal element (for inclusion).

Proof. (FG $\Rightarrow$ ACC): for a chain $I_1 \subseteq I_2 \subseteq \cdots$ , the union $I$ is an ideal, generated by $x_1, \dots, x_r$ ; all $x_i$ lie in some $I_N$ , so $I = I_N = I_n$ for $n \geq N$ . (ACC $\Rightarrow$ maximal elements): if a nonempty family $\mathcal F$ had no maximal element, pick $I_1 \in \mathcal F$ , then inductively $I_{n+1} \supsetneq I_n$ in $\mathcal F$ (possible since $I_n$ is not maximal): an infinite strictly increasing chain. (This uses the axiom of dependent choices, a weak form of choice we do not fuss over.) (Maximal elements $\Rightarrow$ FG): given an ideal $I$ , the family of finitely generated ideals contained in $I$ is nonempty ( $(0)$ ); a maximal element $J = (x_1, \dots, x_r)$ must equal $I$ : otherwise, adding $x \in I \setminus J$ to the generators produces a strictly bigger member of the family. ∎

Theorem 2.30 (Hilbert’s basis theorem)

If $A$ is Noetherian, so is $A[X]$ . Hence so are $A[X_1, \dots, X_n]$ , and every quotient of them.

Proof. Let $I$ be an ideal of $A[X]$ , and suppose $I$ is not finitely generated. Build a sequence: $f_1 \in I \setminus \{0\}$ of minimal degree, and inductively $f_{k+1} \in I \setminus (f_1, \dots, f_k)$ of minimal degree (the set is nonempty by assumption). Degrees $d_k = \deg f_k$ are nondecreasing (by minimality of each choice: $f_{k+1}$ was available at step $k+1$ ... precisely, $f_{k+1} \notin (f_1,\dots,f_k) \supseteq (f_1, \dots, f_{k-1})$ , so $f_{k+1}$ competed at step $k$ and lost or tied: $d_{k+1} \geq d_k$ ). Let $a_k \in A$ be the leading coefficient of $f_k$ . The chain of ideals $(a_1) \subseteq (a_1, a_2) \subseteq \cdots$ stabilizes: $a_{n+1} \in (a_1, \dots, a_n)$ for some $n$ , say $a_{n+1} = \sum_{k\leq n} u_k a_k$ . Consider

g = f_{n+1} - \sum_{k=1}^{n} u_k X^{\,d_{n+1} - d_k} f_k .

Then $g \in I \setminus (f_1, \dots, f_n)$ (the sum lies in the ideal, $f_{n+1}$ does not), yet the coefficient of degree $d_{n+1}$ cancels: $\deg g < d_{n+1}$ , contradicting the minimality of $d_{n+1} = \deg f_{n+1}$ .

Iterating, $A[X_1, \dots, X_n] = (A[X_1, \dots, X_{n-1}])[X_n]$ is Noetherian; a quotient $A/I$ is Noetherian because its ideals $J/I$ lift to ideals of $A$ (correspondence), where finitely many generators project onto generators. ∎

Remark 2.31

Noetherianity is the finiteness axiom of algebraic geometry: any system of polynomial equations in $n$ variables, however infinite, is equivalent to finitely many of them — its solution set is cut out by finitely many polynomials. PIDs are Noetherian (trivially); $\Z[X_1, X_2, \dots]$ in infinitely many variables is not ( $(X_1) \subsetneq (X_1, X_2) \subsetneq \cdots$ ). Non-Noetherian rings also occur naturally in analysis: continuous functions on $\intcc01$ form one (Exercise 2.10).

2.5 Exercises

Exercise 2.1 ★

Identify the quotients: (a) $\Z[X]/(X^2 + 1) \cong \Z[\iu]$ ; (b) $\R[X]/(X^2+1) \cong \C$ ; (c) $\mathbb F_2[X]/(X^2 + X + 1)$ is a field with $4$ elements — write its multiplication table.

Solution

Solution of Exercise 2.1.

(a) Evaluation $f \colon \Z[X] \to \Z[\iu]$ , $P \mapsto P(\iu)$ , is a surjective ring morphism ( $a + bX \mapsto a + b\iu$ ). Kernel: divide $P$ by the monic $X^2 + 1$ in $\Z[X]$ : $P = (X^2 + 1)Q + (bX + a)$ with $a, b \in \Z$ ; then $P(\iu) = a + b\iu = 0$ iff $a = b = 0$ . So $\ker f = (X^2+1)$ and Theorem 2.2 concludes.

(b) The same computation with $\R$ -coefficients: $\R[X]/(X^2+1) \cong \C$ — this is the cleanest construction of $\C$ .

(c) $X^2 + X + 1$ has no root in $\mathbb F_2$ ( $0, 1 \mapsto 1$ ), so, having degree $2$ , it is irreducible: the quotient $\mathbb F_4 = \mathbb F_2[X]/(X^2+X+1)$ is a field (Proposition 2.4; $(P)$ maximal in $K[X]$ when $P$ is irreducible, since $K[X]$ is a PID: an ideal $(D) \supseteq (P)$ means $D \mid P$ ). Its four elements are $0, 1, \omega, \omega + 1$ where $\omega = \bar X$ , with $\omega^2 = \omega + 1$ . Multiplication table (nonzero elements):

\omega \cdot \omega = \omega + 1, \qquad \omega(\omega + 1) = \omega^2 + \omega = 1, \qquad (\omega+1)^2 = \omega^2 + 1 = \omega .

The nonzero elements form a cyclic group of order $3$ generated by $\omega$ .

Exercise 2.2 ★

(a) Show that in a UFD, every irreducible element is prime. (b) Show that a finite integral domain is a field. (c) Deduce that in a finite ring, every prime ideal is maximal.

Solution

Solution of Exercise 2.2.

(a) Let $p$ be irreducible in a UFD and $p \mid ab$ , say $ab = pc$ , with $a, b \neq 0$ (else trivial). If $a$ or $b$ is a unit, $p$ divides the other. Otherwise factor $a$ , $b$ and $c$ into irreducibles: the two factorizations of $ab$ ,

(\text{factors of } a)(\text{factors of } b) = p \cdot (\text{factors of } c),

must agree up to order and associates: $p$ is an associate of some irreducible factor of $a$ or of $b$ , hence divides it.

(b) Let $A$ be a finite domain and $x \neq 0$ . The map $y \mapsto xy$ is injective ( $xy = xy' \Rightarrow x(y - y') = 0 \Rightarrow y = y'$ ), hence surjective ( $A$ finite): $1 = xy$ for some $y$ .

(c) If $\mathfrak p$ is prime in a finite ring $A$ , then $A/\mathfrak p$ is a finite domain, hence a field by (b), so $\mathfrak p$ is maximal (Proposition 2.4).

Exercise 2.3 ★

In $\Z[\iu\sqrt5]$ : check that $3$ , $1 + \iu\sqrt5$ and $1 - \iu\sqrt5$ are irreducible, that $9 = 3\cdot 3 = (2 + \iu\sqrt5)(2 - \iu\sqrt5)$ , and conclude again (after Proposition 2.12) that $\Z[\iu\sqrt5]$ is not a UFD. Where exactly does uniqueness fail?

Solution

Solution of Exercise 2.3.

Norms: $N(3) = 9$ , $N(1 \pm \iu\sqrt5) = 6$ , $N(2 \pm \iu\sqrt5) = 9$ . The equations $x^2 + 5y^2 = 2$ and $x^2 + 5y^2 = 3$ have no integer solutions, so no element has norm $2$ or $3$ . A proper factorization of $3$ would need two factors of norm $3$ : impossible — $3$ is irreducible. A proper factorization of $1 \pm \iu\sqrt5$ (norm $6$ ) would need factors of norms $2, 3$ : impossible. Same for $2 \pm \iu\sqrt5$ (norm $9$ : factors would have norm $3$ ). Now

9 = 3 \cdot 3 = (2 + \iu\sqrt5)(2 - \iu\sqrt5),

two factorizations into irreducibles. They are genuinely different: the units are $\pm 1$ (norm $1$ ), and $2 \pm \iu\sqrt5 \neq \pm 3$ . So uniqueness fails — while existence of factorizations holds in $\Z[\iu\sqrt5]$ (Exercise 2.10(c)): non-factoriality here is purely a uniqueness failure. (Consistently, Proposition 2.12: these irreducibles are not prime.)

Exercise 2.4 ★★

(a) Show that $\Z[\iu]$ is Euclidean for the norm $N(x + \iu y) = x^2 + y^2$ : given $a, b \neq 0$ , choose $q \in \Z[\iu]$ nearest to $a/b \in \C$ . (b) Determine $\Z[\iu]^\times$ . (c) Same questions for $\Z[\iu\sqrt2]$ and $N(x + \iu y\sqrt2) = x^2 + 2y^2$ . Why does the same argument fail for $\Z[\iu\sqrt5]$ ?

Solution

Solution of Exercise 2.4.

(a) Let $a, b \in \Z[\iu]$ , $b \neq 0$ , and $a/b = x + \iu y \in \C$ . Choose integers $m, n$ with $\abs{x - m} \leq \frac12$ , $\abs{y - n} \leq \frac12$ , and set $q = m + \iu n$ , $r = a - bq$ . Then

N(r) = N(b)\,\abs*{\tfrac ab - q}^2 \leq N(b)\Bigl(\tfrac14 + \tfrac14\Bigr) = \tfrac{N(b)}2 < N(b).

So $N$ is a Euclidean function ( $N(r) < N(b)$ or $r = 0$ ).

(b) If $uv = 1$ then $N(u)N(v) = 1$ with $N(u) \in \N$ : $N(u) = 1$ , i.e. $x^2 + y^2 = 1$ : $u \in \{\pm 1, \pm\iu\}$ ; conversely these are units.

(c) For $\Z[\iu\sqrt2]$ : the same rounding gives $\abs{a/b - q}^2 \leq \frac14 + \frac{2}4 = \frac34 < 1$ : Euclidean; units: $x^2 + 2y^2 = 1$ gives $\pm 1$ . For $\Z[\iu\sqrt5]$ the bound becomes $\frac14 + \frac54 = \frac32 > 1$ : the rounding argument fails — and must fail, since $\Z[\iu\sqrt5]$ is not even a UFD (Exercise 2.3), while Euclidean would imply UFD (Theorems 2.14 and 2.18).

Exercise 2.5 ★★

Let $A$ be a ring. (a) Show that if $x$ is nilpotent ( $x^n = 0$ for some $n$ ) then $1 + x \in A^\times$ . (b) Show that if $A$ is a domain, $A[X]^\times = A^\times$ ; give a counterexample over $\Z/4\Z$ . (c) Show that a domain has no idempotents ( $e^2 = e$ ) other than $0, 1$ , and none nilpotent other than $0$ .

Solution

Solution of Exercise 2.5.

(a) If $x^n = 0$ :

(1 + x)\bigl(1 - x + x^2 - \dots + (-1)^{n-1}x^{n-1}\bigr) = 1 + (-1)^{n-1}x^n = 1 .

(b) In a domain, $\deg(PQ) = \deg P + \deg Q$ ; $PQ = 1$ forces $\deg P = \deg Q = 0$ and $P, Q \in A^\times$ : $A[X]^\times = A^\times$ . Over $\Z/4\Z$ : $(1 + 2X)^2 = 1 + 4X + 4X^2 = 1$ , so $1 + 2X$ is a unit of degree $1$ (here $2$ is nilpotent; compare (a)).

(c) $e^2 = e$ gives $e(e - 1) = 0$ , so $e \in \{0, 1\}$ in a domain. If $x^n = 0$ with $n \geq 1$ minimal and $x \ne 0$ , then $n \geq 2$ and $x \cdot x^{n-1} = 0$ with both factors nonzero: contradiction.

Exercise 2.6 ★★

In $A = K[X, Y]$ : (a) show that the ideal $(X, Y)$ is maximal but not principal — so $K[X,Y]$ is a UFD (Theorem 2.24) that is not a PID; (b) identify $K[X, Y]/(Y - X^2)$ and $K[X,Y]/(XY - 1)$ as subrings of rational functions; (c) is $(Y - X^2)$ prime? maximal?

Solution

Solution of Exercise 2.6.

(a) $K[X,Y]/(X,Y) \cong K$ (evaluate at $(0,0)$ ): a field, so $(X,Y)$ is maximal. If $(X, Y) = (P)$ : $P \mid X$ forces (degrees in $Y$ ) $P \in K[X]$ , and $P \mid Y$ then forces $P \in K$ ; $P = 0$ is absurd and $P \in K^\times$ would give $(P) = K[X,Y]$ , contradicting properness ( $K[X,Y]/(X,Y) \cong K \neq 0$ ). So $(X,Y)$ is not principal.

(b) Evaluation $P(X, Y) \mapsto P(X, X^2)$ maps $K[X,Y]$ onto $K[X]$ ; its kernel is $(Y - X^2)$ : dividing by the monic-in- $Y$ polynomial $Y - X^2$ , $P = (Y - X^2)Q + R(X)$ , and $P(X, X^2) = R(X)$ . So $K[X,Y]/(Y - X^2) \cong K[X]$ — the coordinate ring of a parabola, isomorphic to a line’s.

Evaluation $P(X, Y) \mapsto P(X, X^{-1})$ maps $K[X, Y]$ onto the ring $K[X, X^{-1}]$ of Laurent polynomials. Its kernel contains $(XY - 1)$ ; conversely, modulo $XY - 1$ every class has a representative $R = \sum_{n \geq 0} a_nX^n + \sum_{m \geq 1} b_m Y^m$ (replace each product $XY$ by $1$ repeatedly), and $R(X, X^{-1}) = \sum a_n X^n + \sum b_m X^{-m} = 0$ forces all $a_n = b_m = 0$ . Hence $K[X, Y]/(XY - 1) \cong K[X, X^{-1}]$ — the coordinate ring of a hyperbola: the line with one point removed.

(c) $(Y - X^2)$ is prime (the quotient $K[X]$ is a domain) but not maximal ( $K[X]$ is not a field; concretely $(Y - X^2) \subsetneq (Y - X^2,\, X) \subsetneq K[X,Y]$ ).

Exercise 2.7 ★★

Irreducible or not over $\Q$ : $X^5 - 12X^3 + 36X - 12$ ; $X^4 + X + 1$ (reduce mod $2$ ); $X^4 + 4$ ; $\Phi_8 = X^4 + 1$ (shift by $1$ ); $X^3 - X - 1$ .

Solution

Solution of Exercise 2.7.

$X^5 - 12X^3 + 36X - 12$ : Eisenstein at $p = 3$ ( $3 \mid 12, 36, 12$ ; $9 \nmid 12$ ; $3 \nmid 1$ ): irreducible. (At $p = 2$ Eisenstein fails: $4 \mid 12$ .)

$X^4 + X + 1$ : reduce mod $2$ . No root in $\mathbb F_2$ ; the only irreducible quadratic over $\mathbb F_2$ is $X^2 + X + 1$ , and $(X^2+X+1)^2 = X^4 + X^2 + 1 \neq X^4 + X + 1$ . So $X^4 + X + 1$ is irreducible over $\mathbb F_2$ , hence over $\Q$ (Theorem 2.25(1); it is monic).

$X^4 + 4$ : reducible — the Sophie Germain identity, $X^4 + 4 = (X^2 - 2X + 2)(X^2 + 2X + 2)$ .

$X^4 + 1$ : shift, $(X+1)^4 + 1 = X^4 + 4X^3 + 6X^2 + 4X + 2$ : Eisenstein at $2$ . A factorization of $X^4+1$ would shift to one of $(X+1)^4 + 1$ : irreducible.

$X^3 - X - 1$ : a cubic is reducible over $\Q$ iff it has a rational root; a rational root of a monic integer polynomial is an integer dividing the constant term (rational root theorem: if $(p/q)$ in lowest terms is a root, $q \mid 1$ , $p \mid -1$ ), and $\pm 1$ are not roots ( $-1$ and $-1$ ): irreducible.

Exercise 2.8 ★★

(a) From Theorem 2.9, prove that Euler’s function is multiplicative on coprime arguments and that $\varphi(p^k) = p^{k-1}(p-1)$ ; recover $\varphi(n) = n\prod_{p \mid n}(1 - \frac1p)$ . (b) Solve: $x \equiv 2 \pmod 7$ , $x \equiv 5 \pmod{11}$ , $x \equiv 1 \pmod{13}$ , exhibiting the idempotents $e_k$ of the proof of Theorem 2.9.

Solution

Solution of Exercise 2.8.

(a) For $\gcd(m, n) = 1$ , Theorem 2.9 gives a ring isomorphism $\Z/mn\Z \cong \Z/m\Z \times \Z/n\Z$ . An element of a product ring is a unit iff both coordinates are, so $(\Z/mn\Z)^\times \cong (\Z/m\Z)^\times \times (\Z/n\Z)^\times$ and $\varphi(mn) = \varphi(m)\varphi(n)$ . For a prime power, the non-units of $\Z/p^k\Z$ are the classes of multiples of $p$ : $\varphi(p^k) = p^k - p^{k-1}$ . Hence

\varphi(n) = \prod_i \bigl(p_i^{\alpha_i} - p_i^{\alpha_i-1}\bigr) = n \prod_{p \mid n}\Bigl(1 - \frac1p\Bigr).

(b) $M = 7 \cdot 11 \cdot 13 = 1001$ . Idempotents: $e_1 \equiv (1, 0, 0)$ : $143 = 11\cdot13 \equiv 3 \pmod 7$ and $3 \cdot 5 \equiv 1$ : $e_1 = 143 \cdot 5 = 715$ . $e_2$ : $91 \equiv 3 \pmod{11}$ , $3 \cdot 4 \equiv 1$ : $e_2 = 91\cdot4 = 364$ . $e_3$ : $77 \equiv -1 \pmod{13}$ : $e_3 = 77 \cdot 12 = 924$ . Then

x \equiv 2\,e_1 + 5\,e_2 + 1\,e_3 = 1430 + 1820 + 924 = 4174 \equiv 170 \pmod{1001},

and indeed $170 = 24\cdot7 + 2 = 15\cdot11 + 5 = 13\cdot13 + 1$ .

Exercise 2.9 ★★★

(The nilradical) Let $\operatorname{Nil}(A)$ be the set of nilpotent elements. (a) Show that $\operatorname{Nil}(A)$ is an ideal contained in every prime ideal. (b) Conversely, let $a$ be non-nilpotent; using Zorn’s lemma on the ideals avoiding $S = \{a^n : n \in \N\}$ , produce a prime ideal not containing $a$ . Conclude:

\operatorname{Nil}(A) = \bigcap_{\mathfrak p \text{ prime}} \mathfrak p .

Solution

Solution of Exercise 2.9.

(a) If $x^n = 0$ and $y^m = 0$ , the binomial expansion of $(x+y)^{n+m}$ has every term $x^iy^j$ with $i + j = n + m$ , so $i \geq n$ or $j \geq m$ : each term vanishes, and $x + y$ is nilpotent; $(ax)^n = a^nx^n = 0$ : $\operatorname{Nil}(A)$ is an ideal. If $\mathfrak p$ is prime and $x^n = 0 \in \mathfrak p$ , induction on $n$ gives $x \in \mathfrak p$ ( $x \cdot x^{n-1} \in \mathfrak p$ ).

(b) Let $a \notin \operatorname{Nil}(A)$ and $S = \{a^n : n \geq 1\}$ , so $0 \notin S$ . The set $\mathcal E$ of ideals disjoint from $S$ contains $(0)$ and is inductive (the union of a chain of ideals disjoint from $S$ is an ideal disjoint from $S$ ): Zorn provides $\mathfrak p \in \mathcal E$ maximal. $\mathfrak p$ is proper ( $a \notin \mathfrak p$ , since $a \in S$ ). Primality: let $x, y \notin \mathfrak p$ . By maximality, $\mathfrak p + (x)$ and $\mathfrak p + (y)$ meet $S$ : $a^m \in \mathfrak p + (x)$ , $a^n \in \mathfrak p + (y)$ . Multiplying, $a^{m+n} \in \mathfrak p + (xy)$ . If $xy \in \mathfrak p$ , then $a^{m+n} \in \mathfrak p \cap S$ : absurd. So $xy \notin \mathfrak p$ — contrapositive of primality. Hence every non-nilpotent element avoids some prime ideal; with (a), $\operatorname{Nil}(A) = \bigcap_{\mathfrak p} \mathfrak p$ .

Exercise 2.10 ★★★

(a) Let $A$ be Noetherian and $f \colon A \to A$ a surjective ring morphism. Show that $f$ is injective. (Consider $\ker f \subseteq \ker f^2 \subseteq \cdots$ .) (b) Show that the ring $\mathcal C(\intcc01, \R)$ of continuous functions is not Noetherian. (Consider $I_n = \{f : f = 0 \text{ on } \intcc0{1/n}\}$ .) (c) Show that in a Noetherian domain, every nonzero nonunit is a (finite) product of irreducibles — so non-factoriality of $\Z[\iu\sqrt 5]$ is a failure of uniqueness only.

Solution

Solution of Exercise 2.10.

(a) The chain $\ker f \subseteq \ker f^2 \subseteq \cdots$ stabilizes (Proposition 2.29): $\ker f^n = \ker f^{n+1}$ for some $n$ . Let $x \in \ker f$ . As $f$ , hence $f^n$ , is surjective, $x = f^n(y)$ for some $y$ ; then $f^{n+1}(y) = f(x) = 0$ , so $y \in \ker f^{n+1} = \ker f^n$ , i.e. $x = f^n(y) = 0$ .

(b) $I_n = \{f \in \mathcal C(\intcc01, \R) : f\restriction_{ \intcc0{1/n}} = 0\}$ is an ideal, and $I_n \subseteq I_{n+1}$ . The inclusion is strict: $x \mapsto \max\bigl(0, x - \frac1{n+1}\bigr)$ vanishes on $\intcc0{\frac1{n+1}}$ but not on $\intcc0{\frac1n}$ . An infinite strictly increasing chain contradicts Proposition 2.29.

(c) Suppose the set of nonzero nonunits admitting no factorization into irreducibles is nonempty. The corresponding family of ideals $\{(a)\}$ has a maximal element $(a)$ (Proposition 2.29). The element $a$ is not irreducible (an irreducible is its own factorization), so $a = bc$ with $b, c$ nonunits; $(a) \subseteq (b)$ is strict (as $(a) = (b)$ would give $b = ad$ , $a = adc$ , so $dc = 1$ : $c$ a unit), likewise $(a) \subsetneq (c)$ . By maximality, $b$ and $c$ both factor into irreducibles; concatenating factors $a$ : contradiction. Applied to $\Z[\iu\sqrt5]$ — Noetherian as a quotient of $\Z[X]$ (Theorem 2.30, $\Z[\iu\sqrt5] \cong \Z[X]/(X^2+5)$ ) — this shows factorizations exist there; Exercise 2.3 showed uniqueness is what fails.

Exercise 2.11 ★★★

Let $P = X^4 + 1$ . (a) Show that $P$ is irreducible over $\Q$ (Exercise 2.7). (b) Show that $P$ is reducible modulo every prime $p$ : treat $p = 2$ ; then, for odd $p$ , show that $8 \mid p^2 - 1$ and admit for now (proved in Chapter 4) that the multiplicative group of the field with $p^2$ elements is cyclic, to conclude that $P$ splits into two quadratic factors mod $p$ ; make them explicit when one of $-1$ , $2$ , $-2$ is a square mod $p$ , and show one of them always is.

Solution

Solution of Exercise 2.11.

(a) Exercise 2.7: shift and Eisenstein at $2$ .

(b) Mod $2$ : $X^4 + 1 = (X + 1)^4$ . Now let $p$ be odd. The squares form a subgroup of index $2$ in $(\Z/p\Z)^\times$ : the morphism $x \mapsto x^2$ has kernel $\{\pm 1\}$ (two elements: $X^2 - 1$ has at most $2$ roots in a field, and $1 \neq -1$ for odd $p$ ), so its image has $\frac{p-1}2$ elements. Consequently, the product of two non-squares is a square (in the order- $2$ quotient group, $\overline{xy} = \bar x\bar y$ ). Hence at least one of $-1$ , $2$ , $-2$ is a square mod $p$ (if $-1$ and $2$ are not, $-2 = (-1)\cdot 2$ is). In each case $X^4 + 1$ factors mod $p$ :

$-1 = c^2$ : $X^4 + 1 = X^4 - c^2 = (X^2 - c)(X^2 + c)$ ;
$2 = c^2$ : $(X^2 + cX + 1)(X^2 - cX + 1) = X^4 + (2 - c^2)X^2 + 1 = X^4 + 1$ ;
$-2 = c^2$ : $(X^2 + cX - 1)(X^2 - cX - 1) = X^4 - (c^2 + 2)X^2 + 1 = X^4 + 1$ .

So $X^4+1$ is reducible modulo every prime, yet irreducible over $\Q$ : the reduction criterion (Theorem 2.25(1)) detects irreducibility but its failure proves nothing.

(For the structural reason: $p^2 - 1 = (p-1)(p+1)$ is a product of two consecutive even numbers, so $8 \mid p^2 - 1$ ; the cyclic group $\mathbb F_{p^2}^\times$ (cyclicity proved in Chapter 4) then contains an element $\zeta$ of order $8$ , a root of $X^4 + 1$ ; its minimal polynomial over $\mathbb F_p$ divides $X^4+1$ and has degree $\leq 2$ — $X^4+1$ can never be irreducible mod $p$ .)

Exercise 2.12 ★★

(Idempotents split rings) An element $e$ of a commutative ring $A$ is idempotent if $e^2 = e$ . (a) Show that if $e$ is idempotent, so is $1 - e$ , and that the map $x \mapsto (ex, (1-e)x)$ is a ring isomorphism $A \cong Ae \times A(1-e)$ , where $Ae$ is a ring with unit $e$ . (b) Find all idempotents of a domain, and of $\Z/12\Z$ ; exhibit the isomorphism $\Z/12\Z \cong \Z/4\Z \times \Z/3\Z$ by naming its two nontrivial idempotents. (c) Show that the CRT decomposition of $\Z/n\Z$ (Example 2.10) corresponds exactly to the idempotents $e_i \equiv 1 \bmod p_i^{a_i}$ , $e_i \equiv 0$ modulo the other prime powers: rings decompose along their idempotents as spaces decompose along projections.

Solution

Solution of Exercise 2.12.

(a) $(1-e)^2 = 1 - 2e + e^2 = 1 - e$ . The map $\varphi(x) = (ex, (1-e)x)$ is additive and multiplicative into the product of the two ideals: $exey = e^2xy = e(xy)$ , and $Ae$ is a commutative ring with unit $e$ ( $e\cdot ex = ex$ ). Injective: $ex = 0$ and $(1-e)x = 0$ sum to $x = 0$ . Surjective: $(ea, (1-e)b)$ is the image of $ea + (1-e)b$ (compute both components using $e(1-e) = 0$ ). Units map to $(1, 0)$ -style pairs correctly: $\varphi(1) = (e, 1-e)$ , the unit of the product.

(b) In a domain, $e(e - 1) = 0$ forces $e \in \{0, 1\}$ : only trivial idempotents. In $\Z/12\Z$ , solving $e^2 \equiv e$ : $e \in \{0, 1, 4, 9\}$ . The nontrivial pair $\{4, 9\}$ : $4 + 9 = 13 \equiv 1$ , $4\cdot9 = 36 \equiv 0$ , and $\Z/12\Z\cdot4 = \{0, 4, 8\} \cong \Z/3\Z$ (unit $4$ ), $\Z/12\Z\cdot9 = \{0, 3, 6, 9\} \cong \Z/4\Z$ (unit $9$ ): the CRT splitting $\Z/12\Z \cong \Z/4\Z\times\Z/3\Z$ , with $9 \leftrightarrow (1, 0)$ and $4 \leftrightarrow (0, 1)$ .

(c) Under the CRT isomorphism $\Z/n\Z \cong \prod_i \Z/p_i^{a_i}\Z$ , the element $e_i$ with the stated congruences corresponds to the tuple with $1$ in slot $i$ and $0$ elsewhere: the elementary idempotents of the product. Conversely a complete family of orthogonal idempotents ( $e_ie_j = 0$ for $i \neq j$ , $\sum e_i = 1$ ) reassembles the product decomposition by (a), inductively. Idempotents are to rings what orthogonal projections are to Hilbert spaces (Chapter 13): the coordinates of an internal direct decomposition.

2.6 Problem: Fermat’s two-squares theorem

Problem 2.1

Weekend problem — sums of two squares, via $\Z[\iu]$

Which integers are sums of two squares? Fermat’s answer (1640) is one of arithmetic’s gems; the Gaussian integers turn its proof into ring theory. Throughout, $N(x + \iu y) = x^2 + y^2$ denotes the norm, $\Z[\iu]$ is Euclidean (Exercise 2.4), hence a PID and a UFD, and Gaussian prime means prime (= irreducible) element of $\Z[\iu]$ .

Part I — Norms and Gaussian primes.

Verify $N(zw) = N(z)N(w)$ , deduce again $\Z[\iu]^\times = \{\pm1, \pm\iu\}$ , and prove the Brahmagupta identity: a product of two sums of two squares is a sum of two squares.
Show that if $N(z)$ is a prime number, then $z$ is a Gaussian prime.
Show that every Gaussian prime $\pi$ divides exactly one prime number $p$ (consider $N(\pi) = \pi\bar\pi$ ), and that then $N(\pi) \in \{p, p^2\}$ .
Deduce the dichotomy: for each prime $p$ , either $p$ stays prime in $\Z[\iu]$ (and no Gaussian prime of norm $p$ exists), or $p = \pi\bar\pi$ with $\pi$ a Gaussian prime of norm $p$ — and then $p = a^2 + b^2$ .

Part II — Wilson’s theorem and $-1$ modulo $p$ .

Prove Wilson’s theorem: for $p$ prime, $(p-1)! \equiv -1 \pmod p$ . (Pair each residue with its inverse; which ones are self-paired?)
Let $p$ be an odd prime and $m = \frac{p-1}2$ . Show that $(m!)^2 \equiv (-1)^{m+1} \pmod p$ (in $(p-1)!$ , replace each factor $k > m$ by $-(p - k)$ ).
Conclude: $-1$ is a square modulo $p$ iff $p = 2$ or $p \equiv 1 \pmod 4$ . (For the “only if”: if $x^2 \equiv -1$ , what is the order of $x$ in $(\Z/p\Z)^\times$ , and what does Lagrange say?)

Part III — The splitting law.

Let $p \equiv 1 \pmod 4$ , and $x$ with $p \mid x^2 + 1 = (x + \iu)(x - \iu)$ . Show that $p$ is not a Gaussian prime, and conclude with Part I: $p = a^2 + b^2$ .
Let $p \equiv 3 \pmod 4$ . Show directly that $p$ is not a sum of two squares (squares mod $4$ ), and deduce that $p$ stays a Gaussian prime.
Settle $p = 2$ : exhibit the factorization $2 = -\iu(1+\iu)^2$ and check that $1 + \iu$ is a Gaussian prime. ( $2$ is the unique ramified prime: divisible by the square of a Gaussian prime up to a unit.)
Assemble the classification of Gaussian primes, up to units: $1 + \iu$ ; the integers $p \equiv 3 \pmod 4$ ; the conjugate pairs $\pi, \bar\pi$ of norm $p \equiv 1 \pmod 4$ . Verify it on $5 = (2+\iu)(2-\iu)$ and on $3$ .

Part IV — The two-squares theorem.

Prove the direct half: if in the factorization $n = \prod p_i^{\alpha_i}$ every prime $\equiv 3 \pmod 4$ appears with an even exponent, then $n$ is a sum of two squares. (Brahmagupta + Parts II–III.)
Prove the converse: if $n = a^2 + b^2 = N(a + \iu b)$ and $q \equiv 3 \pmod 4$ divides $n$ , show that $q$ , a Gaussian prime, divides $a + \iu b$ or $a - \iu b$ , that it in fact divides both $a$ and $b$ , and conclude by induction on $n$ that the exponent of $q$ in $n$ is even.
State the final theorem. Which of $2025$ , $2026$ , $2027$ are sums of two squares? ( $2025 = 81 \cdot 25$ ; $2026 = 2 \cdot 1013$ , $1013$ prime; $2027$ prime.)
(Epilogue) Show that a prime $p \equiv 1 \pmod 4$ is a sum of two squares in an essentially unique way: if $p = a^2 + b^2 = c^2 + d^2$ (positive integers), then $\{a, b\} = \{c, d\}$ . (Uniqueness of factorization in $\Z[\iu]$ .)

Part V — Counting representations: Jacobi’s formula and Leibniz’s series. Write $r_2(n) = \#\{(a, b) \in \Z^2 : a^2 + b^2 = n\}$ (ordered pairs, signs and zeros included), and let $\chi$ be the nontrivial character mod $4$ : $\chi(d) = +1$ if $d \equiv 1$ , $-1$ if $d \equiv 3 \pmod4$ , $0$ if $d$ even.

(Warm-up, by contrast) Which integers are differences of two squares? Show: $n = a^2 - b^2$ with $a, b \in \Z$ iff $n \not\equiv 2 \pmod 4$ — no ring theory needed, and no structure comparable to what follows.
Show that $r_2(n)$ is the number of $z \in \Z[\iu]$ with $N(z) = n$ . Writing $n = 2^{a}\prod_jp_j^{b_j} \prod_kq_k^{c_k}$ with $p_j \equiv 1$ , $q_k \equiv 3 \pmod4$ , use the classification of question 11 and unique factorization to show: such $z$ exist iff all $c_k$ are even, and in that case

$r_2(n) = 4\prod_j\,(b_j + 1) .$

(Count: $z = u\,(1+\iu)^{a}\prod_j\pi_j^{s_j} \bar\pi_j^{\,b_j - s_j}\prod_kq_k^{c_k/2}$ with $u$ a unit and $0 \leq s_j \leq b_j$ ; why is this list exhaustive and repetition-free?)
Show that $d \mapsto \chi(d)$ is completely multiplicative, deduce that $n \mapsto \sum_{d \mid n}\chi(d)$ is multiplicative, and compute it on prime powers: it equals $1$ on $2^a$ ; $b + 1$ on $p^b$ ( $p \equiv 1$ ); $1$ or $0$ on $q^c$ ( $q \equiv 3$ ) according as $c$ is even or odd.
Conclude Jacobi’s theorem:

$r_2(n) = 4\sum_{d \mid n}\chi(d) = 4\bigl(d_1(n) - d_3(n)\bigr),$

where $d_i(n)$ counts the divisors $\equiv i \pmod 4$ . Verify on $n = 3, 5, 9, 25$ , and list the $16$ representations of $65$ .
(The circle) Show that $\sum_{n \leq x}r_2(n)$ is the number of lattice points of $\Z^2$ in the closed disc of radius $\sqrt x$ , and prove

$\sum_{n\leq x}r_2(n) = \pi x + O(\sqrt x)$

(each lattice point owns a unit square; compare areas, the error living in an annulus of width $O(1)$ ).
(Leibniz, read arithmetically) Combine questions 19–20:

$\sum_{d \leq x}\chi(d)\Bigl\lfloor\frac xd\Bigr\rfloor = \frac{\pi x}4 + O(\sqrt x),$

and deduce — removing the floors carefully — Leibniz’s series

$1 - \frac13 + \frac15 - \frac17 + \dots = \frac\pi4 .$

The alternating series of odd reciprocals is the average excess of divisors $\equiv 1$ over divisors $\equiv 3$ : analysis computed by arithmetic.
(How rare are sums of two squares?) Show that no integer $\equiv 3 \pmod 4$ is a sum of two squares (two ways: squares mod $4$ , or the parity criterion of question 17), so at least a quarter of all integers are missed; and show that the average $\frac1x\sum_{n\leq x}r_2(n) \to \pi$ of question 20 is compatible with representable integers having density $0$ — exhibit integers with abnormally many representations (take products of many primes $\equiv 1 \bmod 4$ ) to explain how a vanishing proportion can still carry a positive average. (Landau proved the true density decays like $1/\sqrt{\log x}$ ; that is beyond our tools, but the mechanism is now visible.)

Part VI — Complements: primitive representations and Pythagoras.

Call a representation $n = a^2 + b^2$ primitive if $\gcd(a, b) = 1$ . Show that $n \geq 1$ admits a primitive representation iff $4 \nmid n$ and no prime $q \equiv 3 \pmod 4$ divides $n$ . (For the necessity, reuse the descent of question 13 and squares mod $4$ ; for the sufficiency, build $z$ from $1 + \iu$ and the $\pi_j$ only — no conjugates — and explain why a common prime factor of $a$ and $b$ would force both $\pi_j$ and $\bar\pi_j$ , or $(1+\iu)^2$ , into $z$ .)
(Pythagorean triples) Let $a^2 + b^2 = c^2$ with $a, b, c$ positive, $\gcd(a, b) = 1$ and $b$ even. Show that $a + \iu b$ and $a - \iu b$ are coprime in $\Z[\iu]$ (a common Gaussian prime divisor would divide $2a$ and $2b$ , and $c$ is odd), deduce from unique factorization that $a + \iu b = u(m + \iu n)^2$ for a unit $u$ , and conclude the classical parametrization: up to swapping $a$ and $b$ ,

$a = m^2 - n^2, \qquad b = 2mn, \qquad c = m^2 + n^2,$

with $m > n \geq 1$ coprime of opposite parities. Recover $(3, 4, 5)$ and $(21, 20, 29)$ from $(m, n) = (2, 1)$ and $(5, 2)$ .
(Numerical verification) Take $x = 25$ . Compute $r_2(n)$ for $1 \leq n \leq 25$ from Jacobi’s formula, check that the nonzero values occur exactly at $n = 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25$ , and that

$\sum_{n \leq 25} r_2(n) = 80 = 4\sum_{d \leq 25}\chi(d) \Bigl\lfloor\frac{25}d\Bigr\rfloor .$

Verify that the closed disc of radius $5$ contains $81$ lattice points, and compare with $\pi x \approx 78.5$ : the error is well within the $O(\sqrt x)$ of question 20.

Solution

Solution of Problem 2.1.

1. $N(z) = z\bar z$ , so $N(zw) = zw\overline{zw} = z\bar z\, w \bar w = N(z)N(w)$ . If $uv = 1$ : $N(u)N(v) = 1$ in $\N$ , so $N(u) = 1$ , i.e. $u \in \{\pm 1, \pm \iu\}$ ; all four are units. Brahmagupta: $(a^2+b^2)(c^2+d^2) = N\bigl((a + \iu b)(c + \iu d)\bigr) = (ac - bd)^2 + (ad + bc)^2$ .

2. If $z = ab$ , then $N(z) = N(a)N(b)$ is prime, so $N(a) = 1$ or $N(b) = 1$ : one factor is a unit. As $N(z) > 1$ , $z$ is neither zero nor a unit: irreducible — and prime, since $\Z[\iu]$ is a UFD (Theorem 2.14, Theorem 2.18 and Lemma 2.17).

3. $\pi$ divides $N(\pi) = \pi\bar\pi \geq 2$ , an integer; factoring $N(\pi)$ into prime numbers and using that $\pi$ is prime, $\pi \mid p$ for some prime number $p$ . If also $\pi \mid q \neq p$ : Bézout in $\Z$ gives $1 = up + vq$ , so $\pi \mid 1$ — absurd: $p$ is unique. From $p = \pi\gamma$ : $p^2 = N(p) = N(\pi)N(\gamma)$ with $N(\pi) \neq 1$ , so $N(\pi) \in \{p, p^2\}$ .

4. Let $\pi$ be a Gaussian prime dividing $p$ , $p = \pi\gamma$ . If $N(\pi) = p^2$ : $N(\gamma) = 1$ , so $p$ is an associate of $\pi$ , itself a Gaussian prime; and no Gaussian prime has norm $p$ (if $N(\rho) = p$ then $\rho \mid \rho\bar\rho = p$ , and $p$ prime in $\Z[\iu]$ would force $\rho$ associate to $p$ , giving $N(\rho) = N(p) = p^2 \neq p$ ). If $N(\pi) = p$ : writing $\pi = a + \iu b$ , $p = \pi\bar\pi = a^2 + b^2$ .

5. In the abelian group $(\Z/p\Z)^\times$ , pair each element with its inverse. The self-inverse elements are the roots of $X^2 - 1$ : exactly $\pm 1$ (at most two roots in a field). The product of all elements is then $1 \cdot (-1) \cdot \prod (\text{pairs } k k^{-1}) = -1$ : $(p-1)! \equiv -1 \pmod p$ . (For $p = 2$ : $1! \equiv -1$ .)

6. Write $(p-1)! = \prod_{k=1}^m k \cdot \prod_{k=m+1}^{p-1}k$ with $m = \frac{p-1}2$ . In the second product substitute $k = p - j$ , $j = 1, \dots, m$ : modulo $p$ , $\prod_{j=1}^m (p - j) \equiv (-1)^m m!$ . Hence $-1 \equiv (-1)^m (m!)^2$ , i.e. $(m!)^2 \equiv (-1)^{m+1} \pmod p$ .

7. If $p \equiv 1 \pmod 4$ , $m$ is even and question 6 gives $(m!)^2 \equiv -1$ : a square root of $-1$ . Conversely, if $x^2 \equiv -1 \pmod p$ ( $p$ odd), then $x^4 = 1 \neq x^2$ : $x$ has order $4$ in $(\Z/p\Z)^\times$ , so $4 \mid p - 1$ (Lagrange). And $p = 2$ : $1^2 = 1 \equiv -1$ . Conclusion: $-1$ is a square mod $p$ iff $p = 2$ or $p \equiv 1 \pmod 4$ .

8. With $x^2 \equiv -1$ : $p \mid x^2 + 1 = (x + \iu)(x - \iu)$ . If $p$ were a Gaussian prime it would divide a factor; but $\frac xp \pm \frac \iu p \notin \Z[\iu]$ . So $p$ is not a Gaussian prime; by the dichotomy (question 4) — $p$ not prime means the second branch — $p = a^2 + b^2$ .

9. Squares are $\equiv 0$ or $1 \pmod 4$ , so $a^2 + b^2 \in \{0, 1, 2\} \pmod 4$ : a prime $p \equiv 3 \pmod 4$ is not a sum of two squares. By question 4, the branch $N(\pi) = p$ ( $p = a^2+b^2$ ) is impossible: $p$ stays a Gaussian prime.

10. $(1 + \iu)^2 = 2\iu$ , so $2 = -\iu(1 + \iu)^2$ ; and $N(1 + \iu) = 2$ is prime, so $1 + \iu$ is a Gaussian prime (question 2).

11. Every Gaussian prime divides exactly one prime number $p$ (question 3); listing by cases: $p = 2$ gives the associates of $1 + \iu$ ; $p \equiv 3 \pmod 4$ gives $p$ itself (question 9); $p \equiv 1 \pmod 4$ gives the pair $\pi, \bar\pi$ of norm $p$ (questions 4 and 8). The pair is genuine: $\bar\pi \in \{\pm\pi, \pm\iu\pi\}$ would force, writing $\pi = a + \iu b$ , either $b = 0$ , $a = 0$ , or $a = \pm b$ , giving $p = a^2 + b^2 \in \{a^2, 2a^2\}$ — impossible for an odd prime. Check: $5 = (2 + \iu)(2 - \iu)$ , $N(2\pm\iu) = 5$ ; $3$ : prime of norm $9$ .

12. Write $n = 2^{\alpha}\prod_i p_i^{\beta_i} \prod_j q_j^{2\gamma_j}$ with $p_i \equiv 1$ , $q_j \equiv 3 \pmod 4$ . Each factor is a sum of two squares: $2 = 1^2 + 1^2$ ; $p_i = a^2 + b^2$ (question 8); $q_j^{2\gamma_j} = (q_j^{\gamma_j})^2 + 0^2$ . The Brahmagupta identity (question 1) propagates the property to the product $n$ .

13. Let $n = a^2 + b^2 = N(a + \iu b)$ and $q \equiv 3 \pmod 4$ , $q \mid n$ . The Gaussian prime $q$ (question 9) divides $(a + \iu b)(a - \iu b)$ , hence one of the two factors — say $q \mid a + \iu b$ (the other case is identical). But then $\frac{a + \iu b}{q} = \frac aq + \iu \frac bq \in \Z[\iu]$ reads off as $q \mid a$ and $q \mid b$ in $\Z$ . Hence $q^2 \mid n$ and $\frac n{q^2} = \bigl(\frac aq\bigr)^2 + \bigl(\frac bq\bigr)^2$ . By strong induction on $n$ , the exponent of $q$ in $n/q^2$ is even; that of $n$ is even too.

14. Theorem (Fermat). A positive integer is a sum of two squares if and only if every prime $\equiv 3 \pmod 4$ occurs in it with an even exponent. — $2025 = 3^4 \cdot 5^2$ : exponent of $3$ even, yes ( $2025 = 45^2 + 0^2 = 27^2 + 36^2$ ). $2026 = 2 \cdot 1013$ with $1013 \equiv 1 \pmod 4$ prime: yes ( $1013 = 22^2 + 23^2$ , and Brahmagupta with $2 = 1^2+1^2$ : $2026 = (22 - 23)^2 + (22 + 23)^2 = 1^2 + 45^2$ ). $2027$ is a prime $\equiv 3 \pmod 4$ : no.

15. Let $p = a^2 + b^2 = c^2 + d^2$ with positive integers, $p \equiv 1 \pmod 4$ , and $\pi$ a Gaussian prime with $p = \pi\bar\pi$ (question 4). Both $a + \iu b$ and $c + \iu d$ have norm $p$ , hence are Gaussian primes (question 2) dividing $p = (a+\iu b)(a - \iu b)$ ; by uniqueness of factorization, $c + \iu d$ is an associate of $a + \iu b$ or of $a - \iu b$ :

c + \iu d \in \{\pm(a \pm \iu b),\ \pm\iu(a \pm \iu b)\} = \{\pm a \pm \iu b,\ \pm b \pm \iu a\}.

Positivity of $c, d$ leaves $c + \iu d \in \{a + \iu b, b + \iu a\}$ : $\{c, d\} = \{a, b\}$ .

16. If $n = a^2 - b^2 = (a-b)(a+b)$ : the two factors have the same parity, so $n$ is odd (both odd) or divisible by $4$ (both even) — never $\equiv 2 \pmod 4$ . Conversely, $n$ odd: $n = \bigl(\frac{n+1}2\bigr)^2 - \bigl(\frac{n-1}2\bigr)^2$ ; $n = 4m$ : $n = (m+1)^2 - (m-1)^2$ . The answer is a bare congruence condition, with a one-line identity behind it: differences of squares carry no arithmetic depth, and the contrast with sums is the whole point of this problem.

17. $(a, b) \mapsto z = a + \iu b$ is a bijection between representations and $\{z : N(z) = n\}$ . Factor $z$ in the UFD $\Z[\iu]$ using the classification (question 11): up to a unit, $z = (1+\iu)^{a'}\prod_j\pi_j^{s_j}\bar\pi_j^{t_j} \prod_kq_k^{u_k}$ , and taking norms ( $N(1+\iu) = 2$ , $N(\pi_j) = N(\bar\pi_j) = p_j$ , $N(q_k) = q_k^2$ ):

n = 2^{a'}\prod_jp_j^{s_j + t_j}\prod_kq_k^{2u_k} .

Matching exponents: $a' = a$ , $s_j + t_j = b_j$ , $2u_k = c_k$ — solvable iff every $c_k$ is even, and then $u_k = c_k/2$ is forced while $s_j \in \intint0{b_j}$ is free. Distinct data $(u, (s_j))$ give non-associate $z$ ’s with the same norm; the unit $u \in \{\pm1, \pm\iu\}$ (4 choices) then enumerates each associate class without repetition (two equal products would violate uniqueness of factorization — $\pi_j$ and $\bar\pi_j$ are non-associate since $p_j = \pi_j\bar\pi_j$ is not ramified). Total: $r_2(n) = 4\prod_j(b_j + 1)$ , and $0$ if some $c_k$ is odd.

18. $\chi(dd') = \chi(d)\chi(d')$ is checked mod $4$ (odd $\times$ odd covers the four sign cases; anything even gives $0 = 0$ ). For coprime $m, n$ , divisors of $mn$ are uniquely $d = d_1d_2$ with $d_1 \mid m$ , $d_2 \mid n$ : $\sum_{d \mid mn}\chi(d) = \bigl(\sum_{d_1\mid m}\chi(d_1)\bigr)\bigl(\sum_{d_2\mid n}\chi(d_2)\bigr)$ : multiplicative. Prime powers: on $2^a$ , only $d = 1$ is odd: sum $= 1$ . On $p^b$ with $p \equiv 1$ : all $\chi(p^i) = 1$ , sum $= b + 1$ . On $q^c$ with $q \equiv 3$ : $\chi(q^i) = (-1)^i$ , alternating sum $= 1$ ( $c$ even) or $0$ ( $c$ odd).

19. The two multiplicative functions $\frac14r_2$ (question 17) and $\sum_{d\mid n}\chi(d)$ (question 18) agree on all prime powers — $1$ on $2^a$ ; $b + 1$ on $p^b$ ; $\mathbf 1_{c\ \mathrm{even}}$ on $q^c$ — hence agree everywhere: Jacobi’s formula, with $\sum_{d\mid n}\chi(d) = d_1(n) - d_3(n)$ by sorting divisors. Checks: $r_2(3) = 0 = 4(1 - 1)$ ; $r_2(5) = 8 = 4(2 - 0)$ ( $(\pm1,\pm2), (\pm2,\pm1)$ ); $r_2(9) = 4 = 4(2 - 1)$ (divisors $1, 9 \equiv 1$ ; $3 \equiv 3$ ; representations $(\pm3, 0), (0, \pm3)$ ); $r_2(25) = 12 = 4(3 - 0)$ . For $65 = 5\cdot13$ : $r_2 = 4\cdot2\cdot2 = 16$ , from $65 = 1 + 64 = 16 + 49$ : the sixteen pairs $(\pm1, \pm8), (\pm8, \pm1), (\pm4, \pm7), (\pm7, \pm4)$ .

20. $\sum_{n \leq x}r_2(n)$ counts the pairs $(a, b)$ with $0 < a^2 + b^2 \leq x$ , i.e. the lattice points of the closed disc $D_{\sqrt x}$ minus the origin. Assign to each lattice point $P$ the unit square $P + \intco01^2$ : these squares tile the plane. Every square attached to a point of $D_{\sqrt x}$ lies in $D_{\sqrt x + \sqrt2}$ , and every square meeting $D_{\sqrt x - \sqrt 2}$ is attached to a point of $D_{\sqrt x}$ (the square has diameter $\sqrt 2$ ): comparing areas,

\pi(\sqrt x - \sqrt2)^2 \leq \#\{\text{lattice points in } D_{\sqrt x}\} \leq \pi(\sqrt x + \sqrt 2)^2,

and both bounds are $\pi x + O(\sqrt x)$ . Subtracting the origin changes nothing at this precision.

21. By Jacobi (question 19) and exchanging the order of summation ( $n = dm$ ):

\frac14\sum_{n\leq x}r_2(n) = \sum_{n \leq x}\sum_{d \mid n}\chi(d) = \sum_{d \leq x}\chi(d)\,\#\{m : dm \leq x\} = \sum_{d\leq x}\chi(d)\Bigl\lfloor\frac xd\Bigr\rfloor,

which is $\frac{\pi x}4 + O(\sqrt x)$ by question 20. Remove the floors: $\lfloor x/d\rfloor = x/d + O(1)$ , but summing $O(1)$ over $d \leq x$ is too crude; instead use that the partial sums of $\chi$ are bounded ( $0, 1, 1, 0$ cyclically), so by Abel summation $\sum_{d\leq x}\chi(d)\{x/d\}$ , whose terms we group in pairs $d \equiv 1, 3$ , is $O(\sqrt x)$ — alternatively and more simply: split at $\sqrt x$ . For $d \leq \sqrt x$ , replace $\lfloor x/d\rfloor$ by $x/d + O(1)$ : error $O(\sqrt x)$ . For $d > \sqrt x$ , $\lfloor x/d\rfloor$ takes each value $v < \sqrt x$ on an interval of consecutive $d$ ’s, on which the $\chi$ -sum is $O(1)$ : total error $O(\sqrt x)$ by summing over the $\leq \sqrt x$ values of $v$ , while $\sum_{d > \sqrt x}\chi(d)\frac xd = O(\sqrt x)$ by alternating-series tails ( $x\sum_{d>\sqrt x}\chi(d)/d = x\,O(1/\sqrt x)$ ). Hence

x\sum_{d \leq x}\frac{\chi(d)}d = \frac{\pi x}4 + O(\sqrt x), \qquad\text{i.e.}\qquad \sum_{d\leq x}\frac{\chi(d)}d = \frac\pi4 + O\Bigl(\frac1{\sqrt x}\Bigr),

and letting $x \to \infty$ : $1 - \frac13 + \frac15 - \dots = \frac\pi4$ .

22. If $n \equiv 3 \pmod4$ were $a^2 + b^2$ : squares are $\equiv 0, 1 \pmod 4$ , and $a^2 + b^2 \in \{0, 1, 2\}$ mod $4$ — impossible. (Question 17’s criterion says the same: $n \equiv 3 \pmod 4$ forces some prime $\equiv 3$ to odd exponent.) So representable integers avoid a full residue class: density $\leq \frac34$ . The average $\pi$ of $r_2$ concentrates on few integers: $n = \prod_{j\leq k}p_j$ (distinct primes $\equiv 1 \bmod 4$ ) has $r_2(n) = 4\cdot2^k$ representations — unboundedly many — so a sparse set of $n$ ’s can carry the whole average, exactly as a lottery’s mean payoff coexists with almost-sure loss. Landau’s $\#\{n \leq x \text{ representable}\} \sim Cx/\sqrt{\log x}$ confirms it: density $0$ , average $\pi$ .

23. Necessity. Let $n = a^2 + b^2$ with $\gcd(a, b) = 1$ . If a prime $q \equiv 3 \pmod 4$ divided $n$ , question 13 shows $q \mid a$ and $q \mid b$ : contradiction. If $4 \mid n$ : squares are $\equiv 0, 1 \pmod 4$ , so $a^2 + b^2 \equiv 0 \pmod 4$ forces $a^2 \equiv b^2 \equiv 0$ , i.e. $a, b$ both even: contradiction. Sufficiency. Write $n = 2^{\alpha}\prod_jp_j^{b_j}$ with $\alpha \leq 1$ and $p_j \equiv 1 \pmod 4$ , and set $z = (1+\iu)^{\alpha}\prod_j \pi_j^{b_j} = a + \iu b$ , of norm $n$ . Suppose a prime $t$ divides $\gcd(a, b)$ ; then $t \mid z$ in $\Z[\iu]$ . If $t \equiv 3 \pmod 4$ : $t \mid N(z) = n$ , excluded. If $t \equiv 1 \pmod 4$ : $t = \pi_t\bar\pi_t$ , so $\bar\pi_t \mid z$ ; but the factorization of $z$ contains no conjugate prime ( $\pi_j$ and $\bar\pi_j$ are non-associate, question 17), contradicting unique factorization. If $t = 2 = -\iu(1+\iu)^2$ : then $(1+\iu)^2 \mid z$ , forcing $\alpha \geq 2$ , excluded. Hence $\gcd(a, b) = 1$ : the representation is primitive.

24. $a$ is odd ( $\gcd(a, b) = 1$ , $b$ even), so $c^2 = a^2 + b^2$ is odd and $c$ is odd. Let $\delta$ be a common Gaussian prime divisor of $a + \iu b$ and $a - \iu b$ : it divides their sum $2a$ and their difference $2\iu b$ , hence $2a$ and $2b$ ; a Bézout relation $ua + vb = 1$ then gives $\delta \mid 2$ , so $\delta$ is associate to $1 + \iu$ and $N(\delta) = 2$ divides $N(a + \iu b) = c^2$ , which is odd: contradiction. So $a + \iu b$ and $a - \iu b$ are coprime with product $c^2$ ; in the UFD $\Z[\iu]$ , each Gaussian prime of $c^2$ occurs to an even exponent and splits entirely into one of the two coprime factors, whence $a + \iu b = u(m + \iu n)^2 = u\bigl(m^2 - n^2 + 2\iu mn\bigr)$ with $u$ a unit. The choices $u = \pm\iu$ make the real part $\mp 2mn$ even — impossible, $a$ is odd. The choices $u = \pm1$ give, after adjusting the signs of $m, n$ and swapping their names to make everything positive, $a = m^2 - n^2$ , $b = 2mn$ with $m > n \geq 1$ ; and $c^2 = N(m + \iu n)^2$ gives $c = m^2 + n^2$ . A common divisor of $m$ and $n$ would divide $a$ and $b$ : $\gcd (m, n) = 1$ ; and $m \equiv n \pmod 2$ would make $a$ even: opposite parities. Checks: $(m, n) = (2, 1)$ gives $(3, 4, 5)$ ; $(m, n) = (5, 2)$ gives $(25 - 4, 20, 25 + 4) = (21, 20, 29)$ , and $441 + 400 = 841 = 29^2$ .

25. Jacobi’s formula $r_2(n) = 4(d_1(n) - d_3(n))$ gives, for $n = 1, \dots, 25$ :

4,\ 4,\ 0,\ 4,\ 8,\ 0,\ 0,\ 4,\ 4,\ 8,\ 0,\ 0,\ 8,\ 0,\ 0,\ 4,\ 8,\ 4,\ 0,\ 8,\ 0,\ 0,\ 0,\ 0,\ 12,

nonzero exactly at $n = 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25$ (for instance $r_2(15) = 0$ : divisors $1, 5 \equiv 1$ and $3, 15 \equiv 3$ balance; $r_2(20) = 8$ : divisors $1, 5 \equiv 1$ , none $\equiv 3$ ). The total is $4 + 4 + 4 + 8 + 4 + 4 + 8 + 8 + 4 + 8 + 4 + 8 + 12 = 80$ . The divisor side: the odd $d \leq 25$ contribute

25 - 8 + 5 - 3 + 2 - 2 + 1 - 1 + 1 - 1 + 1 - 1 + 1 = 20,

reading $\chi(d)\lfloor 25/d\rfloor$ for $d = 1, 3, 5, \dots, 25$ ; and $4 \cdot 20 = 80$ , as predicted by question 21’s identity. Lattice points of the closed disc of radius $5$ : the $80$ points with $1 \leq a^2 + b^2 \leq 25$ plus the origin, i.e. $81$ ; and $\pi x = 25\pi \approx 78.54$ , an error of about $2.46$ , comfortably within the $O(\sqrt x)$ band of question 20 ( $\sqrt x = 5$ ).