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) / (c2 + d2) =
= (ac - adi + bci - bdi2)/(c2 + d2) =
=(ac + bd)/(c2 + d2) + i[(bc - ad)/(c2 + d2)]
(3) Let r = (ac + bd)/(c2 + d2).
(4) Let s = (bc - ad)/(c2 + d2)
(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)2 + (s - n)2] * Norm(γ) ≤ [ (1/2)2 + (1/2)2]*Norm(γ) =
= (1/2)*Norm(γ) which is less than Norm(γ)