Euclidean domain

In early chapters we analyzed the structure of ℤ and the polynomial ring 𝕂[x] and seen how in these fields is possible to perform the Euclidean division. In ℤ given two integers a and b, with b ≠ 0, there exist two integers q and r such that a = bq + r, with 0 ≤ r |b|, or in a more general way

Notice how the integers q and r are not univocally determined, for example, let a = 34, b = 8, we have

both relation verify the condition: |r| < |b|.

Analogously, given two polynomial f(x) and g(x), g(x) ≠ 0 in 𝕂[x], indicating by ∂g(x) the degree of g(x), there exist two polynomials q(x) and r(x) in 𝕂[x], such that

In both cases of ℤ and the ring 𝕂[x] we have associated to each element of the domain a positive integer (the absolute value and the degree of the polynomial respectively) in a way that the integer associated to the remainder is less than the the remainder, associated to the divisor. In this way we were able to determine the gcd of two integers or two polynomials through the Euclidean algorithm. The possibility to determine the gcd in this way, was due to the decreasing attitude of the integers associated to the remainders which at some point should be zero, the last non zero remainder was identified with the gcd.

We not want to put what has been said about the division algorithm in ℤ and 𝕂[x] in a wider, abstract context.

Definition 4.8.1. An integral domain R is called a Euclidean domain (or euclidean ring) if there exists a function v: D\{0} → ℕ that satisfies the following two criteria:

1. For all a,b ∈ R with a ≠0, b ≠0, v(a)v(b). ≤ v(ab).

2. For a, b ∈ R with a,b ∈ R with b ≠0 there exist q, r ∈ R (called the quotient and remainder, respectively) such that

   a = bq + r,   r = 0 or v(r) < v(b).

The function v is called a Euclidean valuation for D, which in turn known as Euclidean domain. You should think of the function v as a measure of ‘size’ of the elements. Thus, the first condition says that we can always divide an element of D by a non-zero element; either the division is exact, or we have a remainder ‘smaller’ than the divisor.

Examples 4.8.2. The ring ℤ of integers is an Euclidean domain. We can take as valuation the absolute values, v(a) = |a|, The first condition is then the Division Theorem of ℤ, and the second condition holds because |ab| = |a||b|; the ring 𝕂[x] of polynomials with coefficients in a field 𝕂, is a Euclidean domain if we take as valuation the degree of any non null polynomial. A field 𝕂 is an Euclidean domain, if for example we let v(a) = 1 ∀a ∈ 𝕂, with a ≠ 0; For example in the field of real numbers 15 = 4 ⋅ 15/4 + 0.

Remark. An integral domain can become an Euclidean domain with respect to different valuations. In the case of the field 𝕂, we can pick as well the valuation v(a) = 2, ∀a ∈ 𝕂, a ≠ 0.

Lemma 4.8.3. If a and b are elements in a euclidean ring R, then v(a) = v(ab) if and only if b is invertible. Otherwise, v(a) < v(ab).

Proof. If b is invertible and bc = 1, then v(a) ≤ v(ab) ≤ v(abc) = v(a). Hence v(a) = v(ab).
If b is not invertible, ab does not divide a (If ab divides a, then there exists c such that abc = a; In an integral domain cancellation holds, so bc = 1, i.e. b is invertible) and a = qab + r, where v(r) < v(ab). Now r = a(1 − qb); thus v(a) ≤ v(r). Therefore, v(a) < v(ab).  □

We now introduce an important example of Euclidean domain, known as Gaussian integers.

Proposition 4.8.5. The subset

of the field ℂ, is an Euclidean domain with respect to the following valuation:

Proof. The addition and multiplication operations in ℂ are operations in ℤ[i] as well, and with respect to them ℤ[i] is a ring. Moreover being a subring of the field ℂ, of complex numbers, it is an integral domain. We now want to show that the function v(a + b) := a² + b² serves as a Euclidean valuation, and consequently that ℤ[i] is an Euclidean domain. This is the norm, ||a + ib|| of a complex number, which is an integer ≥ 1 (since such are a and b) whatever non null a + ib ∈ ℤ[i]. Since the complex norm is multiplicative, that is v(xy) = v(x)v(y), is verified as well the relation v(x) ≤ v(xy) ∀ x,y ∈ℤ[i].

Unfortunately, the Division Theorem is not really obvious. So suppose that z₁ = a + ib and z₂ = a + ib two elements of ℤ[i] and we wish to verify the division Theorem for them, where z₂ ≠ 0 will serve as the divisor.

We know that

We can write the ratio of the two complex numbers as

The real and imaginary parts of this complex number certainly need not be integers; We not rewrite this equation using the fact that any fraction of integers can be written as an integer part plus a fractional one, which in absolute value is less that 1/2. Eq (4.8.1) can be rewritten as

with α + iβ ∈ ℤ[i], whilst r₁/(c² + d²) + i r₂/(c² + d²) is in ℚ[i] = {x + iy | x,y ∈ ℚ}. Moreover

By multiplying both sides of 4.8.2 by z₂:

We managed to write a relation of the form

with q = α + iβ, and

This last element is in ℤ[i] since obtained as difference of two elements of ℤ[i]. It is left to prove that r = 0 or v(r) < v(z₂). Indeed we have

It's clear that a ring which is not an integral domain, as for example ℤ_n with n not prime, cannot be an Euclidean domain. Unfortunately, it is not always easy to verify that an euclidean domain in an Euclidean ring: it is necessary to verify that there is not a valuation function satisfying the properties given in the definition.

It is more easy to verify other properties that a ring R has to satisfy to be an integral domain, and which follows from the definition of Euclidean domain. We start by giving the following definitions.

Definition 4.8.6. An integral domain with unit in which every ideal is principal, is known as principal ideal domain.

We've already seen that in ℤ all subrings are of the form (n) = nℤ for some n ∈ ℤ, and how these are automatically all ideals. Thus in ℤ every ideal is a principal ideal domain. With the same proof used for ℤ we can show that 𝕂[x] as well is a principal ideal domain. Every field is obviously an integral domain. We prove now the following proposition.

Definition 4.8.7. Every Euclidean domain is a principal ideal domain.

Proof. We have to prove that every Euclidean domain R has a unit and it is principal. Let I ≠ (0) an ideal of R, and let v the valuation defined on R \ {0}. Let V = {v(a) | a ∈ I}. Since V is not empty V ⊆ ℕ, there exists a n₀ ∈ V and let a₀ an element of I with mininum valuation, i.e. v(a₀) = n₀. We prove that I = a₀R. Clearly, since that a₀ ∈ I we have a₀R ⊆ I. We are left to show that every a ∈ I can be written as a₀t for some t ∈ R. We divide a by a₀:

Since r ∈ I (since it is the difference of two elements in I), to satisfy the minimality of v(a₀) it must be r = 0, as we wished.

Consider now the case I = R. As we already showed there exists an element u ∈ R such that R = uR. Every element a of R can be written as a = ut with t ∈ R. In particular u itself can be written as u = ue, for some e ∈ R: we prove now that this element e is a unit of R. Indeed, for every a ∈ R:

Then R possesses unit, thus I = a₀R = (a₀), i.e. every ideal is principal.□

Proposition 4.8.8. In an Euclidean domain R, any two nonzero elements a and b possess a greatest common divisor.

Proof. Let S = {xa + yb | x,y ∈ R}. Since R has the unit, it must be S ≠ ∅, because a and b are in S. Moreover S is an ideal, and owing to the previous theorem S = (d) for some d ∈ R. We prove now that d is the gcd(a,b). We have d|a and d|b since a ∈ (d) and b ∈ (d). If there exist another divisor d' such that d'| a and d'|b, then d'|d = sa + tb.□

The fact that every Euclidean domain has a unit, has the following consequence.

Proposition 4.8.9. The invertible elements of an euclidean domain R are all and the only elements with minimum valuation, equal to the the valuation of the unit.

Proof. Let a an invertible element of R (hence a ≠ 0). Then

On the other hand we know that, ∀a ∈ R, a≠ 0, v(a) = v(a ⋅ 1) ≥ v(1) i.e. the valuation of 1 is the minimum, from which v(a) = v(1) for all invertible a. Conversely, if a is such that v(a) = v(1), then a is invertible. Indeed by dividing 1 by a we have

Since v(1) is the least valuation, it must necessarily be r = 0 and thus a is invertible. We have so proved that the set, U(R) of invertible elements of R is given by

We have the following table:

The notion of divisibility given for irreducible elements, prime elements and associated elements that were given in the previous chapters for ℤ and 𝕂[x] that lead to the notion of factorization, can be extended to every integral domain with unit.

Let R an integral domain with 1.

• a| b   ⇐⇒   ∃c ∈ R | b = ac

• a ~ b (a is associated to b)   ⇐⇒  a| b and b| a

• u is unit or invertible element   ⇐⇒   ∃u ∈ R | uv = vu = 1

• a ≠ 0 and not invertible is irreducible   ⇐⇒   a = bc   ⇒   b or c is a unit

• a is prime   ⇐⇒   a | bc   ⇒   a | bc   ⇒   a |b or a| c

It can be proven that every prime element of an integral domain with unit is irreducible as we have already proved for ℤ in (Proposition 2.2.12) but the converse is not always true. We now give an example of ring in which the irreducible elements are not prime.

Let a ∈ ℂ. We indicate as

the intersection all subrings of ℂ, containing ℤ and a. For example, in the case of a = i, we have

Let now a = √−3. Consider the ring

We determine first the inevrtible elements of the ring; to every element we associate the complete norm N(a + b√−3) = a² + 3b², the invertibility of a + b√−3 means that there exists a β = c + d√−3 such that αβ = 1. Then N(α)N(β) = N(αβ) = N(1) = 1. Being N(α) a non negative integer it must be N(α) = 1. Hence, to be invertible, an element of ℤ[√−3] must have norm equal to 1. The expression a² + 3b² with a,b ∈ ℤ implies b = 0 and a = ±1. The only invertible elements of ℤ[√−3] are thus ±1.

Example 4.8.9. We now want to show that in ℤ[√−3] there exist irreducible elements which are not also prime elements. Such an element is for example 1 + √−3: suppose that (1 + √−3) = (a + b√−3) (c + d√−3) in ℤ[√−3]. Calculating the norm, we have

The only possibility is that a² + 3b² = 1 or a² + 3b² = 4, since it's not possible the alternative a² + 3b² = 2. The first identity implies, as we've already seen b = 0 and a = ±1, that is a + b√−3 is invertible, in the second case c + d√−3 is invertible. Since 1 + √−3 is not null and not invertible we proved that 1 + √−3 is irreducible; But it is not prime since

we can verify easily that 1 + √-3 divides 2 ⋅ 2, but it does not divide 2; if 1 + √−3 would divide 2, we'd have 2 = (1 + √−3) (a + b√−3) for some a,b ∈ ℤ, and passing to norms, we would have the following relation in ℕ

that implies a² + 3b² = 1, thus b = 0 and a = ±1, that is a + b√−3 = ± 1, giving the absurd relation

Then we proved that in general an irreducible element is not also a prime element. There exists a particular family of rings in which irreducible elements are also prime element, we're going to study in the next paragraph.

Proposition 4.8.10. Suppose the number 3 + 2i can be written as αβ for some Gaussian integers α and β. Then N(α) N(β) = N(3 + 2i) = 13. So either N(α) or N(β) must be 1 and the other must be 13. The factor that has norm 1 must then be ±1 or ±i, so 3 + 2i can only be written as a product of Gaussian integers if one of its factor is a unit: this means that 3 + 2i is irreducible in ℤ[i].