exam Flashcards
Group
[G1]
(xy)z = x(yz)
[G2]
ex=x=xe
[G3]
xy=e=yx , ∀x, ∃y
[abelian]
xy=yx , ∀x,y
identity element e is unique
if e’x=x or xe’=x for some x∈G and any e’∈G then the identity element is e’.
inverse element of x
unique y∈G : xy=e=yx
y=x^(-1)
show that xy=e
inverse element properties
(a^(-1))^(-1) = a
(a1…an)^(-1) = an^(-1)…a1^(-1)
(a^n)^(-1) = a^(-n) = (a^(-1))^n
x^0=
e
a and b “congruent modulo N”
N|a-b
a≡bmodN
equivalence relation
[reflexivity]
a≡amodN
[symmetry]
a≡bmodN ⟺ b≡amodN
[transitivity]
a≡bmodN and b≡cmodN
⟹ a≡cmodN
residue class of a modulo N
amodN := {b∈Z| b≡amodN}
amodN=bmodN
⟺a≡bmodN
a=qN+r
⟹a≡rmodN
⟹amodN=rmodN
amodN
= a_
= {a+Nk|k∈Z}
a is a “unit modulo N”
∃b_ ∈ Z/NZ :
a_ * b_ = 1_
gcd(a,N) = 1
(Z/NZ)^X
subset of Z/NZ containing all units modulo N
Euler’s totient function
ρ(N) = #(Z/NZ)^X
Euler’s theorem
for all a_∈ (Z/NZ)^X,
(a_)^ρ(N) = 1_
Fermat’s little theorem
if p is prime,
(amodp)^p = amodp
subgroup H of G
H<=G
H is subset of G and group law and unit element are the same.
subgroup criterion
[H1]
e∈H
[H2]
x,y∈H ⟹ x*y ∈H
[H3]
x ∈H ⟹ x^(-1) ∈H
Lagrange
H is a subgroup of finite G
⟹
#H | #G
ord(x)
- minimum m>0 such that x^m=e
- no such m exists ⟹ ord(x)=∞
ord(x^(-1))
- ord(x) = ord(x^(-1))
- ord(x)<∞
⟹
<x>={x,x^2,...,x^ord(x)=e}
-
</x>
ord(x)<∞
<x> = {x , x^2, ..., x^(ord(x)) = e}
</x>
<x></x>
= ord(x)
G<∞
⟹ ord(x) < ∞ ⟹ ord(x)|#G
x^n=e
⟹ ord(x) | n
G “cyclic”
if G=<g> for some g∈G
g is then the "generator" of G</g>
ord(g) = #G
⟺ G is cyclic and generated by g
, for finite G
homomorphism
f:X->Y : f(xy) = f(x)f(y)
homorphism properties
- f(e1) = e2
- f(x^(-1)) = f(x)^(-1)
- f isomorphism ⟹ f^(-1) isomorphism
- g:G2->G3 homomorphism -> g∘f homomorphism
, for f:G1->G2
isomorphism
bijective homomorphism
isomorphism properties
- G1 abelian ⟺ G2 abelian
- ord(g1) = k ⟺ f(x) of order k
- # G1 = #G2
- the restriction of f to any H1<=G1 is an isomorphism
kernel of f
given homomorphism f:(X,ex)->(Y,ey)
ker(f) := {x∈X | f(x) = ey}
kernel properties
- ker(f) is subgroup of X
- f injective ⟺ ker(f) = {ex}
CHINESE REMAINDER THEOREM
- take N,M ∈ Z>0: Gcd(N,M)=1
- then the map f:Z/NMZ -> Z/NZ X Z/MZ : amodNM ↦ (amodN, amodM)
is a well-defined group isomorphism
ρ(n)
for n∈Z>0: n=p1^(e1) * … * pk^(ek) where pi prime.
ρ(n) = ∏ (pi-1)pi^(ei-1) = n∏ (1-1/pi)
* product taken over prime divisors of n
Euler’s totient function properties
φ(NM) = φ(N) * φ(M)
for all positive integers N,M with gcd(N,M) = 1
S↓(Σ)
Σ non-empty set
S↓(Σ) := set of all bijections from Σ to Σ
symmetric group on the set Σ
(S↓(Σ) , ∘ , idΣ)
Cayley’s theorem
every group G is isomorphic to a subgroup of S↓(G)
k-cycle properties
δ = (i1 … ik) ∈S↓(n)
- every δ can be written as a product δ = δ1* … * δr where δi are pairwise disjoint cycles of length >=2
(unique aside from order of δi)
- δ^(-1) = (ik … i1)
- ord(δ) = k
- δ1, … , δr pairwise disjoint ⟹ (δ1 … δr)^n = δ1^n … δr^n
- δ1, … , δr pairwise disjoint with lengths Li>=2 ⟹ ord(δ1 … δr) = lcm(L1,…,Lr)
- every permutation can be written as a product of transpositions
sign of permutation
ε(δ) := ∏{1<=i<j<=n} (δ(i)-δ(j))/(i-j)
= (-1)^(ΣLi-1)
= +- 1
ρ ∘ ( a1 … al) ∘ ρ^(-1)
= (ρ(a1) … ρ(al))
for any ρ∈S↓(n) and any l-cycle (a1 … al) ∈S↓(n)
S↓(n)
= n!
if a permutation can be written as a product of transpositions as 𝓣1…𝓣L and γ1…γk
⟹ L = Kmod2
