# 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 , we can write the ideals (*a*) and (*b*) uniquely as a product of primes:

where are prime elements and are integers.

Lemma 1.We have if and only if for each .

**Proof**

Only (⇒) is non-trivial. Write for . If, say, , then we have

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

Definition.The

gcdandlcmof a and b are respectively defined by elements of A satisfying:

**Note**

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

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

- Let ; if satisfies for each then .
- Let ; if satisfies for each then .

We often say elements are coprime if their gcd is 1. This potentially conflicts with our earlier definition of coprime ideals, for if are coprime here, it does not mean . E.g. in the next article we will show that is a UFD but (*X*, *Y*) is a proper ideal.

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

# 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 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 is an ideal, necessarily principal. Write . Then for some *n*. So

and . This proves the first claim

For the second, let be irreducible and suppose ; we need to show *y* or *z* lies in (*x*). Then is principal so we write . 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 .
- Latter case gives us for some so since . ♦

# Euclidean Domains

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

Definition.An

Euclidean functionon A is a function such that

- for any where , we can write for some such that or .
If A has an Euclidean function on it, we call A an

Euclidean domain.

**Note**

The Euclidean function gives the “size” of an element , 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 be an ideal. If it is clearly principal. Otherwise, pick such that is minimum. We claim that Clearly we only need to show ⊆.

Suppose . Thus we can write where or . In the former case we have . The latter case cannot happen since , but is already minimum among elements of . Thus . ♦

In a nutshell we have:

### Example: *k*[*X*]

Let , where *k* is a field. We take the degree of a polynomial

For any , the remainder theorem gives where or . This is exactly the condition for an Euclidean function.

# Case Study: Gaussian Integers

We shall prove that the norm function *N* on given by is Euclidean. Note that *N* extends to

which is still multiplicative. Now to prove that *N* is Euclidean, let with . Define . By rounding off the real and imaginary parts of *x*, we obtain such that

It follows that . Hence we have:

.

In conclusion, we have shown:

Theorem.The ring 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 .

Proposition 1.Let be prime..

- If we have , where is prime.
- If , then p is still prime in A.
- If , then where 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

Now this ring is a domain if and only if has no solution. From theory of quadratic residues, this holds if and only if . For , we have

for distinct *u*, *v* modulo *p*. On the RHS ring we have ; hence in the original ring *A* we have since *X* corresponds to *i*. And since *A* is a PID, we have for primes 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 , their gcd such that .

## Exercises

1. Find all solutions to 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: is the norm of .]

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

[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 for positive integers *x* and *n*.

5. Write a Python program to compute the Euclidean algorithm in .