math.wiki
Abstract algebra › Rings in depth › Euclidean domains and principal ideal domains
Sign in

Euclidean domains and principal ideal domains

In the integers and in the polynomials over a field, division leaves a remainder smaller than the divisor, and every ideal is generated by one element. Which other rings have such a division, and what does it buy?

Where you are 4 in Rings in depth

Why this exists

Every ideal of \mathbb{Z} is \langle n \rangle (Ideals and quotient rings, Theorem 5), and the The Euclidean algorithm and coprime numbers finds greatest common divisors; both rest on The division algorithm, which leaves a remainder smaller than the divisor. In F[x], for a field F, degree plays the part of size and the same two facts hold (Polynomial rings and the division algorithm, Theorems 3 and 8). This lesson names the tool, a Euclidean function, and proves both facts once for every integral domain that has one, the Gaussian integers \mathbb{Z}[i] among them.

Definition

Throughout, D is an integral domain: a commutative ring with 1 \ne 0 and no zero divisors (Rings and integral domains).

  • For a, b \in D, b divides a, written b \mid a, if a = cb for some c \in D. Elements a and b are associates if a = ub for a unit u.
  • A greatest common divisor of a and b is a d \in D with d \mid a, d \mid b, and c \mid d for every common divisor c of a and b.
  • An element p \in D is irreducible if it is nonzero, not a unit, and whenever p = bc with b, c \in D, one of b, c is a unit. In F[x], whose units are the nonzero constants, this is the meaning used in Prime and maximal ideals.
  • An ideal is principal if it is \langle a \rangle = \{ra : r \in D\} for some a. A principal ideal domain is an integral domain in which every ideal is principal.

A Euclidean function on D is a map \nu : D \setminus \{0\} \to \mathbb{Z}_{\ge 0} such that for all a, b \in D with b \ne 0 there are q, r \in D with

a = qb + r, \qquad r = 0 \text{ or } \nu(r) < \nu(b).

A Euclidean domain is an integral domain with at least one Euclidean function. Some books, Judson’s among them, also require \nu(a) \le \nu(ab) for nonzero a, b; the functions in Theorem 1 satisfy it, and only Example 5(b) uses it.

The norm on \mathbb{Z}[i] is N(a + bi) = a^2 + b^2, and on \displaystyle \mathbb{Z}[\sqrt{d}] for d = -2 or -5 it is \displaystyle N(a + b\sqrt{d}) = a^2 - db^2. In each case N(z) = z\bar z = |z|^2 (Complex numbers), so N(zw) = N(z)N(w), and N(z) = 0 only for z = 0.

Intuition

A Euclidean function measures size. An ideal holds a nonzero element of least size, and anything else in the ideal, divided by it, leaves a remainder that is in the ideal and smaller still, so zero. That one element generates.

For \mathbb{Z}[i] the picture is the plane. To divide \alpha by \beta, pick a lattice point q near the complex number \alpha/\beta. The remainder r = \alpha - q\beta has |r| = |\beta| \cdot |\alpha/\beta - q|, so N(r) < N(\beta) exactly when q lies at distance less than 1 from \alpha/\beta.

3 + i
4 + i
4 + 2i
3 + 2i
\alpha/\beta
Figure 1Dividing \alpha = 27 + 23i by \beta = 8 + 3i (Example 1). A Gaussian integer q leaves a remainder of smaller norm exactly when it lies in the shaded disk of radius 1 about \alpha/\beta; here three do, 3 + i only just. Every point of the plane is within \displaystyle \frac{\sqrt 2}{2} < 1 of a lattice point, so the disk always holds one.

Results

Throughout, D is an integral domain.

Theorem 1 (three Euclidean domains). (a) \nu(n) = |n| is a Euclidean function on \mathbb{Z}. (b) For a field F, \nu(f) = \deg f is a Euclidean function on F[x]. (c) The norm N is a Euclidean function on \mathbb{Z}[i]; for nonzero \beta, a q can be chosen with \displaystyle N(\alpha - q\beta) \le \frac{1}{2}N(\beta).

Theorem 2. Every Euclidean domain is a principal ideal domain. If \nu is a Euclidean function and I \ne \{0\} an ideal, then I = \langle b \rangle for any nonzero b \in I with \nu(b) least.

Lemma 3. For a, b \in D: \langle a \rangle \subseteq \langle b \rangle if and only if b \mid a; and \langle a \rangle = \langle b \rangle if and only if a and b are associates.

Theorem 4 (greatest common divisors). Let D be a principal ideal domain and a, b \in D. If \langle a, b \rangle = \langle d \rangle, then d is a greatest common divisor of a and b, and d = sa + tb for some s, t \in D. The greatest common divisors of a and b are exactly the associates of d.

Theorem 5 (the Euclidean algorithm). Let \nu be a Euclidean function on D, a, b \in D, b \ne 0. Put r_0 = a, r_1 = b, and while r_k \ne 0 write r_{k-1} = q_k r_k + r_{k+1} with r_{k+1} = 0 or \nu(r_{k+1}) < \nu(r_k). Some r_{n+1} is 0, and the last nonzero remainder r_n is a greatest common divisor of a and b, with \langle a, b \rangle = \langle r_n \rangle.

Theorem 6 (irreducibles in a principal ideal domain). Let D be a principal ideal domain and p \in D nonzero. The following are equivalent: (a) p is irreducible; (b) \langle p \rangle is maximal; (c) \langle p \rangle is prime. So the prime ideals of D are \langle 0 \rangle and the \langle p \rangle with p irreducible, every nonzero prime ideal is maximal, and an irreducible p with p \mid ab divides a or b.

Theorem 7. If D[x] is a principal ideal domain, then D is a field. In particular \mathbb{Z}[x] is not a principal ideal domain, and neither is F[x][y] = F[x, y] for a field F.

Why it is true

Proof of Theorem 1. (a) For b > 0, The division algorithm gives a = qb + r with 0 \le r < b. For b < 0, divide by -b: a = q(-b) + r = (-q)b + r with 0 \le r < |b|.

(b) This is Polynomial rings and the division algorithm, Theorem 3: r = 0 or \deg r < \deg b.

(c) \mathbb{Z}[i] is a subring of \mathbb{C}, hence a domain. Let \alpha, \beta \in \mathbb{Z}[i] with \beta \ne 0. Then \alpha/\beta = \alpha\bar\beta/N(\beta) = s + ti with s, t \in \mathbb{Q}, since \alpha\bar\beta \in \mathbb{Z}[i]. Choose integers m, n with \displaystyle |s - m| \le \frac{1}{2} and \displaystyle |t - n| \le \frac{1}{2}, and put q = m + ni and r = \alpha - q\beta \in \mathbb{Z}[i]. Then

\begin{aligned} N(r) &= |\beta|^2 \left|\tfrac{\alpha}{\beta} - q\right|^2 \\ &\le N(\beta)\left(\tfrac14 + \tfrac14\right) = \tfrac12 N(\beta), \end{aligned}

so r = 0 or N(r) < N(\beta). \square

Proof of Theorem 2. Let \nu be a Euclidean function on D and I an ideal. If I = \{0\}, then I = \langle 0 \rangle. Otherwise the values \nu(b) for nonzero b \in I are nonnegative integers, so one is least; fix such a b. Then \langle b \rangle \subseteq I, as I absorbs multiplication. For a \in I write a = qb + r with r = 0 or \nu(r) < \nu(b). Now r = a - qb \in I, so \nu(r) < \nu(b) is impossible by the choice of b; hence r = 0 and a \in \langle b \rangle. \square

Proof of Lemma 3. \langle a \rangle \subseteq \langle b \rangle holds exactly when a \in \langle b \rangle, that is, a = cb for some c. If \langle a \rangle = \langle b \rangle, then a = cb and b = c'a, so a = cc'a. If a = 0, then b = 0 = 1 \cdot a; otherwise cancellation in the domain D gives cc' = 1, so c is a unit. Conversely, if a = ub with u a unit, then b \mid a and b = u^{-1}a, so a \mid b. \square

Proof of Theorem 4. As d \in \langle a, b \rangle, d = sa + tb for some s, t. As a, b \in \langle d \rangle, d \mid a and d \mid b. If c \mid a and c \mid b, then c divides sa + tb = d. So d is a greatest common divisor. If d' is another, then d \mid d' and d' \mid d, so \langle d \rangle = \langle d' \rangle and they are associates (Lemma 3). Conversely an associate ud divides a and b, and any common divisor c divides d, hence ud. \square

Proof of Theorem 5. While the remainders are nonzero, \nu(r_1) > \nu(r_2) > \cdots is a strictly decreasing sequence of nonnegative integers, so it stops: some r_{n+1} = 0. From r_{k+1} = r_{k-1} - q_k r_k and r_{k-1} = q_k r_k + r_{k+1}, each of r_{k-1}, r_k lies in \langle r_k, r_{k+1} \rangle and each of r_k, r_{k+1} in \langle r_{k-1}, r_k \rangle, so these ideals are equal. Hence \langle a, b \rangle = \langle r_n, r_{n+1} \rangle = \langle r_n \rangle, and Theorem 4 applies, D being a principal ideal domain by Theorem 2. \square

Proof of Theorem 6. (a) implies (b). As p is not a unit, \langle p \rangle \ne D (Ideals and quotient rings, Theorem 2). Let J be an ideal with \langle p \rangle \subseteq J. Then J = \langle c \rangle, and p = cc' by Lemma 3. If c is a unit, J = D; if c' is, c and p are associates and J = \langle p \rangle.

(b) implies (c): every maximal ideal is prime (Prime and maximal ideals, Corollary 4).

(c) implies (a). As \langle p \rangle is proper, p is not a unit, and p \ne 0 by hypothesis. Let p = bc. Then bc \in \langle p \rangle, so say b \in \langle p \rangle: b = pt. Then p = ptc, and cancelling p gives tc = 1, so c is a unit.

For the rest: every ideal is some \langle p \rangle; \langle 0 \rangle is prime as D is a domain; a nonzero prime \langle p \rangle has p irreducible, so is maximal. If p is irreducible and p \mid ab, then ab \in \langle p \rangle, which is prime, so p \mid a or p \mid b. \square

Proof of Theorem 7. As D[x] is a principal ideal domain it is a domain, and so is its subring D of constants. The ideal \langle x \rangle of D[x] is prime because D is a domain (Prime and maximal ideals, Exercise 14), and x \ne 0, so \langle x \rangle is maximal by Theorem 6. By the same exercise, D is a field. Neither \mathbb{Z} nor F[x] is a field (2 and x have no inverses). \square

Worked examples

Example 1

Division with remainder in \mathbb{Z}[i]

Divide \alpha = 27 + 23i by \beta = 8 + 3i in \mathbb{Z}[i]. Find every q with N(\alpha - q\beta) < N(\beta).

Solution

Here N(\beta) = 64 + 9 = 73 and

\alpha\bar\beta = (27 + 23i)(8 - 3i) = 285 + 103i,

so \displaystyle \alpha/\beta = \frac{285}{73} + \frac{103}{73}i \approx 3.904 + 1.411i. Rounding each part gives q = 4 + i and r = (27 + 23i) - (29 + 20i) = -2 + 3i, with N(r) = 13 < 73. By the Intuition, the valid q are the lattice points at distance less than 1 from \alpha/\beta: 4 + i, 3 + i and 4 + 2i (the figure). The other two leave (27 + 23i) - (21 + 17i), which is 6 + 6i with norm 72, and (27 + 23i) - (26 + 28i), which is 1 - 5i with norm 26. So quotient and remainder are not unique.

Example 2

A greatest common divisor in \mathbb{Z}[i]

Find a greatest common divisor \delta of \alpha = 61 + 8i and \beta = 23 + 14i, write it as s\alpha + t\beta, and decide whether \langle \alpha, \beta \rangle is maximal.

Solution

Run Theorem 5, rounding as in Theorem 1(c). First \alpha\bar\beta = 1515 - 670i and N(\beta) = 725, so \alpha/\beta \approx 2.09 - 0.92i, q_1 = 2 - i, and

61 + 8i = (2 - i)(23 + 14i) + (1 + 3i).

Next (23 + 14i)/(1 + 3i) = (65 - 55i)/10 = 6.5 - 5.5i, a corner of four lattice squares; each of the four nearest points leaves norm 5 < 10. With q_2 = 7 - 5i,

23 + 14i = (7 - 5i)(1 + 3i) + (1 - 2i).

Finally 1 + 3i = (-1 + i)(1 - 2i), remainder 0. So \delta = 1 - 2i. Back-substituting, with 1 + (7 - 5i)(2 - i) = 10 - 17i,

\begin{aligned} 1 - 2i &= \beta - (7 - 5i)\bigl(\alpha - (2 - i)\beta\bigr) \\ &= -(7 - 5i)\alpha + (10 - 17i)\beta. \end{aligned}

As N(1 - 2i) = 5 is prime, a factorization 1 - 2i = \gamma\gamma' has a factor of norm 1, a unit. So 1 - 2i is irreducible, and \langle \alpha, \beta \rangle = \langle 1 - 2i \rangle is maximal by Theorem 6.

Example 3

A generator in \mathbb{Z}_7[x]

In \mathbb{Z}_7[x], writing k for [k], let f = x^4 + x^3 + 5x^2 + 2x + 6 and g = x^3 + 5x^2 + 5. Find the monic generator h of I = \langle f, g \rangle, write h = uf + vg, and decide whether I is maximal.

Solution

Dividing, f - xg = 3x^3 + 5x^2 + 4x + 6, and subtracting 3g = 3x^3 + x^2 + 1 leaves

f = (x + 3)g + (4x^2 + 4x + 5).

Next (2x + 1)(4x^2 + 4x + 5) expands to 8x^3 + 12x^2 + 14x + 5, which is g: remainder 0. So 4x^2 + 4x + 5 generates I (Theorem 5), and so does its associate h = 2(4x^2 + 4x + 5) = x^2 + x + 3, as 2 \cdot 4 = 1. From the first division, h = 2f - 2(x + 3)g = 2f + (5x + 1)g. The values of h at 0, 1, \dots, 6 are 3, 5, 2, 1, 2, 5, 3, none 0, so the quadratic h is irreducible, and I is maximal by Theorem 6: \mathbb{Z}_7[x]/I is a field with 49 elements (Prime and maximal ideals, Theorem 7).

Example 4

The camel’s squares

Leah and Samir are designing pieces for a board game on an unbounded square grid. Leah’s camel leaps from (a, b) by any of the eight steps (\pm 3, \pm 1), (\pm 1, \pm 3). Which squares can it reach from (0, 0), and how does it reach (1, 1)?

Solution

Write the square (a, b) as a + bi. The eight steps are u(3 + i) and u(1 + 3i) for the units u = \pm 1, \pm i. The reachable set R, the sums of steps, is closed under addition and negation (the reverse of a step is a step), and under multiplication by i, which permutes the steps. As (c + di)z = cz + d(iz), R absorbs multiplication by \mathbb{Z}[i]: it is an ideal containing 3 + i and 1 + 3i, and every step lies in \langle 3 + i, 1 + 3i \rangle. So R = \langle 3 + i, 1 + 3i \rangle.

Euclid: (1 + 3i)/(3 + i) = (6 + 8i)/10, so q = 1 + i and 1 + 3i = (1 + i)(3 + i) + (-1 - i); then 3 + i = (-2 + i)(-1 - i) exactly. So R = \langle 1 + i \rangle, and a + bi \in R exactly when

\frac{a + bi}{1 + i} = \frac{(a + b) + (b - a)i}{2} \in \mathbb{Z}[i],

that is, when a + b is even. On a checkerboard coloring the camel keeps its color and reaches every square of it. As 1 + i equals (1 + i)(3 + i) - (1 + 3i), three leaps reach (1, 1): (3, 1) + (-1, 3) + (-1, -3).

Example 5

Units from a Euclidean function

Let \nu be a Euclidean function on D. Prove: (a) a nonzero b with \nu(b) least is a unit; (b) if also \nu(a) \le \nu(ab) for all nonzero a, b, then u is a unit if and only if \nu(u) = \nu(1).

Solution

Proof. (a) Write 1 = qb + r with r = 0 or \nu(r) < \nu(b). The second is impossible as \nu(b) is least, so qb = 1.

(b) For nonzero a, \nu(1) \le \nu(1 \cdot a) = \nu(a), so \nu(1) is the least value. If \nu(u) = \nu(1), then u is a unit by (a). If u is a unit, \nu(u) \le \nu(uu^{-1}) = \nu(1) \le \nu(u). \square

The norm on \mathbb{Z}[i] meets the extra condition, as N(ab) = N(a)N(b) \ge N(a), so its units are the elements of norm 1: \pm 1, \pm i, as in Rings and integral domains.

Example 6

A ring that is not a principal ideal domain

Prove that \displaystyle I = \langle 2, 1 + \sqrt{-5} \rangle is not principal in \displaystyle \mathbb{Z}[\sqrt{-5}], so \displaystyle \mathbb{Z}[\sqrt{-5}] has no Euclidean function at all.

Solution

Proof. Write \displaystyle w = \sqrt{-5}. With a, b, c, d \in \mathbb{Z}, an element of I is

\begin{aligned} &2(a + bw) + (1 + w)(c + dw) \\ &\quad = (2a + c - 5d) + (2b + c + d)w, \end{aligned}

and its two coordinates differ by 2a - 2b - 6d, an even number. The coordinates of 1 differ by 1, so 1 \notin I and I is proper.

Suppose I = \langle \delta \rangle. Then 2 = \delta\gamma and 1 + w = \delta\gamma', so N(\delta) divides N(2) = 4 and N(1 + w) = 6, hence N(\delta) \in \{1, 2\}. No integers have a^2 + 5b^2 = 2, so N(\delta) = 1, forcing \delta = \pm 1 and I the whole ring, a contradiction. \square As a subring of \mathbb{C}, \displaystyle \mathbb{Z}[\sqrt{-5}] is a domain, so by Theorem 2 it has no Euclidean function.

Boundaries

  • Not every principal ideal domain is Euclidean. The ring \displaystyle \mathbb{Z}\bigl[\frac{1 + \sqrt{-19}}{2}\bigr] is a principal ideal domain with no Euclidean function. This is stated without proof; both halves are beyond this lesson (Dummit and Foote, Abstract Algebra, Sections 8.1 and 8.2).
  • No uniqueness. In \mathbb{Z} the rule 0 \le r < |b| makes q and r unique, and in F[x] degree does; in \mathbb{Z}[i] up to four quotients can work (Exercise 1). A greatest common divisor is unique only up to a unit.
  • The norm can fail. On \displaystyle \mathbb{Z}[\sqrt{-5}] the norm is not Euclidean (Exercise 9), and by Example 6 nothing is: the point \displaystyle \frac12 + \frac12\sqrt{-5} is farther than 1 from every lattice point, so the argument of Theorem 1(c), which works in \displaystyle \mathbb{Z}[\sqrt{-2}] (Exercise 10), breaks.
  • Two variables. \mathbb{Z}[x] and F[x, y] are not principal ideal domains (Theorem 7), though both factor uniquely (Unique factorization domains).

Where this goes next

By Theorem 6 an irreducible element of a principal ideal domain divides a factor of any product it divides, the property behind Every number has exactly one prime factorization in \mathbb{Z}. Unique factorization domains proves that every principal ideal domain factors uniquely. For irreducible f \in F[x], the field F[x]/\langle f \rangle starts Field extensions and degree.

Exercises

Division and greatest common divisors

  1. Divide 37 + 2i by 5 + 7i in \mathbb{Z}[i]: give the q whose remainder has least norm, and count every q with N(37 + 2i - q(5 + 7i)) < N(5 + 7i).
  2. Find a greatest common divisor of 32 + 9i and 13 - 4i in \mathbb{Z}[i] and write it as s(32 + 9i) + t(13 - 4i).
  3. In \mathbb{Z}_3[x], let f = x^4 + x^3 + x^2 + 2x + 1 and g = x^3 + 2x. Find the monic generator h of \langle f, g \rangle, write h = uf + vg, and decide whether the ideal is prime.
  4. In \displaystyle \mathbb{Z}[\sqrt{-2}], divide \displaystyle 17 + 5\sqrt{-2} by \displaystyle 3 + 2\sqrt{-2} with a remainder of norm less than \displaystyle N(3 + 2\sqrt{-2}).

Ideals and generators

  1. Samir’s piece leaps by (\pm 5, \pm 1) and (\pm 1, \pm 5) on Leah’s grid. Find a generator of the ideal of squares it reaches from (0, 0), and a route to (1, 1).
  2. A second piece of Samir’s leaps by (\pm 3, \pm 2) and (\pm 2, \pm 3). Show that it reaches every square, with a route to (1, 0).
  3. Decide which of 11, 1 + 3i and 5 + 2i generate maximal ideals of \mathbb{Z}[i].

Rings without the property

  1. Prove that \displaystyle \langle 3, 1 + \sqrt{-5} \rangle is not principal in \displaystyle \mathbb{Z}[\sqrt{-5}].
  2. Refute the claim that the norm is a Euclidean function on \displaystyle \mathbb{Z}[\sqrt{-5}], using \displaystyle a = 1 + \sqrt{-5} and b = 2.

Proofs

  1. Prove that \displaystyle N(a + b\sqrt{-2}) = a^2 + 2b^2 is a Euclidean function on \displaystyle \mathbb{Z}[\sqrt{-2}].
  2. Let D be a principal ideal domain and a, b, c \in D with a \mid bc and 1 a greatest common divisor of a and b. Prove that a \mid c.
  3. Call m a least common multiple of a, b in D if a \mid m, b \mid m, and m divides every common multiple. Prove that in a principal ideal domain, \langle a \rangle \cap \langle b \rangle = \langle m \rangle for some m, and that m is a least common multiple.
  4. Prove that every nonzero ideal I of \mathbb{Z}[i] contains a positive integer n, and that \mathbb{Z}[i]/I has at most n^2 elements.
  5. Prove that every subring of \mathbb{Q} is a principal ideal domain.
Answers
  1. (37 + 2i)(5 - 7i) = 199 - 249i, so the quotient is about 2.69 - 3.36i. The nearest point q = 3 - 3i leaves (37 + 2i) - (36 + 6i), that is, 1 - 4i of norm 17. Four q work: 3 - 3i, 2 - 3i, 3 - 4i, 2 - 4i, with remainders of norm 17, 45, 37, 65, all below 74.
  2. 32 + 9i = (2 + i)(13 - 4i) + (2 + 4i), then 13 - 4i = (1 - 3i)(2 + 4i) + (-1 - 2i), then 2 + 4i = -2(-1 - 2i). So 1 + 2i is a greatest common divisor, and 1 + 2i equals (1 - 3i)(32 + 9i) + (-6 + 5i)(13 - 4i).
  3. f = (x + 1)g + (2x^2 + 1) and g = 2x(2x^2 + 1), so h = 2(2x^2 + 1) = x^2 + 2 and h = 2f + (x + 1)g. Not prime: x^2 + 2 = (x + 1)(x + 2) in \mathbb{Z}_3[x], so h is not irreducible (Theorem 6); neither factor lies in \langle h \rangle.
  4. \displaystyle N(3 + 2\sqrt{-2}) = 17, and multiplying by the conjugate \displaystyle 3 - 2\sqrt{-2} gives the quotient \displaystyle (71 - 19\sqrt{-2})/17, so \displaystyle q = 4 - \sqrt{-2}. The remainder is 1, of norm 1: indeed \displaystyle (4 - \sqrt{-2})(3 + 2\sqrt{-2}) + 1 is \displaystyle 17 + 5\sqrt{-2}.
  5. As in Example 4 the ideal is \langle 5 + i, 1 + 5i \rangle. Euclid: 1 + 5i = i(5 + i) + 2, 5 + i = 2 \cdot 2 + (1 + i), 2 = (1 - i)(1 + i). So the generator is 1 + i: the squares with a + b even. Back-substituting, 1 + i = (1 + 2i)(5 + i) - 2(1 + 5i), five leaps: (5, 1) + 2(-1, 5) + 2(-1, -5).
  6. 2 + 3i = 1 \cdot (3 + 2i) + (-1 + i) and 3 + 2i = (-1 - 2i)(-1 + i) + i, a unit, so the ideal is \mathbb{Z}[i]. Back-substituting, 1 = (2 - i)(2 + 3i) - 2(3 + 2i), five leaps: 2(2, 3) + (3, -2) + 2(-3, -2).
  7. 11: a factorization into nonunits would have norms 11 \cdot 11, and a^2 + b^2 = 11 has no integer solution, so 11 is irreducible and \langle 11 \rangle is maximal. 1 + 3i = (1 + i)(2 + i) with both factors of norm above 1: not irreducible, so not maximal. 5 + 2i: norm 29 is prime, so irreducible, and \langle 5 + 2i \rangle is maximal.
  8. Proof. With \displaystyle w = \sqrt{-5}, an element 3(a + bw) + (1 + w)(c + dw) = (3a + c - 5d) + (3b + c + d)w has coordinates differing by 3a - 3b - 6d, a multiple of 3; 1 does not, so the ideal is proper. If it were \langle \delta \rangle, N(\delta) would divide N(3) = 9 and N(1 + w) = 6, so N(\delta) \in \{1, 3\}. As a^2 + 5b^2 = 3 has no solution, N(\delta) = 1, \delta = \pm 1, and the ideal is the whole ring: a contradiction. \square
  9. For \displaystyle q = c + d\sqrt{-5}, \displaystyle a - 2q = (1 - 2c) + (1 - 2d)\sqrt{-5} has odd coordinates, so N(a - 2q) \ge 1 + 5 = 6 > 4 = N(2), and a - 2q \ne 0. No division with smaller remainder exists.
  10. Proof. \displaystyle \mathbb{Z}[\sqrt{-2}] is a subring of \mathbb{C}, so a domain, and N(z) = |z|^2. For \beta \ne 0, \displaystyle \alpha/\beta = \alpha\bar\beta/N(\beta) = s + t\sqrt{-2} with s, t rational. Take integers m, n with \displaystyle |s - m|, |t - n| \le \frac12, and \displaystyle q = m + n\sqrt{-2}. Then r = \alpha - q\beta lies in the ring, and N(r) = N(\beta)\bigl((s - m)^2 + 2(t - n)^2\bigr), which is at most \displaystyle \frac34 N(\beta) < N(\beta). \square
  11. Proof. By Theorem 4, \langle a, b \rangle = \langle d \rangle with d an associate of 1, a unit, so \langle a, b \rangle = D and 1 = sa + tb. Then c = sac + tbc, and a divides both terms. \square
  12. Proof. \langle a \rangle \cap \langle b \rangle contains 0, is closed under subtraction and absorbs multiplication, as both ideals do; so it is an ideal, \langle m \rangle. As m lies in both, a \mid m and b \mid m. A common multiple c lies in both ideals, so in \langle m \rangle: m \mid c. \square
  13. Proof. Take \alpha \in I nonzero; then n = \alpha\bar\alpha = N(\alpha) > 0 lies in I, which absorbs \bar\alpha \in \mathbb{Z}[i]. If a \equiv a' and b \equiv b' \pmod n, then (a + bi) - (a' + b'i) \in \langle n \rangle \subseteq I. So each coset of I contains some a' + b'i with 0 \le a', b' < n, and there are at most n^2 cosets. \square
  14. Proof. A subring R contains 1, hence \mathbb{Z}, and is a domain inside the field \mathbb{Q}. If \displaystyle \frac{a}{b} \in R in lowest terms with b > 0, then ua + vb = 1 for some integers (Bezout's identity and the extended Euclidean algorithm), so \displaystyle \frac1b = u\frac{a}{b} + v \in R. The zero ideal is \langle 0 \rangle; let I \ne \{0\}. For \displaystyle \frac{a}{b} \in I, \displaystyle a = b \cdot \frac{a}{b} \in I, so I \cap \mathbb{Z} is a nonzero ideal of \mathbb{Z}, equal to n\mathbb{Z} with n > 0 (Ideals and quotient rings, Theorem 5). Then nR \subseteq I, and for \displaystyle \frac{a}{b} \in I in lowest terms, a = nk, so \displaystyle \frac{a}{b} = n \cdot k\frac1b \in nR. So I = \langle n \rangle. \square
math.wiki · updated 2026-11-17 · CC-BY-SA-4.0