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

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 (XY) is a proper ideal.

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

# 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)$. ♦

# 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:

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

# 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. ♦

# 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}]$.

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