Monthly Archives: October 2010

Every quotient of a PID by a prime ideal is again a PID

Prove that a quotient of a principal ideal domain by a prime ideal is again a principal ideal domain.


Let R be a principal ideal domain and let P \subseteq R be a prime ideal. Note that R/P is an integral domain.

Now by the lattice isomorphism theorem for rings, every ideal of R/P has the form I/P, where I is an ideal of R containing P. Since R is a principal ideal domain, I = (\alpha) for some \alpha \in R. Then I/P = (\alpha + P) is principal, and thus every ideal of R/P is principal.

Note that every ideal of a quotient of R is principal; we needed P to be prime so that R/P is also an integral domain.

Least common multiples exist in a PID

Let R be a principal ideal domain. Prove that any two nonzero elements in R have a least common multiple.


We saw in this previous exercise that the least common multiples of a and b are precisely the generators of the \subseteq-largest principal ideals contained in (a) \cap (b). Since R is a principal ideal domain, (a) \cap (b) = (\ell) is itself principal, so that a least common multiple indeed exists.

In a PID, two ideals are comaximal precisely when 1 is a gcd of their generators

Prove that in a principal ideal domain, two ideals (a) and (b) are comaximal (that is, (a) + (b) = R if and only if 1 is a greatest common divisor of a and b. In this case, we say that a and b are relatively prime.


Suppose (a) + (b) = R. Since R has a 1, we have (a) + (b) = (a,b) = (1). Then by Proposition 6 in D&F (page 280), 1 is a greatest common divisor of a and b.

Conversely, suppose 1 is a greatest common divisor of a and b. Then we have ax + by = 1 for some x,y \in R, so that 1 \in (a) + (b), and hence (a) + (b) = R.

A public key code

Let N be a positive integer. Let M be an integer which is relatively prime to N and let d be an integer relatively prime to \varphi(N), where \varphi denotes the Euler totient function. Prove that if M_1 \equiv M^d \mod N then M \equiv M_1^e \mod N, where e is a multiplicative inverse of d mod \varphi(N); that is, de \equiv 1 \mod \varphi(N).


Note that M^{de} \equiv M^{k\varphi(N) + 1} \equiv (M^{\varphi(N)})^k \cdot M^1 \mod N. By Euler’s Theorem (proved here), we have M^{\varphi(N)} \equiv 1 \mod N, so that M_1^e \equiv M \mod N as desired.

Update

Hello all.

I just realized that the current front-page post doesn’t really make sense anymore.

The exercises are slowly coming back up- as of right now just over half are back. Before republishing I am giving each example/theorem a descriptive title and updating any backreferences. I’ve also started tagging each post with relevant descriptors. This might have caused you some frustration, but I hope that in the long run this will make the archive more useful.

My goal for now is to get all of the existing posts back up, and then resume working through examples and proofs.

Thanks for reading!

Definition and basic properties of least common multiples

Let R be a commutative ring with 1. Given nonzero elements a,b \in R, a least common multiple of a and b is an element \ell \in R such that a|\ell and b|\ell and if m \in R such that a|m and b|m, then \ell|m.

  1. Prove that a least common multiple of a and b, if it exists, is precisely a generator for the \subseteq-largest principal ideal contained in (a) \cap (b).
  2. Deduce that any two nonzero elements in a Euclidean domain have a least common multiple which is unique up to multiplication by a unit.
  3. Prove that in a Euclidean domain, the least common multiple of a and b is \dfrac{ab}{\mathsf{gcd}(a,b)}.

  1. Suppose first that a least common multiple \ell of a and b exists. Then by definition, we have a|\ell and b|\ell, so that (\ell) \subseteq (a) and (\ell) \subseteq (b). Thus (\ell) \subseteq (a) \cap (b). Suppose now that (m) \subseteq (a) \cap (b). Then (m) \subseteq (a) and (m) \subseteq (b), so that a|m and b|m. Thus \ell|m, and we have (m) \subseteq (\ell). Thus a least common multiple of a and b, provided it exists, generates a \subseteq-largest principal ideal in (a) \cap (b).

    Suppose conversely that (a) \cap (b) contains a \subseteq-largest principal ideal, say (\ell). Then (\ell) \subseteq (a) and (\ell) subseteq (b), so that a|\ell and b|\ell. Moreover, if a|m and b|m, then we have (m) \subseteq (a) \cap (b), so that (m) \subseteq (\ell), and thus \ell|m. Thus a \subseteq-largest principal ideal in (a) \cap (b), if it exists, is a least common multiple of a and b.

  2. Suppose R is a Euclidean domain, and let a,b \in R be nonzero. Now (a) \cap (b) is an ideal in R, and thus is principal (since all ideals in a Euclidean domain are principal). Say (a) \cap (b) = (\ell). Now (\ell) is necessarily the \subseteq-largest principal ideal contained in (a) \cap (b), and so (by the previous part) \ell is a least common multiple of a and b. Moreover, if u is a unit in R, then (u\ell) = (\ell). Thus the least common multiple of a and b is unique up to multiplication by a unit.
  3. Let d be a greatest common divisor of a and b. Note that \dfrac{ab}{d} = a \cdot \dfrac{b}{d}, so that (\frac{ab}{d}) \subseteq (a). Similarly, (\frac{ab}{d}) \subseteq (b), so that (\frac{ab}{d}) \subseteq (a) \cap (b). By the previous part, we have (\frac{ab}{d}) \subseteq (\ell), where \ell is a least common multiple of a and b. Now note that ax = \ell for some x; then abx = b\ell, so that \frac{ab}{\ell}x = b. In particular, \frac{ab}{\ell} divides b. Similarly, \frac{ab}{\ell} divides a. Thus \frac{ab}{\ell} divides d; say \frac{ab}{\ell} \cdot k = d. Then \frac{ab}{d} \cdot k = \ell, so that \frac{ab}{d} divides \ell, and in fact we have (\ell) \subseteq (\frac{ab}{d}). Thus \frac{ab}{d} is a least common multiple of a and b, as desired.

Every proper quotient of the Gaussian integers is finite

Prove that if I \subseteq \mathbb{Z}[i] is a nontrivial ideal, then \mathbb{Z}[i]/I is finite.


Let I \subseteq \mathbb{Z}[i] be a nonzero ideal. We know that every ideal in \mathbb{Z}[i] is principal, so that I = (\beta) for some Gaussian integer \beta. Let \alpha + I be a coset of I; since \mathbb{Z}[i] is a Euclidean domain and \beta \neq 0, we have \alpha = \gamma \beta + \delta, where N(\delta) < N(\beta). That is, every coset in \mathbb{Z}[i]/I is represented by an element whose norm is strictly less than N(\beta).

We claim that for a fixed k \in \mathbb{N}, only finitely many elements \zeta \in \mathbb{Z}[i] can have N(\zeta) = k. To see this, let \zeta = a+bi have norm k; that is, a^2+b^2 = k. Certainly it must be the case that |a|, |b| \leq k, so that there are only finitely many possibilities for \zeta.

Thus there are only finitely many possible representatives of distinct cosets in \mathbb{Z}[i]. Hence \mathbb{Z}[i]/I is finite.

The integers with the square root of 2 adjoined is a Euclidean domain

Prove that \mathbb{Z}[\sqrt{2}] is a Euclidean domain with norm N(a+b\sqrt{2}) = |a^2 - 2b^2|, where bars denote absolute value.


Let \alpha = a_1 + a_2 \sqrt{2} and \beta = b_1 + b_2 \sqrt{2} be elements of \mathbb{Z}[\sqrt{2}] with \beta \neq 0. We wish to show that there exist \gamma and \delta in \mathbb{Z}[\sqrt{2}] such that \alpha = \gamma\beta + \delta and N(\delta) \leq N(\beta). To that end, note that in \mathbb{Q}(\sqrt{2}) we have \frac{\alpha}{\beta} = c_1 + c_2 \sqrt{2}, where c_1 = \dfrac{a_1b_1 - 2a_2b_2}{b_1^2 - 2b_2^2} and c_2 = \dfrac{a_2b_1 - a_1b_2}{b_1^2 - 2b_2^2}. Let q_1 be an integer closest to c_1 and q_2 an integer closest to c_2; then |c_1 - q_1| \leq 1/2 and |c_2 - q_2| \leq 1/2. Now let \gamma = q_1 + q_2 \sqrt{2}; certainly \gamma \in \mathbb{Z}[\sqrt{2}]. Next, let \theta = (c_1 - q_1) + (c_2 - q_2) \sqrt{2}. We have \theta = \frac{\alpha}{\beta} - \gamma, so that \theta\beta = \alpha - \gamma\beta. Letting \delta = \theta\beta, we have \alpha = \gamma\beta + \delta. It remains to be shown that N(\delta) < N(\beta). To that end, note that N(\theta) = |(c_1 - q_1)^2 - 2(c_2 - q_2)^2| \leq |(c_1 - q_1)^2| + |-2(c_2 - q_2)^2| by the triangle inequality. Thus we have N(\theta) \leq (c_1 - q_1)^2 + 2(c_2 - q_2)^2 \leq (1/2)^2 + 2(1/2)^2 = 3/4. In particular, N(\delta) \leq \frac{3}{4}N(\beta) as desired.

Prove that a given quadratic integer ring is or is not a Euclidean domain

Let D be a squarefree integer. Let F = \mathbb{Q}(\sqrt{D}) be the quadratic field with associated quadratic integer ring \mathcal{O} and field norm N given by N(a + \omega b) = |a^2 - Db^2| if D \equiv 2,3 \mod 4 and |a^2 + ab + \frac{1-D}{4}b^2| if D \equiv 1 \mod 4, where \omega = \sqrt{D} if D \equiv 2,3 \mod 4 and \frac{1 + \sqrt{D}}{2} if D \equiv 1 \mod 4. (Recall that \mathcal{O} = \mathbb{Z}[\omega].)

  1. Prove that if D \in \{-1,-2,-3,-7,-11\} then \mathcal{O} is a Euclidean domain with respect to the norm N.
  2. Prove that if D \in \{-43,-67,-163\} then \mathcal{O} is not a Euclidean domain with respect to any norm.

[With help from Planet Math.]

Let D be a squarefree integer, and let \omega = \sqrt{D} if D \equiv 2,3 \mod 4 and (1+\sqrt{D})/2 if D \equiv 1 \mod 4.

First we prove that \mathbb{Z}[\omega] is a Euclidean domain for D \in \{-1,-2\}. That is, for all \alpha,\beta \in \mathbb{Z}[\omega] with \beta \neq 0, there exist \gamma,\delta \in \mathbb{Z}[\omega] such that \alpha = \gamma\beta + \delta and N(\delta) < N(\beta).

To that end, let \alpha = a_1 + a_2\sqrt{D} and \beta = b_1 + b_2 \sqrt{D}. In \mathbb{Q}(\sqrt{D}), we have \dfrac{\alpha}{\beta} = c_1 + c_2 \sqrt{D}, where c_1 = \dfrac{a_1b_1 - Da_2b_2}{b_1^2 - Db_2^2} and c_2 = \dfrac{a_2b_1 - a_1b_2}{b_1^2 - Db_2^2}. Let q_1 \in \mathbb{Z} be an integer closest to c_1 and q_2 an integer closest to c_2. Then |c_1 - q_1| \leq 1/2 and |c_2 - q_2| \leq 1/2. Now let \gamma = q_1 + q_2 \sqrt{D}; certainly \gamma \in \mathbb{Z}[\omega]. Now let \theta = (c_1 - q_1) + (c_2 - q_2)\sqrt{D}, and let \delta = \theta\beta. In \mathbb{Q}(\sqrt{D}), we have \theta = \frac{\alpha}{\beta} - \gamma, so that \delta = \alpha - \gamma\beta. Then \delta \in \mathbb{Z}[\sqrt{D}], and moreover \alpha = \gamma\beta + \delta. It remains to be shown that N(\delta) < N(\beta). To that end, note that N(\theta) = (c_1 - q_1)^2 + |D|(c_2 - q_2)^2 \leq (1/2)^2 + |D|(1/2)^2 = \dfrac{1+|D|}{4}. For D \in \{-1,-2\}, this yields N(\delta) = N(\theta)N(\beta) \leq \frac{3}{4}N(\beta), as desired. \square

Now we show that \mathbb{Z}[\omega] is a Euclidean domain for D \in \{-3,-7,-11\}. But first, a lemma.

Lemma: If D is a squarefree integer such that D \equiv 1 \mod 4 and \omega = (1+\sqrt{D})/2, then \mathbb{Z}[\omega] = \{\frac{a}{2}+\frac{b}{2}\sqrt{D} \ |\ a,b \in \mathbb{Z}, 2|a-b \}. Proof: (\subseteq) If a+b \omega \in \mathbb{Z}[\omega], then evidently a+b\omega = \frac{2a+b}{2} + \frac{b}{2}\sqrt{d}, where certainly 2 divides 2a+b-b. (\supseteq) Consider \frac{a}{2} + \frac{b}{2}\sqrt{D}, with 2|a-b. Evidently, \frac{a}{2} + \frac{b}{2}\sqrt{D} = \frac{a-b}{2} + b\omega, which is in \mathbb{Z}[\omega]. \square

Now to the desired result: Let D \in \{-3,-7,-11\} and \omega = (1+\sqrt{D})/2. Suppose \alpha,\beta \in \mathbb{Z}[\omega] such that \beta \neq 0. Then there exist \gamma,\delta \in \mathbb{Z}[\omega] such that \alpha = \gamma\beta + \delta and N(\delta) < N(\beta), where N(x+y\sqrt{D}) = x^2-Dy^2.

To see this, let \alpha = a_1 + a_2\omega and \beta = b_1 + b_2 \omega. Note that, in \mathbb{Q}(\sqrt{D}), we have \frac{\alpha}{\beta} = c_1 + c_2\sqrt{D}, where c_1 = \dfrac{(2a_1 + a_2)(2b_1+b_2) - a_2b_2D}{(2b_1 + b_2)^2 - Db_2^2} and c_2 = \dfrac{a_2(2b_1 + b_2) - b_2(2a_1 + a_2)}{(2b_1 + b_2)^2 - Db_2^2}. Choose q_2 \in \mathbb{Z} to be an integer closest to 2c_2. Then we have |2c_2 - q_2| \leq \frac{1}{2}, and thus |c_2 - \frac{q_2}{2}| \leq \frac{1}{4}. Next, choose t \in \mathbb{Z} to be an integer closest to c_1 - \frac{q_2}{2}. Let q_1 = 2t + q_2; then we have |c_1 - \frac{q_1}{2}| \leq 1/2. Let \gamma = \dfrac{q_1}{2} + \dfrac{q_2}{2} \sqrt{D}. Certainly q_1-q_2 = 2t is divisible by 2, so that \gamma \in \mathbb{Z}[\omega]. Next, let \theta = (c_1 - \frac{q_1}{2}) + (c_2 - \frac{q_2}{2})\sqrt{D}, and let \delta = \theta\beta. Note that \theta = \dfrac{\alpha}{\beta} - \gamma, so that \delta = \alpha - \gamma\beta is in \mathbb{Z}[\omega]. Moreover we have \alpha = \gamma\beta + \delta. It remains to be shown that N(\delta) < N(\beta); to that end, note that N(\theta) = (c_1 - \frac{q_1}{2})^2  + |D|(c_2 - \frac{q_2}{2})^2 \leq (1/2)^2 + |D|(1/4)^2 = \dfrac{4 + |D|}{16}. For D \in \{-3,-7,-11\}, we have N(\delta) = N(\theta)N(\beta) \leq \frac{15}{16}N(\beta), as desired. \square

Note that our proof is constructive, so that we can easily compute the division algorithm explicitly in these rings or (even better) write a program to do it. Moreover, we can get a bound on how quickly the Euclidean algorithm terminates; for D = -3, at each step we have N(\delta) \leq \frac{7}{16}N(\beta), for instance.

Finally, we show that \mathbb{Z}[\omega] is not a Euclidean domain for D \in \{-43, -67, -163\}. To achieve this, we will show that \mathbb{Z}[\omega] contains no universal side divisors. Recall that if R is an integral domain, then an element u \in R \setminus (R^\times \cup 0) is called a universal side divisor if for every x \in R, there exist elements z \in R^\times \cup 0 and q \in R such that x = qu + z. It is a fact that every Euclidean domain contains universal side divisors; thus if a domain does not contain universal side divisors it cannot be Euclidean with respect to any norm. We begin with some lemmas.

Lemma: Let R be an integral domain with a,b \in R. If ab \in R is a universal side divisor, then a and b are universal side divisors. Proof: Since ab is a universal side divisor, for all x \in R there exist z \in R^\times \cup 0 and q \in R such that x = qab + z. Thus b is a universal side divisor, and since R is commutative, so is a. \square

Let D be a squarefree integer such that D \equiv 1 \mod 4, \dfrac{1-D}{4} \equiv 1 \mod 2, and \dfrac{1-D}{4} \equiv 2 \mod 3, let \omega = (1+\sqrt{D})/2, and suppose that u = a+b\omega \in \mathbb{Z}[\omega] is a universal side divisor. Note that by the lemma, we may assume that \mathsf{gcd}(a,b) = 1; otherwise, we can write u = du^\prime where u^\prime has this property. Now we know that the units in \mathbb{Z}[\omega] are 1 and -1 (for any D). Thus here R^\times \cup 0 = \{0,1,-1\}. Let x = 2; then it must be the case that u divides one of 2-0 = 2, 2-1=1, or 2+1 = 3. By definition u cannot be a unit, so that u cannot divide 1. Thus u divides either 2 or 3.

Suppose u divides 2, and we have 2 = uw. Taking the norm of both sides, we have 4 = N(2) = N(u)N(w). In particular, since u is not a unit, we have N(u) \in \{2,4\}. More generally, N(u) \equiv 0 \mod 2. Note that N(u) = \left|a^2 + ab + \dfrac{1-D}{4}b^2\right|, so that by the hypothesis, a^2 + ab + b^2 \equiv 0 \mod 2. We can see by checking all the cases (there are 4 of them) that this equation has only one solution in \mathbb{Z}/(2), namely the zero solution, with a \equiv b \equiv 0 \mod 2. But this contradicts our assumption that a and b are relatively prime. Thus u cannot divide 2.

Suppose instead that u divides 3, with 3 = uw. Then as above, we have 9 = N(u)N(w), and N(u) \equiv 0 \mod 3. Again by our hypothesis, this yields a^2 + ab + 2b^2 \equiv 0 \mod 3. Note that the squares mod 3 are 0 and 1. Checking all four possibilities for a^2 and b^2, we see that this equation has only the solution a \equiv b \equiv 0 \mod 3, again contradicting the relative primeness of a and b. Thus u cannot divide 3.

Thus we have shown that \mathbb{Z}[\omega] contains no universal side divisors, and thus cannot be a Euclidean domain. (We have proved this in fact for a much larger class of quadratic integer rings than was requested here.)

Compute greatest common divisors in the Gaussian integers

Find a generator for the ideal (85, 1+13i) in \mathbb{Z}[i]; that is, a greatest common divisor of 85 and 1+13i. Use the Euclidean algorithm. Do the same for the ideal (47-13i,53+56i).


First we compute \mathsf{gcd}(85, 1+13i). Evidently, we have 85 = (1-6i)(1+13i) + (6-7i) and 1+13i = (-1+i)(6-7i), where N(1+13i) = 170 and N(6-7i) = 85. Thus \mathsf{gcd}(85,1+13i) = 6-7i, and we have (85,1+13i) = 6-7i.

Now we compute \mathsf{gcd}(47-13i,53+56i). Note that N(47-13i) = 2378 and N(53+56i) = 5945. Evidently we have the following.

53+56i  =  (1+i)(47-13i) + (-7+22i) with N(-7-4i) = 533
47-13i  =  (-1-2i)(-7+22i) + (-4-5i) with N(-4-5i) = 41
-7+22i  =  (-2-3i)(-4-5i)

Thus \mathsf{gcd}(47-13i,53+56i) = -4-5i, so that (47-13i,53-56i) = (4+5i).

We used the following procedure to compute the division algorithm in \mathbb{Z}[i]. Given \alpha = a+bi and \beta = c+di, with \beta \neq 0, let p be an integer closest to \dfrac{ac+bd}{c^2 + d^2} and let q be an integer closest to \dfrac{bc-ad}{c^2+d^2}. Then \alpha = Q\beta + R, where Q = p+qi and R = \alpha - Q\beta. (This is what computers are for.)