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.
We have if and only if for each .
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. ♦
The gcd and lcm of a and b are respectively defined by elements of A satisfying:
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
A principal ideal domain (PID) is a domain in which every ideal is principal.
The key property we want to show is:
Let A be a PID. Then A satisfies a.c.c. on principal ideals and A is a UFD.
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 . ♦
Finally, we have an effective method for identifying some PIDs.
An Euclidean function on 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.
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.
An Euclidean domain A is a PID.
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:
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:
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 .
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.
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. ♦
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 .
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 .