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.

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.)