Quadratic Integers: Generalizing Gaussian Integers

Leonhard Euler proposed a proof for Fermat's Last Theorem: n = 3, using integers based on a+b√-3. Carl Friedrich Gauss showed the need for a proof for uniqueness of factorization for a + b√-1. Both of these integer extensions are examples of what we call today quadratic integers.

Quadratic integers are integers that are extended in the form of a + bα where α is an irrational value that is a solution to a quadratic equation. A quadratic equation is any equation that can be represented in the form x² + bx + c = 0 where b,c are rational integers. The important point is that the coefficient for x² needs to be 1 and the other coefficients need to be rational integers.

Applying basic algebra, we know that quadratic equations have the following solution:

Theorem: ax² + bx + c = 0 → x = (-b ± √b² - 4ac)/2a.

(1) Subtracting c from both sides gives us:
ax² + bx = -c

(2) Multiplying both sides by 4a gives us:
4a²x² + 4abx = -4ac.

(3) Adding b² to both sides, gives us:
4a²x² + 4abx + b² = b² - 4ac.

(4) Now, since (2ax + b)*(2ax + b) = 4a²x² + 4abx + b², we get:
(2ax + b)² = b² - 4ac.

(5) Taking the square root of both sides, gives us:
2ax + b = ± √b² - 4ac

(6) Finally, subtracting b and then dividing both sides by 2a gives us our proof.

QED

From this formula, we see that Euler's integer is a solution to:
x² + 3 = 0.

and Gaussian Integers are a solution to:
x² + 1 = 0.

For purposes of notation, a set of quadratic integers is identified using a Z-notation. Z by itself represents the set of standard integers. Z[i] represents the set of Gaussian Integers. Z[√-3] represents the set of Euler's integers.

Now, when it comes to integers of the form Z[√d] where d ≡ 1 (mod 4), it turns out that an integer is of the form: (a + b√d)/2 where a,b are both odd or both even.

To understand the mathematics behind this result, let's start out with a very simple lemma:

Lemma: a² ≡ 1 or 0 (mod 4).

(1) We know that a ≡ 0, 1, 2, or 3 (mod 4).

(2) Now here's what we get for each of these values in the case of a²

(a) 0² ≡ 0 * 0 ≡ 0 (mod 4).
(b) 1² ≡ 1 * 1 ≡ 1 (mod 4).
(c) 2² ≡ 2 * 2 ≡ 0 (mod 4).
(d) 3² ≡ 3 * 3 ≡ 1 (mod 4).

QED

Here is the lemma that establishes this:

Lemma: for a set of quadratic integers Z[√d] , if d ≡ 1 (mod 4), then the form of this quadratic integer is (a + b√d)/2 where both a,b are even or both a,b are odd, otherwise, it is a + b√d

(1) The goal here is to prove that (a + b√d)/2 is an integer, that is, it satisfies an equation of the form x² + bx + c = 0.

(2) Now let's assume that we have a value α which is equal to (e + f√d)/2 where e,f are rational integers and d ≡ 1 (mod 4).

(3) Let x = (e + f√d)/2

(4) Then,
2x - e = f√d

(5) And squaring each side gives us:
4x² - 4ex + e² = f²d

(6) Which amounts to:
4x² - 4ex + e² - f²d = 0

(7) Now if we divide both sides by 4, we get:
x² - ex + (1/4)[e² - f²d] = 0

(8) Now, if both e,f are odd, then: [from the lemma above]
e² - f²d ≡ 1 - 1*1 ≡ 0 (mod 4).

(9) Now, if both e,f are even, then: [from the lemma above]
e² - f²d ≡ 0 - 0 * 1 ≡ 0 (mod 4).

(10) This value then meets our definition of quadratic integer.

QED

Corollary: if d ≡ 1 (mod 4), a number is an integer if it can be written as a + b[(1 + √d)/2], where a,b are rational integers.

(1) a + b(1 + √d)/2 = [(2a + b) + b√d]/2

If b is odd, then (2a + b) is odd. If b is even, then (2a + b) is even. In both cases (2a + b),b are both even or both odd.

(2) If a,b are both even or both odd.

(a + b√d)/2 = (a - b)/2 + b(1 + √d)/2

QED

The result of this is that in the case of d=-3, the set of integers is Z[(-1+√-3)/2] because we are dealing with integers of the form (a + b√-3)/2. I will go into more detail on this when I revisit a proof for n=3 based on Eisenstein integers.

The other interesting point about quadratic integers is that it turns out that not all of them are characterized by unique factorization and most of them are not characterized by a division algorithm.

I will go into more detail about this in my next blog.

The content of this blog is based in a large part on Harold M. Stark's An Introduction to Number Theory.

Proof for n=4 using Gaussian Integers: Step 2

Today's blog continues a proof that was first presented in a previous blog. If you are new to unique factorization, start here. If you are new to Gaussian Integers, start here. To begin this proof, start here.

Today's result is based on work presented by Paulo Ribenboim's Fermat's Last Theorem for Amateurs.

Today's blog shows the details to Step 2 in Fermat's Last Theorem n = 4. As before, I use Greek letters to refer to Gaussian Integers and Latin letters to refer to rational integers. I introduced the Gaussian Prime λ in a previous blog.

Lemma: if Fermat's Last Theorem is true for n = 4, then there exist Gaussian integers: μ₁, μ₂, β, ε, λ such that:

ε * λ^4(r-1) * μ₂⁴ + μ₁⁴ = β².

(1) From the previous lemma, we know that:
ε * λ^4r*α⁴ = γ² - β⁴ = (γ - β²)(γ + β²)

(2) We know that λ² divides both (γ - β²) and (γ + β²) since:

(a) Assume λ² does not divide γ - β²

(b) Then, it must divide γ + β² [From Euclid's Generalized Lemma for Gaussian Integers and (step #1 above)]

(c) But then it necessarily divides γ - β² since
(γ + β²) + (γ - β²) = 2*γ = (λ²)(i * γ) [Since 2= i*λ²]

(d) Having found a contradiction we reject our assumption in step #2a above. We can make the same exact argument if we assume that λ² does not divide γ + β²

(e) So, we are left concluding that λ² necessarily divides both γ - β² and γ + β².

(3) We can also conclude that gcd(γ - β², γ + β²) cannot be greater than 2.

(a) Assume that gcd(γ - β², γ + β²) is greater than 2. Then gcd = λ³ or there exists a prime μ that is greater than 2. [Since we know that λ divides 2, see Lemma 2, here and further, we know that there is no other prime less than 2; see Lemma 4, here]

(b) First, let's assume that there exists a prime μ that is greater than 2.

(c)Then there exists values δ₁, δ₂ such that:
γ - β² = μ * δ₁ and γ + β² = μ * δ₂.

(d) And this means that: μ divides γ since:
2 * γ = (γ - β²) + (γ + β²) = μ(δ₁ + δ₂).

(e) And this also means that μ divides β² since:
2 * β² = (γ + β²) - (γ - β²) = μ(δ₂ - δ₁).

(f) But this is a contradiction since from the lemma cited in step #1 above (see step #4, here), we know that gcd(β²,γ) = 1.

(g) So we reject our assumption in step #3b above and assume that gcd = λ³.

(h) But, then λ³ divides 2 * γ = (γ - β²) + (γ + β²) and λ³ divides 2 * β².

(i) Since λ² is an associate of 2 (see Lemma 2, here), this gives us that λ divides both γ and β².

(j) But this is impossible since we know that β and γ are relatively prime from the lemma cited in step #1 above (see step #4, here)

(k) So we can also reject the assumption in step #3g above and for that matter, the assumption in step #3a above.

(l) So, we can conclude that gcd(γ - β², γ + β²) cannot be greater than 2.

(4) So, we can conclude that λ^4r-2 divides either γ + β² or γ - β² since:

(a) From step #1 above, we know that: λ^r divides (γ - β²)(γ + β²).

(b) From step #2 above, we know that λ² divides both (γ - β²) and (γ + β²).

(c) But, from step #3 above, we know that (λ^4r/λ² = λ^4r-2) can only divide (γ + β²) or (γ - β²) but not both.

(5) So, there exist two values: let's call them η₁ and η₂ such that:
γ ± β² = λ² * η₁
γ ± β² = λ^4r-2 * η₂

NOTE: Please read ± as + or -. So that one of these values is γ + β² and another of these values is γ - β².

(6) We also can conclude that gcd(η₁,η₂) = 1.

(a) Assume that gcd(η₁,η₂) = δ which is not a unit.

(b) So that δ ≥ λ [Since there is no other prime less than λ, see Lemma 4, here]

(c) But then δ*λ² would be greater than 2 which contradicts Step (3) above.

(7) Thus, ε*λ^4rα⁴ = λ^4rη₁η₂ since:

ε*λ^4rα⁴ =(γ - β²)(γ + β²) [From step #1 above]

λ^4rη₁η₂ =(γ - β²)(γ + β²) [From step #5 above]

(8) By the lemma of relatively prime divisors of n-powers, we can conclude that there exists μ₁ and μ₂ such that:

η₁ = ε₁ * μ₁⁴
η₂ = ε₂ * μ₂⁴

NOTE: ε₁ and ε₂ are units.

(9) Now, we know that:
2*β² = γ + β² - (γ - β²)

(10) From step(5) above and step(8) above, let's assume that:
γ - β² = ε₁ * λ² * μ₁⁴
γ + β² = ε₂ * λ^4r-2 * μ₂⁴

NOTE: We can make a similiar argument if the other case is true.

(11) Then,
2 * β² = ε₂ * λ^4r-2 * μ₂⁴ - ε₁ * λ² * μ₁⁴

(12) Which dividing both sides by i*λ² gives us:
β² = -i*ε₂*λ^4r-4*μ₂⁴ + i*ε₁*μ₁⁴

[Note: since 2=i*λ², see Lemma 2, here and since 1/i=-i since -i*i=-(-1)=1]

(13) Now, we can assume that i*ε₁ = 1 since:

(a) r ≥ 2, so we know that λ⁴ divides β² - i*ε₁*μ₁⁴.

(b) But, λ does not divide β

[if it did, from step #2 above, this would mean λ also divides γ, but this is impossible since they are relatively prime from the lemma cited in step #1 above (see step #4, here)]

(c) So, λ cannot divide μ₁

[if λ divided μ₁, then it would also divide η₁ from step #8 above and this is impossible since gcd(η₁,λ)=1 from step #5 above.]

(d) So μ₁ ≡ 1 (mod λ⁶) [See Lemma 5, here]

(e) So that, λ⁴ divides β² - i*ε₁.

(f) But, λ⁶ divides β⁴ - 1 = (β² - 1)(β² + 1)

(g) So, β² ≡ 1 or -1 (mod λ⁴)

(h) This shows that i*ε₁ = ± 1.

(i) If μ₁ = -1, by multiplication with -1, we obtain the relation:
-i*ε₁λ^4(r-1)μ₂⁴ + μ₁⁴ = (iβ)².

(14) Combining Step (12) and Step(13) and setting ε = -i*ε₁ gives us:
β² = ε*λ^4(r-1)*μ₂⁴ + μ₁⁴

QED

Proof for n=4 using Gaussian Integers: Step 1

Today's blog continues a proof that was first presented in a previous blog. If you are new to unique factorization, start here. If you are new to Gaussian Integers, start here. To begin this proof, start here.

Today's result is based on work presented by Paulo Ribenboim's Fermat's Last Theorem for Amateurs.

Today's blog shows the details to Step 1 in Fermat's Last Theorem n = 4. As before, I use Greek letters to refer to Gaussian Integers and Latin letters to refer to rational integers. I introduced the Gaussian Prime λ in a previous blog.

Lemma: if Fermat's Last Theorem is true for n = 4, then there exist α, β, γ, ε, λ such that:
ε * λ^4r * α⁴ + β⁴ = γ² where r ≥ 2

(1) Assume that x⁴ + y⁴ = z² where xyz ≠ 0.

(2) Setting α = x + 0*i, β = y + o*i, γ = z+0*i, we get:
α⁴ + β⁴ = γ² where α, β, γ, are Gaussian Integers.

(3) Now, we can assume that α, β are coprime.

(a) Let δ = gcd(α,β). [See here for method of gcd for Gaussian Integers]
(b) Then, there exists α',β' such that α = δ * α', β = δ * β'.
(c) We know that gcd(α',β') = 1. [since we already divided out all common divisors]
(d) We also know that δ⁴ must divide γ² since γ² = δ⁴(α'⁴ + β'⁴)
(e) Which gives us that δ² must divide γ [From here based on Euclid's Lemma for Gaussian Integers and Fundamental Theorem of Arithmetic for Gaussian Integers]
(f) Then, there exists γ' such that γ = γ' * δ².
(g) So that we get α'⁴ + β'⁴ = γ'²
(h) This shows that we can always reduce α,β, to coprime values.

(4) We can further assume that α, β, γ are coprime.

(a) We know for example that α²,β², and γ are coprime. [See here ]
(b) Assume that there exists δ = gcd(α,γ) where δ is greater than 1.
(c) Then δ² would necessarily divide α⁴ and γ²
(d) It would then also divide β² which goes against (a) so we reject our assumption in (b).
(e) We can use the same argument to show that gcd(β,γ)=1.

(5) We know that λ divides either α or β [See here for proof.]

(6) Let us assume that it divides α. The same arguments will hold if it divides β

(7) Then, there exists α' such that α = α'*λ^r where r ≥ 1.

(8) Let ε be some unit such as 1, -1, i, or -i. We can now state that:
ε * α'⁴ * λ^4*r + β⁴ = γ².

(9) Now, since λ does not divide β, we know that β ≡ 1 (mod λ⁶) which also means that β ≡ 1 (mod λ⁴) since:

(a) β ≡ 1 (mod λ⁶) [See here for proof]
(b) β ≡ 1 (mod λ⁶) implies that λ⁶ divides β - 1. [Definition of ≡]
(c) Thus, there exists δ such that β - 1 = λ⁶ * δ = λ⁴(λ² * δ).

(10) From (8) and (9), we conclude that:
γ² ≡ 1 (mod λ⁴).

(11) Now, based on this we can conclude that γ ≡ 1 (mod λ²) or γ ≡ i (mod λ²) since:

(a) λ² = -2i. [Since λ = 1-i]
(b) γ = a + bi which gives us 4 cases that we need to prove.
(c) Case 1: a is even, b is even. This is impossible since 2 would then divide γ and 2 = (-2i)*i.
(d) Case 2: a is odd, b is odd. This is also impossible since then γ ≡ λ (mod λ²) and we know that λ does not divide γ
(e) Case 3: a is odd, b is even. Since b is divisible by 2i and a is partially divisible by 2, this gives us: γ ≡ 1 (mod λ²)
(f) Case 4: a is even, b is odd. Since a is divisible by 2i and b is partially divisible by 2i, this gives us: γ ≡ i (mod λ²)

(12) But, γ ≡ i (mod λ²) is impossible since:

(a) λ² would divide γ - i.
(b) Then, there exists δ such that: γ - i = λ² * δ
(c) We can restate this as: γ = λ² * δ + i.
(d) Squaring both sides gives us:
γ² = λ⁴*δ² + 2*λ²*δ*i - 1 = λ⁴*δ² + (i*λ²)*λ²*δ*i - 1 =
λ⁴(δ² - δ) - 1.
(e) But then γ² + 1 is divisible by (λ⁴) which contradicts step #10 since γ² - 1 is divisible by λ⁴.

(13) So, γ ≡ 1 (mod λ²) and there exists δ such that:
γ - 1 = λ² * δ

(14) Adding 2 to both sides gives us:
γ + 1 = λ² * δ + 2 = λ²(δ + i).

(15) Now we can conclude that λ divides δ(δ + i) since

(a) if λ divides δ, then this is true so we can assume that λ does not divide δ
(b) By the definition of Gaussian Integers, there exists a,b such that δ = a + bi.
(c) We know that a,b cannot both be even. If both are even, the δ is divisible by 2 which is divisible by λ²
(d) We know that a,b cannot both be odd. If both are odd, then we get a remainder of 1 + i which is equal to (λ)*i = (1 - i)*i = i + 1.
(d) If a is even, b is odd, the remainder is i, then λ divides i + i = 2i which is divisible by λ².
(e) If a is odd, b is even, the remainder is 1. then λ divides 1 + i which is equal to λ * i.

(16) Multiplying Step#13 to both sides of Step#14 gives us:
γ² - 1 = λ⁴(δ)(δ + i).

(17) From this, we can conclude that λ⁵ divides γ² - 1. [From Step #15]

(18) And this gives us that λ⁵ divides ε * α'⁴ * λ^4*r + (β⁴-1).

(19) λ⁵ divides β⁴-1 since:

(a) λ does not divide β [from step #5 and step #6 above]

(b) Then, β⁴ ≡ 1 (mod λ⁶) [See Lemma 5, here]

(c) So, λ⁶ divides β⁴ - 1

(d) Which means that λ⁵ must also divide β⁴ - 1

(20) So, λ⁵ divides ε * α'⁴ * λ^4*r. [if any x divides A+B (step #18 above) and x divides B (step #19 above), then x divides A+B-B=A]

(21) But λ does not divide α' (step #7 above) and it does not divide ε (see step #8 above), so we are left with the conclusion that λ⁵ must divide λ^4*r. [Note, ε is a unit and is only divisible by other units]

(22) And this shows that r ≥ 2.

QED

i - 1 and Fermat's Last Theorem n = 4

Today's blog continues a proof that was first presented in a previous blog. If you are new to unique factorization, start here. If you are new to Gaussian Integers, start here. To begin this proof, start here.

Today's result is based on work presented by Paulo Ribenboim's Fermat's Last Theorem for Amateurs.

Today's blog applies the Gaussian prime λ to Fermat's Last Theorem n = 4. As before, I use Greek letters to refer to Gaussian Integers and Latin letters to refer to rational integers. I introduced the Gaussian Prime λ in a previous blog.

Lemma: if α⁴ + β⁴ = γ² where gcd(α,β,γ)=1, then we can assume that λ divides α * β

(1) Assume λ does not divide α * β

(2) Then, from a previous lemma, we know that α⁴ ≡ 1 (mod λ⁶), β⁴ ≡ 1 (mod λ⁶)

(3) Then, there exists δ₁, δ₂ where: [based on the definition of ≡ found here]
α⁴ - 1 = λ⁶ * δ₁.
β⁴ - 1 = λ⁶ * δ₂

(4) So that:
α⁴ = λ⁶*δ₁ + 1.
β⁴ = λ⁶*δ₂ + 1.

(5) Then:
γ² = λ⁶*δ₁ + 1 + λ⁶*δ₂ + 1 = λ⁶(δ₁ + δ₂) + 2.

(6) Since 2 = i*λ², we get: [From a lemma, found here]
γ² = λ⁶(δ₁ + δ₂) + i*λ² =λ²[λ⁴(δ₁ + δ₂) + i]

(7) Which shows that:
λ² divides γ²

(8) And from this, that:
λ divides γ [Since we have a Gaussian Integer proofs for gcd, unique factorization, and Euclid's Lemma, we can use the proof here. ]

(10) This means that λ⁴ does not divide γ².

(a) Assume that λ⁴ does divide γ².
(b) Then λ⁴ would divide 2 since γ² = λ⁴(λ²δ₁ + λ²δ₂) + 2. [Since d divides a + b and d divides a, implies d divides b]
(c) Then there exists ζ such that 2 = λ⁴ * ζ
(d) Since 2 = i *λ², we get:
i *λ²= λ⁴*ζ
(e) Dividing both sides from λ² gives:
i = λ²*ζ = (1-i)²*ζ = -2i * ζ
(f) Which is impossible since ζ is a Gaussian Integer and not a fraction.

(11) This also gives us that λ² does not divide γ [if it did, then λ⁴ would divide γ² which it cannot.]

(12) Now, since λ divides γ, there must exist a value η such that γ = λ * η

(13) We know that λ cannot divide η. [If it did, then λ² would divide γ]

(14) Now, we have our contradiction. Here are the details

(15) In step(5), we showed that:
γ² = λ⁶*δ₁ + 1 + λ⁶*δ₂ + 1 = λ⁶(δ₁ + δ₂) + 2.

(16) Letting μ = δ₁ + δ₂ and letting γ = λ * η, we get:
(λ*η)² = λ²*η² = λ⁶ * μ + i*(λ²)

(17) Dividing both sides by λ², we get:
η² = λ⁴ * μ + i.

(18) Squaring both sides gives us:
η⁴ = (λ⁴ * μ + i)² = λ⁸*μ² + 2*λ⁴*μ*i -1 =
λ⁸*μ² + ( i*λ²)*λ⁴*μ*i -1 =
λ⁶[λ²*μ² -μ] - 1

(19) So, that we get:
η⁴ ≡ -1 (mod λ⁶)

(20) But, since λ does not divide η, from a previous lemma, we get:
η⁴ ≡ 1 (mod λ ⁶)

(21) It is impossible for both of these modulo λ⁶ values to be true.

(a) Assume η⁴ ≡ -1 (mod λ⁶) and η⁴ ≡ 1 (mod λ⁶).
(b) λ⁶ divides both η⁴ - 1 and η⁴ + 1.
(c) Then there exists ν₁ and ν₂ such that;
η - 1 = λ⁶ * ν₁
η + 1 = λ⁶ * ν₂
(d) Adding the two equations together gives us:
2*η = λ⁶[ν₁ + ν₂]=
i*(λ²)*η = λ⁶[ν₁ + ν₂]
(e) Dividing both sides by λ² gives us:
i*η = λ⁴[ν₁ + ν₂]
(f) But this then implies that λ divides η which goes against assumption. [Note, it doesn't divide i because it is not a unit. It therefore divides η by Euclid's Lemma for Gaussian Integers]

QED

Gaussian Integers: properties of 1 - i

Today's blog continues a proof that was first presented in a previous blog. If you are new to unique factorization, start here. If you are new to Gaussian Integers, start here. To begin this proof, start here.

Today's result is based on work presented by Paulo Ribenboim's Fermat's Last Theorem for Amateurs.

Today's blog focuses on properties of the Gaussian prime λ which we will need to prove Fermat's Last Theorem for n = 4.

Definion 1: λ is a Gaussian Integer that is equal to 1 - i.

Lemma 1: λ is a prime.

Since Norm(λ) = (1 - i)(1 + i) = 1 + 1 = 2. [See here for further details on why this proves that λ is a prime.]

QED

Lemma 2: λ divides 2

i * λ² = (i)(1 - i)² = (i)(1 -2i - 1) = 2.

QED

Corollary 2.1: λ⁶ divides 8

From Lemma 2 above,
(i*λ²)³ =(-i)*λ⁶= 8

QED

Lemma 3: λ*i = (1 + i)

λ * i = i(1 - i) = i + 1

QED

Definition 2: ≡ is relation such that α ≡ β (mod γ) means that α - β is divisible by γ.

We describe this relationship by saying that α modulus γ is equal to β

This definition is true for Gaussian Integers or standard integers. For example, we know that 6 ≡ 2 (mod 4) since 4 divides 6 - 2. We then can say that 6 modulus 4 is equal to 2.

Lemma 4: Let α be any Gaussian Integer. α modulus 2 equals 0, 1, i, or λ

(1) For any α, there exists a,b such that α = a + bi. [Definition of Gaussian Integer]

Case I: a is even, b is even

In this case, α ≡ 0 (mod 2) since a is even, b is even implies there exists A, B such that a = 2A, b = 2B and α = 2A + 2Bi = 2(A+Bi)

Case II: a is odd, b is even

In this case, α ≡ 1 (mod 2) since there exists A, B such that a = 2A+1, b = 2B and α - 1 = 2A + 1 - 1 + 2Bi = 2(A + Bi)

Case III: a is even, b is odd

In this case, α ≡ i (mod 2) since there exists A, B such that a = 2A, b = 2B + 1 and α - i = 2A + (2B+1)i - i = 2A + 2Bi = 2(A+Bi)

Case IV: a is odd, b is odd

In this case, α ≡ λ (mod 2) since there exists A,B such that a = 2A + 1, b = 2B + 1, and α - λ = 2A + 1 + (2B + 1)i - (1 - i) = 2A + 1 + 2Bi + i + i - 1 = 2A + 2B + 2i = 2(A + B + i)

QED

Lemma 5: if α is a Gaussian Integer that is not divisible by λ, then α⁴ ≡ 1 (mod λ⁶).

(1) Since α is not divisible by λ, it cannot be divisible by 2. [See Lemma 2 above]

(2) We also know that modulo 2, it cannot be λ. If α modulo 2 is λ then it would imply that α is divisible by λ which it is not.

(3) So, we are left with α ≡ 1 or i (mod 2) from Lemma 4.

(4) α⁴ ≡ 1 (mod 8) since:

Case I: α ≡ 1 (mod 2)

(a) (α + 1) ≡ (α - 1) ≡ 0 (mod 2)

(b) (α² - 1) ≡ (α + 1)(α - 1) ≡ 0 (mod 4)

(c) (α² + 1) ≡ 0 (mod 2)

(d) (α⁴ - 1) ≡ (α² + 1)(α² - 1) ≡ 0 (mod 8)

Case II: α ≡ i (mod 2)

(a) (α + i) ≡ (α - i) ≡ 0 (mod 2)

(b) (α² + 1) ≡ (α + i)(α - i) ≡ 0 (mod 4)

(c) (α² - 1) ≡ 0 (mod 2)

(d) (α⁴ - 1) ≡ (α² + 1)(α² - 1) ≡ 0 (mod 8)

(5) And this proves that α⁴ ≡ 1 (mod λ⁶) using Corollary 2.1 above.

QED

Proof for n=4 using Gaussian Integers

In today's blog, I will show how it is possible to use Gaussian Integers to establish a proof for Fermat's Last Theorem n = 4. Previously, I showed two proofs for this result. I showed a standard proof based on Pythagorean Triples (see here). Also, I showed how it could be derived from Fermat's proof that a right triangle cannot have a square area (see here).

The proof for the case n = 4 using Gaussian Integer is both very strange and very interesting. The proof that I present is taken from Paul Ribenboem's book Fermat's Last Theorem for Amateurs.

Please note that I use Greek letters to represent Gaussian Integers and Latin letters to represent rational integers. This is really to emphasize that reasoning with Gaussian Integers requires different assumptions. For example, the Well Ordering Principle no longer applies and 2 is no longer a prime.

Theorem: x⁴ + y⁴ = z² has no solution in Gaussian Integers where xyz ≠ 0.

(1) First, I will show that if there is a solution in rational integers, then the following is true:

There exists α, β, γ, ε, λ such that:
ε * λ⁴ⁿ * α⁴ + β⁴ = γ² where n ≥ 2. [See here for proof.]

(2) Second, I will show that if (1) is true, then there is another set of values: ε₁, α₁, β₁, γ₁ such that:

ε₁ * λ^4(n-1) * α₁⁴ + β₁⁴ = γ₁². [See here for proof.]

(3) But then, repeating step (2) again and again, we eventually get to values: α_i, β_i, ε_i, γ_i where

ε_i * λ⁴*α_i⁴ + β_i⁴ = γ_i²

(4) Which contradicts step (1) where n ≥ 2. So we reject that there is a solution to FLT for n=4.

QED

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

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) / (c² + d²) =
= (ac - adi + bci - bdi²)/(c² + d²) =
=(ac + bd)/(c² + d²) + i[(bc - ad)/(c² + d²)]

(3) Let r = (ac + bd)/(c² + d²).

(4) Let s = (bc - ad)/(c² + d²)

(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)² + (s - n)²] * Norm(γ) ≤ [ (1/2)² + (1/2)²]*Norm(γ) =
= (1/2)*Norm(γ) which is less than Norm(γ)

QED

Properties of Gaussian Integers

In my last blog, I spoke about relationship between Gaussian Integers and Fermat's Last Theorem. I went into some detail about norm function which provides a mapping from Gaussian Integers to standard integers. Anyone who is not familiar with Gaussian Integers or the norm function should start here. Anyone not familiar with the idea of unique factorization, should start here.

When we look at standard integers, officially called rational integers, we recognize that most of their properties are based on the Well Ordering Principle. This is the idea that for any given set of nonnegative integers, there is always one that is the smallest. If any one is interested in seeing the proofs related to the Well Ordering Principle and rational integers, you can check out here.

With Gaussian Integers, we are looking at a domain where the Well Ordering Principle does not apply. In the case of rational integers, it was clear that they can be thought to extend across a number line. Gaussian Integers, in contrast, extend across two number lines: a rational integer line and an i integer line.

For this reason, the previous proofs do not apply. We will need to come up with new proofs for the basic ideas. The basic idea of unique factorization is built from the following ideas:

(1) A Division Algorithm: What assumptions can we make about division? What assumptions can we make about quotients and remainders? See here for the algorithm with regard to rational integers. See here for the algorithm with regard to Gaussian Integers.

(2) Bezout's Identity: This is the idea that the greatest common denominator of any two integers can be represented as an equation based on two other integers. See here for the identity with regard to rational integers. See here for the proof of the identity with regard to Gaussian Integers.

(3) Euclid's Lemma: This is the idea that if a prime integer divides the product of two integers, then either it divides the first integer or it divides the second. See here for the proof of Euclid's Lemma regarding rational integers. See here for the proof with regard to Gaussian Integers.

Unique Factorization, it turns out, comes directly from Euclid's Lemma. As a convention, I will use Greek letters to represent Gaussian Integers and Latin letters to represent Rational Integers. So that: α = a + bi where α is a Gaussian Integer and a,b are rational integers.

There is one trick that we need to do in addition to using norms. We need to talk about the idea of associates.

Definition: Associates: Two numbers are associates if one is equal to the other multiplied by a unit.

The Gaussian Integers have four different units: i,-i,1,-1 (see Corollary 4.1, here). So, we can see that 4, -4, 4i, and -4i are all associates of each other. So, when we are talking about unique factorization of primes, we are considering prime associates to be the same prime. So, when we prove unique factorization, we are really proving a unique set of prime-associates.

Theorem: Gaussian Integers posess Unique Factorization.

(1) We know that all non-zero, non-units are either primes or composed of primes. [By the definition of primes]
(2) Let's assume that a given number is made of two different sets of primes.
(4) So α = β₁*β₂*...*β_r = γ₁*γ₂*...*γ_s
(5) Now each prime β_i must necessarily match a prime in γ_j by Euclid's Generalized Lemma. [See here for the proof of Euclid's Generalized Lemma for Gaussian Integers]
(6) But we can make the same argument for all β_i so there must be an equal prime or associate in the set of γ_j.
(7) But then, there cannot be any prime left over since if we divide all the β_i, then we are left with a unit.
(8) So, we have proven that the set of primes is necessarily unique.

QED

Corollary: All Euclidean Integers posessess unique factorization.

(1) By definition, all Euclidean Integers are characterized by a Division Algorithm. [See here for review of Euclidean Integers]

(2) All Euclidean Integers are therefore also characterized by Euclid's Generalized Lemma. [See here for the proof.]

(3) With these two results, the same arguments above apply to all Euclidean Integers.

QED