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

warning We 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 (X, Y) is a proper ideal.

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

blue-lin

Principal Ideal Domains

Definition.

A 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 u, v 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:

x, y 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

Commutative Algebra 16

Gcd and Lcm

Principal Ideal Domains

Euclidean Domains

Example: k[X]

Case Study: Gaussian Integers

Factoring in Gaussian Integers

Summary

Exercises

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages

Commutative Algebra 16

Gcd and Lcm

Principal Ideal Domains

Euclidean Domains

Example: k[X]

Case Study: Gaussian Integers

Factoring in Gaussian Integers

Summary

Exercises

Share this:

Like this:

Related

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages