Today's blog continues my discussion of Gaussian Integers. If you are unfamiliar with the concept of unique factorization, start

here. For the full discussion about Gaussian Integers, start

here.

Bezout's Identity states that the greatest common denominator of any two integers can be expressed as a linear combination with two other integers. For example, because we know that

gcd(2,3)=1, we also know that 1

= 2(-1) + 3(1). The proof for rational integers can be found

here.

Bezout's Identity is one of three main ideas that are required in order to prove unique factorization. The other two ideas you need are a Division Algorithm, which I detailed in my

last blog, and Euclid's Lemma, which I will discuss in a future blog.

Before discussing Bezout's Identity, we will need a lemma that shows that the notion of greatest common denominator applies to Gaussian Integers.

Using the

Division Algorithm for Gaussian Integers and Euclid's method for

greatest common denominators, we are set. The idea behind Euclid's Method is to do a continuous number of divisions.

Let's assume that we have

**a,b.** First, we divide

**a** by

**b** and get a remainder which I will call

**r**_{1}. Then we divide

**b** by

**r**_{1} and we get a second remainder which I will call

**r**_{2}. We can keep repeating this until eventually we get a remainder which is

**0**. We know that this will happen because each remainder is guaranteed by the Division Algorithm to be smaller than the remainder before. After at most

**b** iterations, we will reach a remainder of

**0**.

Euclid's Method tells us that the last

**r**_{i} value we use is the remainder. It is guaranteed to be at least

**1**. To make the idea behind this lemma as clear as possible, I will throw out one very simple lemma:

Lemma 1: d divides a, d divides b , a = b + c, then d divides c.(1)

d divides

a → there exists

A such that

a = dA.

(2)

d divides

b → there exists

B such that

b = dB(3)

a = b + c → c = a - b = d(A - B)

QED

**Lemma 2: For any two Gaussian Integers, it is possible to find the greatest common denominator.**(1) Let

**α, β** be two Gaussian Integers.

(2) We know that there exists

**η**_{1},δ_{1} such that:

**α = η**_{1}β + δ_{1} and

**0 ≤ δ**_{1} which is less than

**β**(3)

**β = η**_{2*}δ_{1} + δ_{2}(4) And:

**δ**_{1} = η_{3*}δ_{2} + δ_{3}(5) We can keep repeating this until eventually we get:

**δ**_{n-3} = η_{n-1} * δ_{n-2} + δ_{n-1}**δ**_{n-2} = η_{n} * δ_{n-1} + δ_{n}**δ**_{n-1} = η_{n+1}* δ_{n}(6) We know that we eventually get to this point since

Norm(δ_{i+1}) is always less than the

Norm(δ_{i}) by the Division Algorithm.

(7) Now, we know that

**δ**_{n} divides

**δ**_{n-1} by Step #5. We also know that

**δ**_{n} divides

**δ**_{n-2} and therefore, it also divides

**δ**_{n-3} and so on up to

β and then

α. In other words, it is a common divisor for

α and

β. [By Lemma 1]

(8) But we also know that if a certain value

γ divides both

α and

β, then it will necessarily divide

δ_{1} and that it will also necessarily divide

δ_{2} and so on. [Again, by Lemma 1]

(9) In other words, we have proven that

δ_{n} is the greatest common divisor.

QED

Corollary: All quadratic integers that are characterized by a Division Algorithm possess a greatest common denominator.This is true since all the arguments above only assume a Division Algorithm.

QED

Here is the proof for Bezout's Identity:

**Lemma 3: Let α, β be Gaussian Integers. Then there exist two other Gaussian Integers, let's say, ζ, η such that gcd(α,β) = ζα + ηβ**

(1) Based on Lemma 2, we have the following:

**δ**_{n-2} = η_{n} * δ_{n-1} + δ_{n}(2) This can be restated as:

δ_{n} = δ_{n-2} - η_{n} * δ_{n-1}(3) Now, if we let ζ = 1 and γ = -η we have:

δ_{n} = ζ * (δ_{n-2}) + γ * (δ_{n-1})(4) Let's define the following:

δ_{0} = βδ_{-1} = αWith this definition, we can view each step as a continuum of different

δ_{i} values all the way up.

(5) Now, if you look at equation (2), it shows that at each point, any

δ_{i} can be restated in terms of smaller values of

δ_{i-1} and

δ_{i-2}. So that:

δ_{n} = δ_{n-2} - η_{n} * δ_{n-1} =δ_{n-2} - η_{n} * (δ_{n-3} - η_{n-1} * δ_{n-2}) =δ_{n-2}(1 + η_{n}*η_{n-1}) + δ_{n-3}(-η_{n})(6) Setting

ζ = 1 + η_{n} * η_{n-1},

γ = -η_{n}, we get:

δ_{n} = ζ * δ_{n-2} + γ*δ_{n-3}(7) Again, we can take (5) and move it up one using the same equation:

δ_{n} = ζ * (δ_{n-4} - η_{n-2} * δ_{n-3}) + γ * δ_{n-3} == δ_{n-3}(-ζ *η_{n-2} + γ) + δ_{n-4}(ζ)(8) This shows that we can simplify the equation to a 1 smaller number which can be restated as a linear combination.

(9) Eventually, we get to:

δ_{n} = ζ * α + η * βwhere

ζ = some Gaussian Integer value and

η = some Gaussian Integer value.

QED

But now, with the proof of Bezout's Identity, we can get Euclid's Lemma as a corollary.

Corollary 3.1: Euclid's Lemma: if π is a prime that divides α * β, then it divides α or it divides β

(1) Assume

π doesn't divide

α.

Please note:

π is selected as the Greek character equivalent of

p. I am

**not** using

π to represent 3.14....

(2) Then

gcd(π,α) = 1. [By definition of gcd, #1]

(3) From Lemma 3, we know that there exists

ζ, η such that:

1 = ζ * α + η * π.

(4) Multiplying both sides by

β gives us:

β = ζ * α * β + η * π * β(5) Since

π divides

α * β, we know that there exists

γ such that:

α * β = π * γ(6) So we have:

β = ζ * π * γ + η * π * β = π * (ζ * γ + η * β)QED

Corollary 3.2: Euclid's Generalized Lemma: if π divides α_{1} * α_{2} * ... * α_{n}, then π divides at least one of the elements in the product.

(1) Let

β_{1} = α_{2} * ... * α_{n}(2) Then

π divides α

_{1} * β_{1} which means by Euclid's Lemma that

π divides

α_{1} or

β_{1}.

(3) If it divides

α_{1}, we are done.

(4) If it divides

β_{1}, then we set β

_{2} = α_{3} * ... * α_{n} and repeat the argument.

(5) Eventually, we hit some

α_{i} that is divisible by

π.

QED

Corollary 3.3 These results apply to all quadratic integers characterized by a Division Algorithm

Again, none of these arguments are specific to Gaussian Integers. They are true of any quadratic integer that has a division algorithm.

QED