Chapter 1 Flashcards
Fundamental Theorem of Arithmetic
Let n≥1 be a natural number. Then the following hold.
(1) n can be written as a product of its primes n = p₁p₂…pₙ
(2) This factorisation is unique
Gaussian Integer
A complex number whose real and imaginary parts are both integers
ℤ[i] = {a+bi | a,b∈ℤ}
Theorem I.2.1 (factors of primes)
Suppose p is prime and a,b∈ℤ if p|ab then p|a or p|b
Corollary of Theorem I.2.1
Suppose p is prime and a₁,a₂,…,aₙ∈ℤ if p|a₁a₂…aₙ then there exists i such that p|aᵢ
Euclidean Algorithm on a,b
- divide a by b. a = cb + r
- We know hcf(a,b)=hcf(b,r)
- repeat with b and r until no remainder
Bezouts Lemma
if h = hcf(a,b) then there exists x,y∈ℤ s.t. h=ax+yb
Division Theorem
Let a and d be natural numbers. Then there are integers q and r such that
a= qd+r
does an analogue of the FTA hold for gaussian integers?
yes
ring
A set R of complex numbers is a ring if
(i) x+y, x-y, xy ∈R for all x,y∈R
(ii) 0,1∈R
a is a factor of b in R (definition)
Let a,b∈R. We say that a is a factor of b in R, a|b, if there exists z∈R s.t. b=az
a|b <=>
b/a∈R
b=az
does a|0 ?
true
if 0|a then
a=0
does 1|a
true always
Lemma I.4.1 (factors in rings)
Suppose that R is a ring and that a,b,c∈R. If a|b and a|c then a|(b+c).
unit
An element u of a ring R is a unit in R if u|1 in R. That is if 1/u ∈ R.
what is always a unit and never a unit?
1 is always a unit
0 is never a unit
Is it always possible to divide by a unit?
yes. x/u = x * 1/u ∈ R
units of ℤ
1 -1
units of the rationals
every non-zero element of the rationals is a unit
units of ℤ[i]
1,-1,i,-i
associate
Let x be an element of a ring R. The associates of x are the elements ux where u is a unit of R.
Associate rules:
- x is always an associate of itself
- if x is an associate of y then y is an associate of x
- if x is an associate of y and y is an associate of z then x is an associate of z
i. e. associate is an equivalence relation
equivalence relation
a~a (reflexive)
if a~b then b~a (symmetric)
if a~b and b~c then a~c (transitive)
Lemma I.6.1 (factors and associates)
Suppose that a,b,a’,b’ are members of a ring R with a’ an associate of a and b’ an associate of b. Then a|b => a’|b’
Lemma I.7.1 (factors of x)
suppose that x is an element of a ring R. Then each unit of R and each associate of x is a factor of x.
irreducible
A non-zero non-unit element of a ring R is irreducible in R if the only factors of x in R are the associates of x and the units of R
irreducibles in ℤ
the prime numbers and their negatives
if x if irreducible then…
all of its associates are irreducible
Are 0 and units of R irreducible?
no
The norm of α
N(α)=αα*
for ℤ[i] N(α) is given by
N(α) = a² + b²
N(α)=0 <=> α=0
true
Lemma I.8.1 (rules for norms)
Let α,β∈ℤ[i]. Then the following hold.
(i) α|β in ℤ[i] => N(α)|N(β) in ℤ
(ii) if α is a unit <=> N(α)=1
(iii) N(α) is irreducible in ℤ => α is irreducible in ℤ[i]
Lemma I.8.2 (units of ℤ[i])
The units of ℤ[i] are 1,-1,i and -i
How to determine the factors of n in a ring R=ℤ[i]
- suppose α|n then there exists β∈ℤ[i] s.t. n=αβ
- N(n) = N(αβ) = N(α)N(β). since the norms are non-negative integers we have the following (however many factors N(n) has) cases
- N(α) = 1 => α is a unit
- N(α) = (factor of n). Write, α= a+bi a,b∈ℤ. Then, a²+b²=n. Since a,b∈ℤ we can extract the possibilities for (a,b). Check which of these are actually factors. by checking n/(a+bi)∈ℤ[i]. If it is a factor then all of its associates are factors.
- N(α) = (partner factor of n). => N(β) = (factor of n) => β = associate of the factors calculated above => α is an associate of n/β
- N(α) = N(n). Then N(β) = 1 => β is a unit => α is an associate of n
Euclidean Ring
A ring R of complex numbers is a Euclidean Ring (ER) if
(i) |a|²∈ℤ for all a∈R
(ii) given any fraction of the form z=a/d with a,d∈R, d not 0. Then there exists a q∈R s.t. |z-q|²<1
i. e. z has distance less than 1 some some member of R
Theorem I.9.1 . example of a ER (1)
The ring ℤ is a ER
Theorem I.9.2 example of a ER (2)
The ring ℤ[i] is a ER
Lemma I.9.3. units in ER.
Let R be a euclidean ring. Let d∈R and suppose |d|²=1. The d is a unit.
Theorem I.9.4. Analogue of FTA in ER.
Let R be a ER and a∈R. We suppose that a is non-zero non-unit. The a is a product of irreducibles.
Highest Common Factor in a Ring
Let R be a ring and a,b∈R. A highest common factor is an element h∈R with the properties
(i) h|a, h|b
(ii) for each c∈R if c\a and c\b then c|h
HCF(a,b) denotes the set of all highest common factors
Highest Common Factor in a Ring (described)
h is a common factor of a and b where every common factor of a and b is a factor of h. The highest common factor is the set of all these h’s.
If h is a common factor then what do we know about other common factors
any associates of h are also common factors
Can HCF(a,b) be empty?
yes (except in the integers)
How to find HCF(a,b)
- find all the common factors of a and b
- for each number:
- check if its divisible by all the other values: if its not then don’t add to HCF(a,b), if it is do add to HCF(a,b)
Theorem I.10.1. The Euclidean Algorithm in a ER
Let R be a Euclidean ring and let a,b be non-zero elements of R. Then:
(i) the numbers a and b have a HCF (i.e. the HCF is non-empty)
(ii) if h is a HCF of a and b then there exists x,y∈R such that h = xa + yb
Prime
Let R be a ring. A non-zero non-unit element p∈R is prime if for all a,b∈R we have that p|ab => p|a or p|b
Lemma I.11.1. induction of definition of p.
Let p∈R be a prime. If a₁,a₂,…,aₙ∈R and p|a₁a₂…a then there exists an i s.t. p|aᵢ
Lemma I.11.2. prime/irreducible.
Let p∈R be prime. Then p is irreducible.
Theorem I.11.3
Let p be an element of a Euclidean ring R. Then,
p is irreducible <=> p is prime
Unique Factorisation Domain (UFD)
A UFD is a ring R with the property that for each a∈R with a a non-zero non-unit
(i) There is exists irreducibles p₁, … , pₙ s.t. a=p₁…pₙ
(ii) If q₁,…,qₘ are also irreducibles with a = q₁…qₘ then m=n and there is a 1-1 correspondence between the ps and the qs s.t. corresponding numbers are associate.
Theorem I.12.1. ERs and UFDs
A Euclidean Ring is a unique factorisation domain
Lemma (after ER => UFD)
Let R be a ER and n∈ℕ and suppose that p₁,…,pₙ are irreducibles in R, Suppose that q₁,…,qₘ are irreducibles and u is a unit such that p₁…pₙ=uq₁…qₘ. Then n=m and there is a bijection σ: {1,…,n}->{1,…,m} such that for all 1≤i≤n pᵢ is associate to q_σ₍ᵢ₎
