Commutative Algebra 16

Gcd and Lcm

We assume A is an integral domain throughout this article.

If A is a UFD, we can define the gcd (greatest common divisor) and lcm (lowest common multiple) of two elements as follows. For a,b\in A-\{0\}, we can write the ideals (a) and (b) uniquely as a product of primes:

\begin{aligned} (a) &= (\pi_1)^{e_1} (\pi_2)^{e_2} \ldots (\pi_k)^{e_k}, \\ (b) &= (\pi_1)^{f_1} (\pi_2)^{f_2} \ldots (\pi_k)^{f_k}.\end{aligned}

where \pi_i \in A are prime elements and e_i, f_i \ge 0 are integers.

Lemma 1.

We have a|b if and only if e_i \le f_i for each 1 \le i \le k.

Proof

Only (⇒) is non-trivial. Write b = ac for c\in A. If, say, e_1 > f_1, then we have

c\pi_1^{e_1 - f_1} \pi_2^{e_2} \ldots \pi_n^{e_n} = \pi_2^{f_2} \ldots \pi_n^{f_n}.

The prime element \pi_1 occurs in the LHS but not the RHS, which violates unique factorizability. ♦

Definition.

The gcd and lcm of a and b are respectively defined by elements of A satisfying:

\begin{aligned}(\gcd(a, b)) &:= (\pi_1)^{\min(e_1, f_1)} \ldots (\pi_k)^{\min(e_k, f_k)}, \\ (\mathrm{lcm}(a,b)) &:= (\pi_1)^{\max(e_1, f_1)} \ldots (\pi_k)^{\max(e_k, f_k)}.\end{aligned}

Note

The gcd and lcm are well-defined only up to associates. We also define the gcd and lcm of x_1, \ldots, x_n recursively via

\begin{aligned}\gcd(x_1, \ldots, x_n) &= \gcd(\gcd(x_1, \ldots, x_{n-1}), x_n),\\  \mathrm{lcm}(x_1, \ldots, x_n) &= \mathrm{lcm}(\mathrm{lcm}(x_1, \ldots, x_{n-1}), x_n).\end{aligned}

The following properties are important and easily derived from lemma 1.

  • Let g = \gcd(x_1, \ldots, x_n); if y\in A satisfies y|x_i for each 1\le i \le n then y | g.
  • Let h = \mathrm{lcm}(x_1, \ldots, x_n); if y\in A satisfies x_i|y for each 1 \le i \le n then h|y.

warningWe often say elements x,y\in A are coprime if their gcd is 1. This potentially conflicts with our earlier definition of coprime ideals, for if x,y\in A are coprime here, it does not mean (x,y) = (1). E.g. in the next article we will show that k[X, Y] is a UFD but (XY) is a proper ideal.

Hence we will refrain from using the term coprime in this case.

blue-lin

Principal Ideal Domains

Definition.

principal ideal domain (PID) is a domain in which every ideal is principal.

The key property we want to show is:

Theorem.

Let A be a PID. Then A satisfies a.c.c. on principal ideals and A is a UFD.

Proof

For the first claim, let (x_1) \subseteq (x_2) \subseteq \ldots be a chain of principal ideals of A. Now the union of an ascending chain of ideals is an ideal (see proof of proposition 2 here), so \cup_i (x_i) is an ideal, necessarily principal. Write \cup_i (x_i) = (y). Then y\in (x_n) for some n. So

(y) \subseteq (x_n) \subseteq \cup_i (x_i) = (y) \implies (y) = (x_n)

and (y) = (x_n) = (x_{n+1}) = \ldots. This proves the first claim

For the second, let x\in A be irreducible and suppose yz \in (x); we need to show y or z lies in (x). Then (x, y) is principal so we write (x, y) = (y'). Thus x is a multiple of y’; since x is irreducible this means either (x) = (y’) or y’ is a unit.

  • Former case gives us y \in (y') = (x).
  • Latter case gives us ax + by = 1 for some a, b\in A so z = (ax + by)z = axz + byz \in (x) since yz \in (x). ♦

blue-lin

Euclidean Domains

Finally, we have an effective method for identifying some PIDs.

Definition.

An Euclidean function on A is a function N : A - \{0\} \to \mathbb Z_{\ge 0} such that

  • for any a, b \in A where b\ne 0, we can write a = bq + r for some q, r\in A such that r=0 or N(r) < N(b).

If A has an Euclidean function on it, we call A an Euclidean domain.

Note

The Euclidean function gives the “size” of an element a\in A, such that we can always divide b by a to obtain a remainder r which is either zero, or strictly smaller. Repeating this process gives us the gcd of two elements via the Euclidean algorithm.

Theorem.

An Euclidean domain A is a PID.

Proof

Fix an Euclidean function N on A. Let \mathfrak a\subseteq A be an ideal. If \mathfrak a = 0 it is clearly principal. Otherwise, pick x\in \mathfrak a - \{0\} such that N(x) is minimum. We claim that \mathfrak a = (x). Clearly we only need to show ⊆.

Suppose y\in \mathfrak a. Thus we can write y = qx + r where r=0 or N(r) < N(x). In the former case we have y \in (x). The latter case cannot happen since r \in \mathfrak a, N(r) < N(x) but N(x) is already minimum among elements of \mathfrak a. Thus \mathfrak a \subseteq (x). ♦

In a nutshell we have:

ed_pid_ufd_chain

Example: k[X]

Let A = k[X], where k is a field. We take the degree of a polynomial

\deg : A- \{0\} \to \mathbb Z_{\ge 0}.

For any a(X)\in A, b(X) \in A-\{0\}, the remainder theorem gives a(X) = b(X) q(X) + r(X) where r(X) = 0 or \deg r < \deg b. This is exactly the condition for an Euclidean function.

blue-lin

Case Study: Gaussian Integers

We shall prove that the norm function N on A = \mathbb Z[\sqrt{-1}] given by N(a+bi) = a^2 + b^2 is Euclidean. Note that N extends to

N : \mathbb Q[\sqrt{-1}] = \{a + bi : a,b\in \mathbb Q\} \longrightarrow \mathbb Q, \quad N(a+bi) = a^2 + b^2

which is still multiplicative. Now to prove that N is Euclidean, let a,b\in \mathbb Z[\sqrt{-1}] with b\ne 0. Define x = \frac a b \in \mathbb Q[\sqrt{-1}]. By rounding off the real and imaginary parts of x, we obtain q\in \mathbb Z[\sqrt{-1}] such that

x - q = \alpha + \beta i, \quad -\frac 1 2 \le \alpha, \beta <\frac 1 2.

It follows that N(x-q) \le \frac 1 2 < 1. Hence we have:

N(a - bq) = N(b) N(\frac a b - q) = N(b) N(x-q) < N(b).

In conclusion, we have shown:

Theorem.

The ring \mathbb Z[\sqrt{-1}] is an Euclidean domain, hence a PID and UFD.

Since the norm is effectively computable, we can write a program to perform the Euclidean algorithm on this ring.

Factoring in Gaussian Integers

Here, we consider how an integer factors in A = \mathbb Z[\sqrt{-1}].

Proposition 1.

Let p\in \mathbb Z be prime..

  • If p = 2 we have 2 = (-i)(1 + i)^2, where 1+i \in A is prime.
  • If p\equiv 3\pmod 4, then p is still prime in A.
  • If p \equiv 1 \pmod 4, then p = \alpha\beta where \alpha, \beta are primes which are not associates.

Proof

The case for p = 2 is obvious (1+i is prime since its norm is 2, a prime). For odd p, we have

A/(p) \cong \mathbb Z[X]/(X^2 + 1, p) \cong \mathbb F_p[X]/(X^2 + 1).

Now this ring is a domain if and only if X^2 + 1 \equiv 0 \pmod p has no solution. From theory of quadratic residues, this holds if and only if p\equiv 3 \pmod 4.  For p\equiv 1 \pmod 4, we have

A/(p) \cong F_p[X]/((X - u)(X-v))

for distinct uv modulo p. On the RHS ring we have (X-u)(X-v) = 0; hence in the original ring A we have (p) = (p, i-u)\times (p, i-v) since X corresponds to i. And since A is a PID, we have p = \alpha\beta for primes \alpha, \beta which are not associates. ♦

blue-lin

Summary

We have thus shown the following in this article and the previous.

  • To ensure factoring terminates after finitely many steps, we need a.c.c. on the principal ideals of A.
  • Assuming a.c.c. on principal ideals, A is a UFD if and only if all irreducibles in A are prime.
  • If A is a PID, then it satisfies a.c.c. on principal ideals and is a UFD.
  • If A has an Euclidean function, then it is a PID and Euclidean algorithm allows us to compute, for any x,y\in A, their gcd z\in A such that (z) = (x,y).

Exercises

1. Find all solutions to x^2 + y^2 = 5^5 \times 13^4 \times 17^3 \times 29^2 in each of the following cases:

  • xy are any integers;
  • x > y are coprime positive integers.

Note: since the numbers are rather large, the reader is advised to work in Python.

[Hint: x^2 + y^2 is the norm of x+ yi \in \mathbb Z[\sqrt{-1}].]

2. Prove that the norm function is Euclidean for the following rings:

\mathbb Z[\sqrt{-2}], \ \ \mathbb Z[\frac{1 + \sqrt{-3}} 2], \ \ \mathbb Z[\frac{1 + \sqrt{-7}}2], \ \ \mathbb Z[\frac{1 + \sqrt{-11}}2].

[Hint for the last case: this diagram may help.]

3. Fill in the gaps in the solution to the sample problem in the previous article.

4. (Hard) Solve x^2 + 7 = 2^n for positive integers x and n.

5. Write a Python program to compute the Euclidean algorithm in \mathbb Z[\sqrt{-1}].

blue-lin

This entry was posted in Advanced Algebra and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s