Thursday, June 16, 2005

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) / (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(γ)

QED

5 comments:

Jose Brox said...

Here you made a typo, you started with beta and switched to gamma!

Larry Freeman said...

Hi Jose,

You are right. Thanks very much! I just fixed it.

-Larry

jenny said...

Suppose Q[sqrt(d)] is a Euclidean field , and alpha, beta are two quadratic integers in Q[sqrt(d)] , so that there exist integers gamma and delta in Q[sqrt(d)] so that alpha = gamma*beta + delta, and
|N(delta)| < |N(beta)|. Show by counterexample that gamma and delta are not necessarily unique.

I have this question that I can't figure out the answer.

Could you suggest me the counterexample counterexample that gamma and delta are not necessarily unique? Thank you very much.

Jenny

Larry Freeman said...

Hi Jenny,

Here's a counter example that I took from another web site:

Divide 3 + 4i by 1 - i so that we have:

(3 + 4i)/(1 - i)

Multiplying top and bottom by 1 + i give us:

(-1 + 7i)/2

We have a choice of four quotients and remainders:

q1 = 3i, r1 = 3 + 4i - (1 - i)3i = i ;

q2 = -1 + 3i, r2 = 1 ;

q3 = 4i, r3 = -1 ;

q4 = -1 + 4i, r4 = -i.

In each case N(ri) < N(1 - i) = 2

-Larry

jenny said...

Hi Larry,

Thank you very much.

Jenny