Example 6.1.
Absolute value on \({\mathbb Z}\) is a Euclidean valuation.
Section 6.1 Euclidean Domains
We have repeatedly used the division algorithm when proving results about either \({\mathbb Z}\) or \(F[x]\text{,}\) where \(F\) is a field. We should now ask when a division algorithm is available for an integral domain.
Let \(D\) be an integral domain such that for each \(a \in D \setminus \{0\}\) there is a nonnegative integer \(\nu(a)\) satisfying the following conditions.
- If \(a\) and \(b\) are nonzero elements in \(D\text{,}\) then \(\nu(a) \leq \nu(ab)\text{.}\)
- Let \(a, b \in D\) and suppose that \(b \neq 0\text{.}\) Then there exist elements \(q, r \in D\) such that \(a = bq + r\) and either \(r=0\) or \(\nu(r) \lt \nu(b)\text{.}\)
Then \(D\) is called a Euclidean domain and \(\nu\) is called a Euclidean valuation.
Example 6.2.
Let \(F\) be a field. Then the degree of a polynomial in \(F[x]\) is a Euclidean valuation.
Example 6.3.
\begin{equation*}
{\mathbb Z}[i] = \{ a + b i : a, b \in {\mathbb Z} \}.
\end{equation*}
We usually measure the size of a complex number \(a + bi\) by its absolute value, \(|a + bi| = \sqrt{ a^2 + b^2}\text{;}\) however, \(\sqrt{a^2 + b^2}\) may not be an integer. For our valuation we will let \(\nu(a + bi) = a^2 + b^2\) to ensure that we have an integer.
We claim that \(\nu( a+ bi) = a^2 + b^2\) is a Euclidean valuation on \({\mathbb Z}[i]\text{.}\) Let \(z, w \in {\mathbb Z}[i]\text{.}\) Then \(\nu( zw) = |zw|^2 = |z|^2 |w|^2 = \nu(z) \nu(w)\text{.}\) Since \(\nu(z) \geq 1\) for every nonzero \(z \in {\mathbb Z}[i]\text{,}\) \(\nu( z) \leq \nu(z) \nu(w)\text{.}\)
Next, we must show that for any \(z= a+bi\) and \(w = c+di\) in \({\mathbb Z}[i]\) with \(w \neq 0\text{,}\) there exist elements \(q\) and \(r\) in \({\mathbb Z}[i]\) such that \(z = qw + r\) with either \(r=0\) or \(\nu(r) \lt \nu(w)\text{.}\) We can view \(z\) and \(w\) as elements in \({\mathbb Q}(i) = \{ p + qi : p, q \in {\mathbb Q} \}\text{,}\) the field of fractions of \({\mathbb Z}[i]\text{.}\) Observe that
\begin{align*}
z w^{-1} & = (a +b i) \frac{c -d i}{c^2 + d^2}\\
& = \frac{ac + b d}{c^2 + d^2} + \frac{b c -ad}{c^2 + d^2}i\\
& = \left( m_1 + \frac{n_1}{c^2 + d^2} \right) + \left( m_2 + \frac{n_2}{c^2 + d^2} \right) i\\
& = (m_1 + m_2 i) + \left( \frac{n_1}{c^2 + d^2} + \frac{n_2}{c^2 + d^2}i \right)\\
& = (m_1 + m_2 i) + (s + ti)
\end{align*}
in \({\mathbb Q}(i)\text{.}\) In the last steps we are writing the real and imaginary parts as an integer plus a proper fraction. That is, we take the closest integer \(m_i\) such that the fractional part satisfies \(|n_i / (a^2 + b^2)| \leq 1/2\text{.}\) For example, we write
\begin{align*}
\frac{9}{8} & = 1 + \frac{1}{8}\\
\frac{15}{8} & = 2 - \frac{1}{8}.
\end{align*}
Thus, \(s\) and \(t\) are the “fractional parts” of \(z w^{-1} = (m_1 + m_2 i) + (s + ti)\text{.}\) We also know that \(s^2 + t^2 \leq 1/4 + 1/4 = 1/2\text{.}\) Multiplying by \(w\text{,}\) we have
\begin{equation*}
z = z w^{-1} w = w (m_1 + m_2 i) + w (s + ti) = q w + r,
\end{equation*}
where \(q = m_1 + m_2 i\) and \(r = w (s + ti)\text{.}\) Since \(z\) and \(qw\) are in \({\mathbb Z}[i]\text{,}\) \(r\) must be in \({\mathbb Z}[i]\text{.}\) Finally, we need to show that either \(r = 0\) or \(\nu(r) \lt \nu(w)\text{.}\) However,
\begin{equation*}
\nu(r) = \nu(w) \nu(s + ti) \leq \frac{1}{2} \nu(w) \lt \nu(w).
\end{equation*}
Recall that for integers and polynomials, we defined the greatest common divisor to be the common divisor which had the largest possible magnitude or degree, respectively. We could make a similar definition with respect to the valuation on a Euclidean domain, but it is also useful to have a definition that works for an arbitrary integral domain. For inspiration, we look at the last sentence of Theorem 2.10, where the greatest common divisor of two integers \(a\) and \(b\) is characterized by being divisible by all common divisors of \(a\) and \(b\text{.}\)
In any integral domain \(R\text{,}\) we say that an element \(d\) is a common divisor of elements \(a\) and \(b\) if \(d\) divides both \(a\) and \(b\text{.}\) The element \(d\) is a greatest common divisior if \(d\) is a common divisor \(a\) and \(b\) and any common divisor \(d'\) of \(a\) and \(b\) divides \(d\text{.}\) In general, the greatest common divisor might not exist or might exist but not be unique. By Theorem 2.10 and Proposition 5.10, the greatest common divisor of two integers or two polynomials is also a greatest common divisor in this more general sense.
Theorem 6.4.
If \(a,b \in D\) are elements in a Euclidean domain, then there exist \(s,t\in D\) such that \(d = sa + tb\text{,}\) and \(d\) is a greatest common divisor of \(a\) and \(b\text{.}\)
Proof.
Let
\begin{equation*}
S = \{ra + r'b : r, r' \in D\}.
\end{equation*}
Let \(d = sa + tb\) be a non-zero element of \(S\) with the smallest possible valuation. We claim that \(d\) is the greatest common divisor of \(a\) and \(b\text{.}\) By the definition of Euclidean domain, there exists \(q, r \in D\) such that \(a = dq + r\) and either \(\nu(r) < \nu(d)\) or \(r=0\text{,}\) where \(\nu\) is the Euclidean valuation. Since
\begin{equation*}
r = a - dq = a - (sa + tb)q = (1-sq)a + tq b
\end{equation*}
is in \(S\text{,}\) and \(d\) was chosen to have minimal valuation, \(r = 0\text{,}\) so \(d\) divides \(a\text{.}\) Similarly, \(d\) divides \(b\text{.}\)
To show that \(d\) is a greatest common divisor, we suppose that \(d'\) divides \(a\) and \(b\text{.}\) But then, \(d'\) divides \(d = sa+tb\text{.}\) Therefore, \(d\) is a greatest common divisor.
