CH 8 Gaussian integers Flashcards
DEF 8.0.1 Gaussian integers
The Gaussian integers are the complex numbers in the set
Z[ı] := {a + bı : a, b ∈ Z},
where ı =√−1.
We also talk about Z[√−5] = {a + b√−5 : a, b ∈ Z} quite a few times.
This section is here for reference only. We are not interested in the general theory of
rings, but need some basic concepts in order to discuss Z[ı], Z[√−5] and similar rings.
Therefore, this section is not directly examinable:
he exam will not ask ‘define what
is a ring’ or ‘give an example of a ring which is not an integral domain’. Rather, you
may be asked about primes, units, factorisations in specific rings of number theoretic
interest such as Z[ı], Z[√−5].
for reference only: rings
A ring is a set R equipped with addition ‘α + β’ and multiplication ‘αβ’ satisfying the
usual axioms:
* addition and multiplication are associative; addition is commutative;
* multiplication is distributive over the sum (α(β + γ) = αβ + αγ);
* there is an additive identity (α + 0 = α, α · 1 = α);
* for every α ∈ R, there is an additive inverse −α ∈ R (that is, α + (−α) = 0).
for reference only
examples of rings
Example 8.1.1.
Examples you have seen are Z, Q, R, C. The Gaussian integers form a ring. Indeed, commutativity, distributivity, associativity hold in C, so they also hold
in Z[ı] automatically; we only need to verify that Z[ı] is closed under sums, products,
and taking additive inverses. Let a + bı, c + dı ∈ Z[ı], thus a, b, c, d ∈ Z. Then
(a + bı) + (c + dı) = (a + c) + (b + d)ı ∈ Z[ı],
(a + bı)(c + dı) = (ac − bd) + (ad − bc)ı ∈ Z[ı],
(a + bı) + (−a + (−b))ı = 0 + 0ı = 0.
Two-by-two matrices also form a ring.
N is not a ring: no natural number apart from 0 has an additive inverses in N.
for reference only
Definition 8.1.2 integral domain
An integral domain is a ring where multiplication is commutative and αβ = 0
happens only if α = 0 or β = 0.
Example 8.1.3. Z, integral domains.
Example 8.1.3. Z, Q, R, C, Z[ı] are all integral domains.
Two-by-two matrices are not: multiplication is not commutative. Diagonal two-bytwo matrices do not form an integral domain either: multiplication is commutative,
but for instance
[1 0
0 0 ]
[ 0 0
0 1 ]
=
0 0
0 0
.
From now on, let R be an integral dom
.
Definition 8.
divides
Let α, β ∈ R. We say that β divides α (written β | α) if there is γ ∈ R with α = ,βγ
.
Example 8.1.5. Within Z, this is the usual definition of divisibil does 2 divide 6 in Z[i]?
Does 1+i divide 2?
for instance, 2 | 6
but 2 ∤ 3.
In Z[ı], we have (1 + ı)(1 − ı) = (1² − ı²) + (1 − 1)ı = 1 + 1 = 2, thus (1 + ı) | 2.
Note that when R ⊆ C, to check if β | α, it suffices to compute γ = α/β
2/(1+i)=2(1-i)/(1+i)(1-i) = 2-2i/2=1+i in Z[i] so true
(a complex number) and check if γ ∈ R. This is analogous to computing a fraction a/b in Q and
checking if a/b ∈ Z
Definition 8.1.6 unit
An element α ∈ R is a unit if α | 1, that is to say, if there is β ∈ R such that αβ = 1
(such β is the multiplicative inverse of 1).
(reminder: a unit is s.t there exists a multiplicative inverse that is also a gaussian integer)
Example 8.1.7. The units of Z are .
Example 8.1.7. The units of Z are the integers ±1.
The units of Z[ı] are
are +1-1,+i,-i
indeed
i(-i)=-(-1)(1) multiplicative inverses?
all the numbers α such that
1/α=α_overline/{αα_overline)=
α_overline/|α|^2
∈ Z[ı].
For instance, (−ı) is a unit: its inverse is ı itself (note that | − ı|^2 = 1!).
Exercise 8.1.8. Show that the units of Z[ı] are exactly ±1 and ±ı. [Hint: show that the
units of Z[ı] must have modulus 1, then find all such Gaussian integers.]
if αβ = 1 for α,β in Z[i]
then | α|^2|β|^2 = 1
property of modulus that it is multiplicative
so |ab|=|a||b|
Definition 8.1.11
ireducible
prime
Let R be an integral domain. An element α ∈ R that is not a unit is:
* irreducible if whenever α = βγ, one of β, γ is a unit;
* prime if whenever α | βγ, we have α | β or α | γ
(in Z analagous to divisors being 1 or itself, instead we say divisors relate to units)
(irreducible- whenevr we break into products of two other integers then 1 of the integers is a unit)
(prime divide one of two factors)
Example 8.1.12
which primes irreducible in Z
in Z[i[
±2, ±3, ±5, . . . are all primes and irreducible, while for instance
6 = 2 · 3 is not irreducible, nor prime.
in Z[i]
2 is not irreducible
2=(i+1)(1-i) and these arent units
3 is irreducible as we will see later
Lemma 8.1.13. irreducible
Lemma 8.1.13. Every prime is irreducible
Suppose that α is prime and α = βγ. Then α | β or α | γ, while of course β | α and γ | α.If α | β, then γ is a unit by Lemma 8.1.10; if α | γ, then β is a unit. Thus one of
β, γ is a unit, showing that α is irreducible.
example:
Example 8.1.14. Take R = Z[√−5].
Is 2 prime
Is 2 irreducible
6 = 2 · 3 = (1 +√−5)(1 −√−5).
Clearly, 2 ∤ (1 +√−5) and 2 ∤ (1 −√−5) (if you divide by 2, you’ll get 1/2 which is not in Z).
However, 2 is irreducible in Z[√−5]. This will become clear in the next section
so 2 is not prime in Z[√−5]]
lectures α is prime if whenever
α is prime if whenever α| βγ then α | β or α | γ
prime in this case is the same as saying it’s not a unit
for ref only
missed some examples of rings in notes but its for reference mostly end of section here
DEF 8.2.1 NORM
defined for Z[i] and Z[√−5]
The norm of α = a + bı ∈ Z[ı] is
N(α) := a² + b²
The norm of β = c + d√−5 ∈ Z[√−5] is
N(β) := a² + 5b²
Note that the norm is always in N.
always posive also
Note here N(α) =|α|²
N(α) =
N(α) =|α|²
In these rings yes in future not always
property of the norm:
multiplicative
N(x)N(y)=N(xy)
Lemma 8.2.2
property of the norm
For all α, β ∈ Z[ı] (or Z[√−5]), we have N(αβ) = N(α) N(β).
not given as lemma in lectures, not proven
proof: Proof. Just recall that |αβ| = |α||β|. For completeness:
N((ac − bd) + (ad + bc)ı) = (ac − bd)^2 + (ad + bc)^2
= (ac)^2 + (bd)^2 −2abcd + (ad)^2 + (bc)^2 +2abcd
= (a^2 + b^2)(c^2 + d^2) = N(a + bı) N(c + dı). □
Exercise 8.2.3. Show that 2 is irreducible in Z[√−5].
skipped?
Lemma 8.2.4. Let α ∈ Z[ı]. Then α = 0 if and only if
Lemma 8.2.4. Let α ∈ Z[ı]. Then α = 0 if and only if N(α) = 0, and α is a unit if and
only if N(α) = 1.
proof
Lemma 8.2.4. Let α ∈ Z[ı]. Then α = 0 if and only if N(α) = 0, and α is a unit if and
only if N(α) = 1.
Proof. Write α = a + bı. Of course, N(α) = 0 if and only if a² + b² = 0 thus if and only
if a = b = 0.
If α is a unit, then αβ = 1 for some β, thus N(α) N(β) = 1 which implies N(α) = 1.
(as Norms are positive integers so -1 or +1)
Conversely, if N(α) = 1, then
1/α= α_conjugate / αα_conjugate
=α_conjugate /¦α¦^2 = α_conjugate /N(α) = α_conujgate
which is still an integer as just flipping sign of b in either Z[i]or Z[√−5])
1/(a + bı) =(a − bı)/(a² + b²) =
(a − bı)/N(α)= a − bı ∈ Z[ı].
(This is just the answer to Exercise 8.1.8 rewritten using the norm.) □
I could ask you:
what are the units in Z[i sqrt -5]
we can use norms
which numbers are + or - 1 here will be units
To find units we determine which elements have multiplicative inverse also in this set ie u is unit if there exists v in the set st uv equals 1
Ie expand and set real part to one and imaginary part to zero
So solving these
a^2 +5b^2 equals 1
The norm must be 1
It’s inverse will also have a norm of one
So possible solutions are only
a equals +1 or -1 for b equals zero
If b was not zero then 5b^2 would be a positive multiple of 5 greater than zero making the norm greater than one
Lemma 8.3.1 (Division algorithm for Gaussiann integers (∈ Z[ı],
Let α, β ∈ Z[ı], where β ̸= 0.
Then there exists q,r ∈ Z[ı] (quotient and remainder)
such that
α = qβ + r and
0 ≤ N(r) < N(β).
-norm here replaces size of integer in EUCLIDS
-norm is an integer so we can use induction
PROOF
Lemma 8.3.1 (Division algorithm for Gaussian integers (∈ Z[ı],
1) compute α/β, a complex number,
(1) compute α/β, a complex number,
α/β = αβ_conjugate/ββ_conjugate
= αβ_conjugate/ N(β)
α/β = A+Bi , A,B in Reals not necessarily integers
2)Choose q = a + bı ∈ Z[ı] as close as possible to A + Bı:
pick a, b ∈ Z s.t.
|a − A| ≤ 1/2, |b − B| ≤ 1/2
Let r = α − qβ ∈ Z[ı].
then
|(α/β)− q|= |(a − A)^2 + (b − B)^2|
≤1/4+1/4=1/2
Therefore,
N(r) = N(α − qβ) = (N(β) )((A-e)^2 +(B-f)^2)
|(α/β)− q|^2N(β) ≤ (1/2)N(β) < N(β).
q and r are not necessarily unique!
Example 8.3.2. Take α = 10 + 10ı, β = 3 − 2ı
α/β
Lemma 8.3.1 (Division algorithm for Gaussian integers (∈ Z[ı],
α/β
= multiply by conjugate
(10 + 10ı)(3 + 2ı)/(3 − 2ı)(3 + 2ı)
=
(30 − 20) + (30 + 20)ı/(3^2 + 2^2) =
(10 + 50ı)/13 .
The nearest Gaussian integer is q = 1 + 4ı (in this case, it is unique). Here
r = (10 + 10ı) − (1 + 4ı)(3 − 2ı) = (10 − 3 − 8) + (10 − 12 + 2)ı = −1.
Indeed, N(r) = 1 < N(β) = 13.
Gaussian integers
in this chapter we dont work with integers anymore, complex numbers with integer parts
Definition 8.3.3
GCD
Let α, β ∈ R integral domain. A greatest common divisor is some element γ ∈ R
such that:
(1) γ is a common divisor, namely γ | α and γ | β;
(2) if δ is a common divisor (δ | α, δ | β), then δ | γ
may not exist, and may not be unique
(everytime we have another common divisor it divides gamma itself)
Example 8.3.4. With this new definition, the greatest common divisors of 4 and 6 in Z
are ±2. In Z we have the luxury of picking the positive greatest common divisor and calling it gcd(a, b)
Lemma 8.3.5.
Let γ be a GCD of α and β in R. Then all GCD δ of α and β are of the form
Let γ be a greatest common divisor of α and β in R. Then all greatest common divisors δ of α and β are of the form δ = uγ for u unit of R.
Theorem 8.3.6 (Bézout’s lemma for Gaussian integers)
Any two Gaussian integers α, β ∈ Z[ı] have a greatest common divisor γ.
Moreover, γ = sα + tβ for some s, t ∈ Z[ı].
Proof
Theorem 8.3.6 (Bézout’s lemma for Gaussian integers)
Any two Gaussian integers α, β ∈ Z[ı] have a greatest common divisor γ.
Moreover, γ = sα + tβ for some s, t ∈ Z[ı].
Essentially the same proof as for Bézout’s Lemma for Z.
If α = β = 0, just take γ = 0, so suppose that one of α, β is not zero. Among all numbers γ = sα + tβ with s, t ∈ Z[ı], pick one with N(γ) minimum possible.
First, we claim that γ | α. By Lemma 8.3.1, α = qγ + r where N(r) < N(γ). Then r = α − qγ = α − q(sα + tβ) = (1 − qs)α − qtβ,
thus N(r) = 0 because of the minimality of N(γ).
So r=0
Hence γ | α.
Similarly, γ | β, so γ is a common divisor.
then γ=sα + tβ
Now if δ is another common divisor, then δ | (sα + tβ) = γ.
Example 8.3.7 Use Euclid’s algorithm to find GCD of two gaussian integers
α = 9 − 2ı and β = −5 + 5ı.
For example, take α = 9 − 2ı and β = −5 + 5ı.
Divide r_0 = α by
r_1 = β giving quotient q_2 and remainder r_2.
N(r_2)<N(β )
N(r_3)<N(r_2)
eventually r_k=0
then r_k-1 is a GCD of α, β
α/β=
(9-2i)(-5-5i)/(-5+5i)(-5-5i)=-55/50 - (35/50)i
= -(11/10)-(7/10)i
not gone through just pointed out
but show you can continue to
The last non-zero remainder is a greatest common divisisor, and we set γ = r_2 =−1 − 2ı. Moreover, working backwards,
γ = −1 − 2ı = α − β(−1 − ı).
The division algorithm in Z[√−5]! Repeat our previous
argument for Z[ı] and find what breaks
The division algorithm does not work in Z[√−5]! Repeat our previous
argument for Z[ı] and find what breaks
Corollary 8.3.9
In Z[ı], every irreducible
In Z[ı], every irreducible is prime.
PROOF
In Z[ı], every irreducible is prime
Let α be irreduciblet with α | βγ, and that α ∤ β.
Let δ be a GCD r of α and β.
α = δϵ:
As α is irreducible, one of δ, ϵ is a unit.
Since δ | β and α ∤ β, δ must be the unit. (BECAUSE …otherwise it would contradict the fact that alpha doesn’t divide beta. If it weren’t a unit it would be a non trivial divisor of alpha and of beta, thus …))
We have determined that a GCD of α and β is 1.
Write it as 1 =
sα + tβ. Then sαγ + tβγ = γ. Since α divides the left hand side, we find that α | γ. This
shows that α is prime.
Theorem 8.3.10 (Fundamental theorem of arithmetic for Gaussian integers) (cont)
If α ∈ Z[ı] is not zero and not a unit, we can write
α = π₁ · · · πᵣ
where each πᵢ
is prime in Z[ı]. Moreover, if
α = σ₁ · · · σₛ
is also a product of primes, then r = s and, after rearranging the factors, we have
σᵢ = uiπᵢ
for some units uᵢ ∈ Z[ı].
PROOF
If α ∈ Z[ı] is not zero and not a unit, we can write
α = π1 · · · πr
where each πi
is prime in Z[ı]. Moreover, if
α = σ1 · · · σs
is also a product of primes, then r = s and, after rearranging the factors, we have
σi = uiπi
for some units ui ∈ Z[ı].
i wont go through proof as
same as the proof of Fundamental theorem of arithmetic for Z by induction on the norm
USES INDUCTION ON N(alpha)
product of prime assumed
Now suppose that N(α) = k + 1. If α is irreducible, it is also prime, and we are done.
Otherwise, suppose that α = βγ where neither β nor γ are units. Then N(β), N(γ) >
1, and since N(α) = N(β) N(γ), we have N(β), N(γ) ≤ k. By induction hypothesis,
both can be written as products of primes, and so does N(α).
For the uniqueness, suppose that α = π1 · · · πr = σ1 · · · σs
. Each irreducible is prime,
thus π1 | σi
for some i. Rearrange the terms so that i = 1. Then σ1 = π1u1 for some
unit u1. Now divide both sides by π1, σ1 and repeat the argument by induction until
there are no primes left (in particular, we will find that r = s)
Example 8.3.11. For instance, 5
FTOA for gaussian integers
For instance, 5 = (2 + ı)(2 − ı) = (1 + 2ı)(1 − 2ı). The two factorisations are equivalent because 2 + ı = ı(2 − ı) and 2 − ı = (−ı)(1 − 2ı).
5 is prime in Z but 5 not prime in Z[i]
as a gaussian integer is not irreducible
(2-i) (2+i) are primes
or can write as a product of primes
(1+2i)(1-2i)
here 1+2i= i(2-i)
this prime is essentially the same prime just differ by unit i
1-2i=-i(2+i)
PROPn 8.4.1.
p∈ Z (ring of integers)
then
p is not primein Z[i]
when
IF p∈ Z (ring of integers)
then
If p is a positive prime of Z with p ≡ 1 (mod 4), then p is not prime
in Z[ı]
and there is α ∈ Z[ı] such that N(α) = p (equivalently, there are a, b ∈ Z such
that p = a^2 + b^2).
when p ≡ 1 (mod 4),
and there is an element s α ∈ Z[ı] such that N(α) = p
ie. prime integers dont remain prime, especially if p ≡ 1 (mod 4),
ONLY ONE DIRECTION
true ot false p∈ Z (ring of integers)
p ≡ 1 (mod 4),
then
p is not prime in Gaussian integers
false!
If p is a positive prime of Z with p ≡ 1 (mod 4), then p is not prime
We need the condition that there is no element in the set with the norm equal to this prime???
For example 13 is congruent to 1 mod 4 but 2 +3i has norm equal to 13
But 13 is not prime in Gaussian …
BECAUSE IT ONLY WORKS IN ONE DIREXTION
IE OUR LEMMA ONLY WORKS TO SHOW IT S NOT PRIME
Remember if irreducible then prime WE CAN SHOW ITS NOT ORIME…
Proposition 8.4.1.
when is a prime in Z not a prime in Z[i]
If p is a positive prime of Z with p ≡ 1 (mod 4), then p is not prime in Z[ı] and there is α ∈ Z[ı] such that N(α) = p (equivalently, there are a, b ∈ Z such
that p = a² + b²
ONLY IN ONE DIRECTION
Example 8.4.2. 17
prime? squares?
17 = N(4 + ı) = (4 + ı)(4 − ı) = 4² + 1²
proof:
If p is a positive prime of Z with p ≡ 1 (mod 4), then p is not prime in Z[ı] and there is α ∈ Z[ı] such that N(α) = p (equivalently, there are a, b ∈ Z such
that p = a² + b²
(we already know that if p ≡ 1 (mod 4) By Corollary 2.3.3, there is x ∈ Z such that x² ≡ −1 (mod p) -1 is a quadratic residue mod p)
So p |(x²+ 1) in Z
=(x+i)(x-i)
however
p does not divide (x+or -i)
(if it did then p(a+bi)=(x +/- i) then pb =+1 or -1 which is impossible
Clearly p does not divide 1 + xı nor 1 − xı, thus it is not prime in Z[ı], so not irreducible either (cant write as elements using units). Because:
N(a+bi) =a²+²
p not prime implies p not irreducible
Therefore, we can write p = αβ where neither α nor β is a unit.
In particular, 1 <N(α), N(β) < N(p) = p²
Since N(α) N(β) = N(p) = p² , we must have N(α) =N(β) = p.
(since not units and bigger than 1, the only way factorisation can happen is if factor p^2 into pxp)
Write α = a + bı: we must have a² + b² = p.
Proposition 8.4.3. If p is a positive prime of Z and p ≡ 3 (mod 4), then
Proposition 8.4.3. If p is a positive prime of Z and p ≡ 3 (mod 4), then p is prime in Z[ı].
PROOF
Proposition 8.4.3. If p is a positive prime of Z and p ≡ 3 (mod 4), then p is prime in
Z[ı].
being irreducible and prime are the same thing in the ring of gaussian integers:
taking a prime number p≡ 3 mod 4
if not prime in gaussian integers there would be a factorisation of non units p = αβ
but then if there is a factorisation then p will be the norm of someone which means it will be the sum of 2 squares but chapter 6 tells us no! because the only primes that are sums of 2 squares are congruent to 1 mod 4!
Proof. Suppose by contradiction that p = αβ for some non-units α, β. Just as in the previous proof, we have 1 < N(α), N(β) < N(p) = p² , thus N(α) = N(β) = p. This
implies that p = a²+ b² which is impossible because −1 is not a square root (or go back
to Corollary 2.3.3) p≡ 1 mod 4 contradiction.
Corollary 8.4.4
The Gaussian primes are exactly:
The Gaussian primes are exactly:
(1) primes of Z of the form 4k + 3, multiplied by ±1 or ±i;
2) elements of the form a + bı where a² + b²
is a prime equal to 2 or of the form 4k + 1.
RE-WRITTEN: the primes of Z[i] are
a)(±p) or (±ip) where p in Z is a prime
b) Norm is a prime N(α) =a² + b² = 2 or 1 mod 4
The Gaussian primes are exactly:
(1) primes of Z of the form 4k + 3, multiplied by ±1 or ±i;
2) elements of the form a + bı where a² + b²
is a prime equal to 2 or of the form 4k + 1
PROOF
Proof. It only remains to check that α = a + bı with N(α) = p, where p = 2 or p ≡ 1 (mod 4) is prime in Z, is a prime. But it is easy to see that α is irreducible:
if α = βγ, then
N(β) N(γ) = p, thus N(β) = 1 or N(γ) = 1,
so one of β, γ is a unit.
which is exactly the definition of being irreducible
remember prime iff irreducible in gaussian integers
in gaussian integers prime means irreducible?
true
in gaussian integers irreducible means prime?
true
Exercise 8.4.5. Write a shorter proof of Fermat’s Christmas theorem using Gaussian
integers.
SKIPPED
Suppose that N = a² + b² for some a, b ∈ Z. Then N = N(α) where α = a + bı ∈ Z[ı]. Let
α = π₁ · · · πᵣ be a prime factorisation of α in Z[ı]. Then N = N(α) N(π₁ ) · · · N(πᵣ ).
It follows at once that if a prime p of the form 4k + 3 divides N, then p | N(πi ) for some i, thus in fact N(πi ) = p2. Therefore, the maximum power of p dividing N has even exponent.
Conversely, write a prime factorisation in Z
N = p α1
1 · · · prαr q21β₁ · · · q2s βs where the pi ’s are either 2 or of the form 4k + 1. For each of them, take πi ∈ Z[ı] such that N(πi ) = pi . Then N = N(π1 )α₁ · · · N(πr )αr N(q1 )β1 · · · N(qs )βs = N(α) = a2 + b2 where α = a + bı = π1α1 · · · πrαr q1β1 · · · qsβs .
Lemma for alpha beta in R if they divide each other
α | β and β |α
IFF
α equals βu for some unit u
proof of :
Lemma 8.1.10. Let α, β ∈ R. Then β | α and α | β if and only if α = uβ for some unit u.
Proof. Suppose that there are γ, δ such that α = βγ and β = αδ.
Then α = αγδ,
that is to say, α(1 − γδ) = 0. Since R is an integral domain, we must have γδ = 1, thus γ is a unit.
Conversely, suppose that α = uβ for some unit u. Then β | α. Let v be the multiplicative inverse of u. Then vα = β, so α | β.
