Division Algorithm for Gaussian Integers

In my previous blog, I showed the details for a proof that Gaussian Integers have unique factorization. If any of the information that I present gets confusing, I suggest that readers start here where I explain about unique factorization, Gaussian Integers, the norm function, and the reason I am using Greek letters to represent Gaussian Integers.

In today's blog, I will show how using the norm function, it is possible to arrive at a Division Algorithm for Gaussian Integers.

The Division Algorithm for rational integers is based on the Well-Ordering Principle and can be found here. It states that whenever we divide one integer by another integer, we are left with a quotient and remainder that are both integers and which are both unique to the division and the remainder is guaranteed to be less than the divisor.

In the lemma below I used Greek letters for Gaussian Integers, Latin letters for rational integers, and Z[i] to represent the set of Gaussian Integers.

Lemma: Division Algorithm for Gaussian Integers

Given: α, γ ∈ Z[i]

Then: there exists ζ, δ such that: α = ζγ + δ and Norm(δ) is less than Norm(γ)

(1) There exists a,b,c,d such that:
α = a + bi
γ = c + di

(2) α / γ = (a + bi) / (c + di) = (a + bi)(c - di) / (c² + d²) =
= (ac - adi + bci - bdi²)/(c² + d²) =
=(ac + bd)/(c² + d²) + i[(bc - ad)/(c² + d²)]

(3) Let r = (ac + bd)/(c² + d²).

(4) Let s = (bc - ad)/(c² + d²)

(5) So, α / γ = r + si

(6) And we know that both r,s are rational. We do not know if they are integers.

(7) We know that there are m,n which are integers such that absolute(r - m) ≤ (1/2) and absolute(s - n) ≤ (1/2). [For proof of this see here]

(8) Let ζ = m + ni.

(9) Let δ = α - ζγ → α = ζγ + δ

(10) Norm(δ) = Norm(α - ζγ) =
= Norm(γ[(α/γ) - ζ] = Norm(α/γ - ζ) * Norm(γ) =
= Norm(r + si - [m + ni]) * Norm(γ) =
= Norm(r - m + si - ni) * Norm(γ) =
= Norm([r - m] + [s -n]i) * Norm(γ) =
= [(r - m)² + (s - n)²] * Norm(γ) ≤ [ (1/2)² + (1/2)²]*Norm(γ) =
= (1/2)*Norm(γ) which is less than Norm(γ)

QED