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 r₁. Then we divide b by r₁ and we get a second remainder which I will call r₂. 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 η₁,δ₁ such that:
α = η₁β + δ₁ and 0 ≤ δ₁ which is less than β

(3) β = η_2*δ₁ + δ₂

(4) And: δ₁ = η_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 δ₁ and that it will also necessarily divide δ₂ 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:
δ₀ = β
δ_-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 α₁ * α₂ * ... * α_n, then π divides at least one of the elements in the product.


(1) Let β₁ = α₂ * ... * α_n

(2) Then π divides α₁ * β₁ which means by Euclid's Lemma that π divides α₁ or β₁.

(3) If it divides α₁, we are done.

(4) If it divides β₁, then we set β₂ = α₃ * ... * α_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