Friday, June 17, 2005

Bezout's Identity for Gaussian Integers

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 r1. Then we divide b by r1 and we get a second remainder which I will call r2. 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 ri 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)


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 η11 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.


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.


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 + ηnn-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.


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:
β = ζ * π * γ + η * π * β = π * (ζ * γ + η * β)


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 π.


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.



Scouse Rob said...

Mis-spelling in Lemma 2 (9):




Scouse Rob said...

Corollary 3.1 (6) shows up as

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

in Internet Explorer.

with an & instead of a * in the second expression of the equality.


Larry Freeman said...

Hi Rob,

Thanks very much for noticing the typos. All have been fixed.



Scouse Rob said...

In Lemma 3, Step (3) it should be:

γ = -η(subscript)n(/subscript)


copyme said...

Very interesting post. But I have a small note. You have written that Euclidean Algorithm will stop after at most b iterations for numbers a and b. In fact, the worst case corresponds to Fibonacci numbers. If you take numbers of indexes N+1 and N+2 then the number of iteration is equal to N.