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**. Then we divide

_{1}**b**by

**r**and we get a second remainder which I will call

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

_{2}**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**value we use is the remainder. It is guaranteed to be at least

_{i}**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

**η**such that:

_{1},δ_{1}**α = η**and

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

_{1}**β**

(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

**δ**divides

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

_{n-1}**δ**divides

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

_{n-2}**δ**and so on up to β and then α. In other words, it is a common divisor for α and β. [By Lemma 1]

_{n-3}(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

## 5 comments:

Mis-spelling in Lemma 2 (9):

wrods.

;-)

Rob

Corollary 3.1 (6) shows up as

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

in Internet Explorer.

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

Rob

Hi Rob,

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

Cheers,

-Larry

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

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

Rob

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.

Post a Comment