Euclidean Integers

A quadratic integer is considered Euclidean if it can be characterized by a division algorithm. This is the algorithm which states that division of any integer by an nonzero integer results in two unique values: a quotient and a remainder and the norm of the remainder is always less than the norm of the divisor.

In a previous blog, I gave the proof for this with regard to Gaussian Integers and with regard to rational integers. So, using these proofs, I have shown that both Gaussian Integers and rational integers are Euclidean.

Since the greatest common divisors algorithm from Euclid derives from the division algorithm, we can also conclude that all Euclidean integers have a greatest common denominator that is a linear combination of two other integers. It is also straight forward to show that all Euclidean integers are characterized by unique factorization.

This means that one sure path to establishing unique factorization is to show that a quadratic integer is Euclidean. Interestingly, it turns out that there are quadratic integers which are not Euclidan which still possess unique factorization.

Definition of Euclidean Integer: A quadratic integer a + b√d is Euclidean if for all integers α, β where β is nonzero, there exists a unique value δ such that δ = α - η*β and absolute(Norm(δ)) is less than absolute(Norm(β)).

Lemma: Z[√2], Z[√-2], Z[√3] are Euclidean

(1) For purposes of this proof, assume that √d = √2, √-2, or √3.

(2) There exists a,b,e,f such that [from the definition quadratic integers]
α = a + b√d
β = e + f√d

(3) α/β = (a + b√d)/(e + f√d) = (a + b√d)(e - f√d) /(e² - f²d)=
(ae - af√d + be√d - bdf)/(e² - f²d) =
(ae - bdf)/(e² - f²d) + √d(be - af)/(e² - f²d)

(4) Let r = (ae - bdf)/(e² - f²d), s = (be - af)/(e² - f²d) where r,s are rational but not necessarily integer. [For a review of rational numbers and their properties, see here]

(5) So α/β = r + s√d.

(6) We know that there exists m,n which are rational integers such that:
absolute(r - m) ≤ (1/2) and absolute(s - n) ≤ (1/2). [See here for proof]

(7) Let η = m + n√d, let δ = α - β * η where η, δ are quadratic integers of type Z[√d]. [For a review of quadratic integers, see here.]

NOTE: The keypoint point is to prove that absolute(Norm(δ)) is less than absolute(Norm(β)).

(8) Norm(δ) = Norm(α - β * η) = Norm(β[(α / β) - η) =
Norm(β) * Norm([α/β] - η)

(9) This means that the key point is to prove that absolute(Norm([α/β] - η)) is less than 1.

(10) We know that:
Norm([α/β] - η) = Norm([r + s√d] - [m + n√d]) = Norm([r - m] + [s - n]√d) =
([r - m] + [s - n]√d)([r - m] - [s - n]√d) = (r - m)² - d(s - n)²

(11) Applying step(6),

gives us for d=2:
absolute((r - m)² - d(s - n)²) ≤ absolute((1/2)² - 2(1/2)²) =
absolute((1/4) - 2(1/4)) = absolute(-1/4) = 1/4 which is less than 1.

gives us for d=-2:
absolute((r - m)² - d(s - n)²) ≤ absolute((1/2)² + 2(1/2)²) =
absolute((1/4) + 2(1/4)) = absolute(3/4) = 3/4 which is less than 1.

gives us for d=3:
absolute((r - m)² - d(s - n)²) ≤ absolute((1/2)² - 3(1/2)²) =
absolute((1/4) - 3(1/4)) = absolute(-2/4) = 1/2 which is less than 1.

QED

Lemma: Z[(1+√-3)/2], Z[(1+√-7)/2], Z[(1+√-11)/2], Z[(1+√5)/2] are Euclidean

(1) For purposes of this proof, assume that √d = √-3, √-7 ,√-11 , or √5.

(2) There exists a,b,e,f such that
α = a + b√d
β = e + f√d

(3) α/β = (a + b√d)/(e + f√d) = (a + b√d)(e - f√d) /(e² - f²d)=
(ae - af√d + be√d - bdf)/(e² - f²d) =
(ae - bdf)/(e² - f²d) + √d(be - af)/(e² - f²d)

(4) Let r = (ae - bdf)/(e² - f²d), s = (be - af)/(e² - f²d) where r,s are rational but not necessarily integer. [For a review of rational numbers and their properties, see here]

(5) So α/β = r + s√d.

(6) We also know that there exists p which is a rational integer such that:
absolute(s - p/2) ≤ 1/4. [See here for proof]

(7) We also know that there exists o which is a rational integer such that:
absolute(r - p/2 - o) ≤ 1/2. [See here for proof]

(8) let η = r + s[(1 + √d)/2] which is an integer as explained in a previous blog since in all above cases d ≡ 1 (mod 4).

(9) Let δ = β*([r - p/2 - o] + [s - p/2]√d)

(10) Norm(δ) = Norm(β) * Norm([r - p/2 - o] + [s - p/2]√d)

(11) Once again, to finish this proof, we need only to show that abs(Norm([r - p/2 - o] + [s - p/2]√d)) is less than 1.

(12) Norm([r - p/2 - o] + [s - p/2]√d) = ([r - p/2 - o] + [s - p/2]√d)([r - p/2 - o] -[s - p/2]√d)
= [r - p/2 - o]² - d[s - p/2]² ≤ (1/2)² - d(1/4)² = (1/4) - d/16.

QED

In addition, here are more interesting facts:

• There are exactly 21 types of quadratic integers that are Euclidean: a quadratic integer is Euclidean if d = -11, -7, -3, -2, -1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37,41, 57, and 73.

• Z[(-1 + √-19)/2] is not Euclidean but still has unique factorization

• Z[√-5] does not have unique factorization.

The content of this blog is based in a large part on Harold M. Stark's An Introduction to Number Theory.