W-ALG-grupa ilorazowa

[ Pobierz całość w formacie PDF ]
1. Powtórzenie: okre±lenie i przykłady grup
Definicja 1.
Zbiór
G
z okre±lonym na nim działaniem dwuargumentowym
nazywamy
grup¡
, gdy:
G1.
8
x,y,z
2
G
(
x
y
)
z
=
x
(
y
z
);
G2.
9
e
2
G
8
x
2
G
e
x
=
x
e
=
x
;
G3.
8
x
2
G
9
x
−
1
2
G
x
x
−
1
=
x
−
1
x
=
e
.
Poniewa» działanie jest ł¡czne, wi¦c (
ab
)
c
=
a
(
bc
) mo»na pisa¢ po prostu jako
abc
. Z tego samego powodu iloczyn
a
1
a
2
...a
n
mo»na pisa¢ bez nawiasów (ale
uwaga na kolejno±¢ !). Je±li
a
1
=
a
2
=
...
=
a
n
, to taki iloczyn nazywamy
n
−
t¡ pot¦g¡ i oznaczamy
a
n
. Okre±lamy ponadto
a
0
=
e
,
a
−
n
= (
a
n
)
−
1
lub
a
−
n
= (
a
−
1
)
n
.
w i c z e n i e. Wykaza¢, »e dla
a
2
G
,
m,n
2
Z
a
m
a
n
=
a
m
+
n
, (
a
m
)
n
=
a
mn
.
Je±li
a
n
=
e
dla pewnego
n >
0, to najmniejsz¡ z liczb o tej własno±ci nazywamy
rz¦dem elementu a
i oznaczamy
|
a
|
. Je±li
a
n
6
=
e
dla ka»dego
n >
0, to
|
a
|
=
1
.
Je±li grupa ma sko«czon¡ liczb¦ elementów, to nazywamy j¡
grup¡ sko«czon¡
.
Liczb¦ elementów grupy nazywamy
rz¦dem grupy
; oznaczenie:
|
G
|
.
w i c z e n i e. Je±li
a
n
=
e
, to
n
dzieli si¦ przez
|
a
|
.
Je»eli
G
spełnia oprócz G1—G3 jeszcze:
G4.
8
x,y
2
G
x
y
=
y
x
,
to nazywamy j¡
grup¡ abelow¡
.
Tradycyjnie działanie w grupie abelowej oznaczamy + i stosujemy nast¦puj¡c¡
terminologi¦:
·
+
mno»enie
dodawanie
iloczyn
suma
jedynka
zero
odwrotny
przeciwny
pot¦ga
krotno±¢
e
lub 1
0
a
−
1
−
a
a
n
na
Przykłady.
1. Zbiór elementów dowolnego ciała rozpatrywany z dodawaniem tworzy grup¦
abelow¡, np.Q
,
R
,
C.
2. Zbiór elementów niezerowych dowolnego ciała rozpatrywany z mno»eniem
tworzy grup¦ abelow¡, np.Q
,R
,C
.
3. ZbiórZz dodawaniem tworzy grup¦ abelow¡.
4. ZbiórZ
n
reszt z dzielenia przez
n
z działaniem dodawania modulo
n
tworzy
grup¦ abelow¡. Jest to grupa sko«czona rz¦du
n
.
5.Q
p
=
{
p
n
|
m,n
2
Z
}
, gdzie
p
jest liczb¡ pierwsz¡, jest addytywn¡ grup¡
abelow¡.
6. ZbiórC
n
pierwiastków stopnia
n
z 1 jest grup¡ multiplikatywn¡ sko«czon¡
rz¦du
n
.
Przypomnienie
.Pierwiastkamistopnia
n
z1s¡liczby
cos
2
k
,
n
+isin
2
k
"
k
=
k
=0
,
1
,...,n
−
1
n
Mo»najezapisa¢wpostaciwykładniczej:
e
i
2
k
n
,
k
=0
,
1
,...,n
−
1
7. Niech b¦dzie zbiorem, a
S
() niech oznacza zbiór odwzorowa« odwracal-
nych
−!
. Zbiór
S
() z działaniem składania tworzy grup¦.
1
 8. W szczególno±ci, gdy =
{
1
,
2
,...,n
}
,to
S
() jest grup¡ permutacji
n
-elementowych.
Nazywamy j¡
grup¡ symetryczn¡
i oznaczamy
S
n
. Grupa
S
n
jest sko«czona;
|
S
n
|
=
n
!. Dla
n >
2 grupy
S
n
s¡ nieabelowe.
9. NiechKb¦dzie dowolnym ciałem. Zbiór macierzy nieosobliwych o wyrazach
zKz działaniem mno»enia macierzy jest grup¡. Oznaczamy j¡
GL
(
n,K
) lub
GL
n
(
K
) i nazywamy
pełn¡ grup¡ liniow¡
. Jedynk¡ tej grupy jest macierz jed-
nostkowa; elementem odwrotnym do macierzy
A
jest macierz odwrotna
A
−
1
.
W
GL
n
(
K
) mo»na rozpatrywa¢ nast¦puj¡ce podzbiory:
a)
SL
n
(
K
) =
{
A
2
GL
n
(
K
) : det
A
= 1
}
;
b)
D
n
(
K
) =
{
A
2
GL
n
(
K
) :
A
jest diagonalna
}
;
c)
T
n
(
K
) =
{
A
2
GL
n
(
K
) :
A
jest górnotrójk¡tna
}
;
d)
UT
n
(
K
) =
{
A
2
T
n
(
K
) :
A
ma jedynki na przek¡tnej
}
.
Grupy te nosz¡ nazwy:
specjalna grupa liniowa, grupa diagonalna, grupa trój-
k¡tna, grupa unitrójk¡tna
.
Uwaga
. Rozpatruje si¦ równie» struktury ubo»sze (tzn. maj¡ce mniej aksjoma-
tów) od grupy.
Definicja 2.
Zbiór
G
z okre±lonym na nim działaniem dwuargumentowym
nazywamy
półgrup¡
, gdy działanie to jest ł¡czne, tj.
8
x,y,z
2
G
(
x
y
)
z
=
x
(
y
z
)
.
Poj¦cie półgrupy okazało si¦ bardzo u»yteczne, np. w teorii automatów.
2. Podgrupy
Je±li podzbiór
H
grupy
G
jest zamkni¦ty ze wzgl¦du na mno»enie (tj.
a,b
2
H
)
ab
2
H
), to ograniczenie operacji mno»enia do
H
jest działaniem na
H
.
Je»eli wzgl¦dem tego działania
H
jest grup¡, to mówimy, »e
H jest podgrup¡ G
i oznaczamy
H
¬
G
. Je±li
H
¬
G
i
H
6
=
G
, to piszemy
H < G
.
Lemat 1.
Nast¦puj¡ce warunki s¡ równowa»ne:
a) H
¬
G;
b)
8
a,b
2
H
ab
−
1
2
H;
c)
8
a,b
2
H
ab
2
H
^
a
−
1
2
H.
Warunki te mo»na zapisa¢ inaczej stosuj¡c poj¦cie
iloczynu kompleksowego
pod-
zbiorów grupy
G
:
AB
de
=
{
ab
:
a
2
A,b
2
B
}
i przyjmuj¡c:
A
−
1
de
=
{
a
−
1
:
a
2
A
}
dla
A
G
i
B
G
.
Lemat 2.
Nast¦puj¡ce warunki s¡ równowa»ne:
a) H < G;
b) HH
H
^
H
−
1
H.
Przykłady.
1.Z
<
Q
p
<
Q
<
R
<
C. Zauwa»my, »eZ=
T
Q
p
.
.
3.C
p
<
C
p
2
< ... <
C
p
1
. PonadtoC
p
1
=
S
<
R
<
C
2.Q
C
p
n
.
4. Dla
n
­
2:
SL
n
(
K
)
<
GL
n
(
K
),
D
n
(
K
)
<
T
n
(
K
),
UT
n
(
K
)
<
T
n
(
K
)
<
GL
n
(
K
)
.
2
3. Iloczyny proste grup
Niech
G,H
b¦d¡ dowolnymi grupami. Wtedy w zbiorze
G
×
H
mo»na okre±li¢
działanie wzorem:
(
g,h
)
(
g
0
,h
0
) = (
gg
0
,hh
0
)
dla dowolnych (
g,g
0
)
,
(
h,h
0
) ze zbioru
G
×
H
. Zbiór
G
×
H
z tym działaniem two-
rzy grup¦, której elementem neutralnym jest (
e
G
,e
H
). Nazywamy j¡
iloczynem
prostym
grup
G
i
H
. Zbiory
G
0
=
{
(
g,e
H
) :
g
2
G
}
i
H
0
=
{
(
e
G
,h
) :
h
2
H
}
s¡ podgrupami grupy
G
×
H
i oczywi±cie s¡ izomorficzne odpowiednio z
G
i
H
.
U w a g a. W przypadku grup abelowych mówimy raczej:
suma prosta
grup.
4. Zbiory generuj¡ce
Jasne jest, »e przekrój dowolnego zbioru podgrup danej grupy jest tak»e pod-
grup¡.
Niech
M
— dowolny podzbiór grupy
G
. Przekrój (
M
) wszystkich podgrup gru-
py
G
zawieraj¡cych
M
nazywamy
podgrup¡ generowan¡ przez M
, a zbiór
M
—
zbiorem generatorów
dla (
M
). Grup¦ maj¡c¡ sko«czony zbiór generatorów
nazywamy
sko«czenie generowan¡
.
Twierdzenie 1.
Je±li M jest podzbiorem grupy G, to
(
M
) =
{
a
"
1
1
a
"
2
2
···
a
"
m
:
a
i
2
M,"
i
=
±
1
,m
= 1
,
2
,...
}
.
D o w ó d. Oznaczmy praw¡ cz¦±¢ przez
H
. Poniewa» (
M
) zawiera wszystkie
a
i
2
M
, wi¦c (
M
)
­
H
. Z drugiej strony, je±li
x,y
2
H
, to
xy
−
1
2
H
, wi¦c
H
jest podgrup¡, oczywi±cie zawieraj¡c¡
M
. St¡d
H
(
M
) i w ko«cu
H
= (
M
).
Przykłady.
. Uwaga: je±li zbiór
M
okre±lony jest w postaci
M
=
{
...
:
...
}
,
to b¦dziemy pisa¢ (
...
:
...
) zamiast (
{
...
:
...
}
).
1.Z= (1).
2.Z
n
= (1(mod
n
)).
3.Q= (
n
:
n
= 1
,
2
,...
).
4.Q
= (
−
1
,
2
,
3
,
5
,
7
,
11
,...
).
5.C
n
= (
"
n
)
,"
n
= cos
2
n
+ i sin
2
n
= e
i
2
n
.
6.C
p
1
= (
"
p
m
:
m
= 1
,
2
,...
).
5. Funkcja Eulera
Definicja 3.
Funkcj¦
'
Eulera przyporz¡dkowuje ka»dej liczbie naturalnej licz-
b¦ liczb wzgl¦dnie z ni¡ pierwszych nie wi¦kszych od niej samej.
Przykład.
Pocz¡tkowe warto±ci funkcji Eulera:
n
1
2
3
4
5
6
7
8
9
10
11
12
'
(
n
)
1
1
2
2
4
2
6
4
6
4
10
4
Funkcja Eulera odgrywa du»¡ rol¦ w teorii liczb. Ma te» istotne zastosowania w
kryptografii w badaniach nad zło»ono±ci¡ szyfrów.
Własno±ci funkcji
'
.
Dla dowolnej liczby pierwszej
p
i
k
2
Njest
'
(
p
k
) =
p
k
−
p
k
−
1
; w szczegól-
no±ci
'
(
p
) =
p
−
1.
1.
2.
Je»eli liczby całkowite
m,n
s¡ wzgl¦dnie pierwsze, to
'
(
mn
) =
'
(
m
)
'
(
n
).
3
 3.
Je»eli
n
nie ma wielokrotnych dzielników pierwszych, tj.
n
=
p
1
p
2
...p
k
gdzie
liczby
p
i
s¡ pierwsze i parami ró»ne (
i
= 1
,...,k
), to
'
(
n
) = (
p
1
−
1)(
p
2
−
1)
...
(
p
k
−
1).
Dla dowolnej liczby całkowitej
n
zachodzi:
P
m
|
n
4.
'
(
m
) =
n
(sumowanie prze-
biega wszystkie dzielniki liczby
n
).
Je»eli
n
=
Q
i
=1
p
k
i
5.
jest rozkładem liczby
n
na czynniki pierwsze to
i
k
Y
'
(
p
k
i
)
'
(
n
) =
i
=1
Z tych własno±ci wynika te» wzór
'
(
n
) =
n
1
−
p
1
1
−
p
2
...
1
−
p
k
,
gdzie
p
1
,p
2
,...,p
k
s¡ wszystkimi czynnikami pierwszymi liczby
n
liczonymi bez
powtórze«.
Ostatniwzórmo»nawyprowadzi¢bezpo±redniozzasadywł¡czania-wył¡czania.
Twierdzenie2.(zasadawł¡czania-wył¡czania)
Niech
|
S
|
oznaczaliczb¦elementówzbio-
ruS.Je»eliA
1
,A
2
,...,A
r
s¡zbioramisko«czonymi,to
|
S
r
i
=1
A
i
|
=
P
r
i
=1
|
A
i
|−
P
r
i,j
=1
i
6
=
j
|
A
i
\
A
j
|
+
+
P
r
i,j,k
=1
i
6
=
j,i
6
=
k,j
6
=
k
|
A
i
\
A
j
\
A
k
|
+
···
+(
−
1)
r
−
1
|
A
1
\
A
2
\···\
A
r
|
.
Załó»my,»eliczba
n
manast¦puj¡cyrozkładnaczynnikipierwsze:
n
=
p
e
1
1
p
e
2
2
...p
e
r
r
.
iniech
A
i
b¦dziezbioremwszystkichliczb
m
2 {
1
,
2
,...,n
}
takich,»e
p
i
dzieli
m
.Mo»na
wykaza¢,»e
|
A
i
|
=
n
p
i
,
|
A
i
\
A
j
|
=
n
p
i
p
j
dla
i
6
=
j,
|
A
i
\
A
j
\
A
k
|
=
n
p
i
p
j
p
k
dlaró»nych
i,j,k,
itd.Poniewa»
'
(
n
)=
n
−|
S
r
i
=1
A
i
|
,wi¦cstosuj¡czasad¦wł¡czania-wył¡czaniaipowy»sze
równo±ciotrzymujemy:
'
(
n
)=
n
−
X
n
p
i
+
X
n
p
i
p
j
p
k
+
...
=
n
1
−
1
p
1
1
−
1
p
2
...
1
−
1
p
k
n
p
i
p
j
−
6. Podgrupy cykliczne
Podgrupa (
a
) generowana przez jeden element
a
nazywa si¦
cykliczn¡
. Z twier-
dzenia o podgrupie generowanej przez zbiór wynika, »e
(
a
) =
{
a
n
:
n
= 0
,
±
1
,
±
2
,...
}
.
Dwa pierwsze przykłady wy»ej pokazuj¡, »eZiZ
n
s¡ grupami cyklicznymi.
Twierdzenie 3.
(i) Ka»da podgrupa grupy cyklicznej jest cykliczna;
(ii) Niech
(
a
)
b¦dzie grup¡ cykliczn¡ rz¦du n. Element a
k
generuje podgrup¦
rz¦du
n
nwd(
k,n
)
;
(iii) Niech
(
a
)
b¦dzie grup¡ cykliczn¡ rz¦du n a l – dodatnim dzielnikiem liczby
n. Wtedy
(
a
)
zawiera '
(
l
)
elementów rz¦du l;
(iv) Grupa cykliczna rz¦du n zawiera '
(
n
)
generatorów. Generatorami s¡ te
i tylko te elementy a
r
dla których
nwd(
r,n
) = 1
.
4
 Dowód (i) (dla grupy sko«czonej). Niech (
a
) b¦dzie cykliczn¡ grup¡ rz¦du
n
,
H
6
=
{
e
}
jej podgrup¡. Niech
m
b¦dzie najmniejsz¡ liczb¡ całkowit¡ o własno-
±ci:
a
m
2
H,
0
< m < n.
Oczywi±cie (
a
m
)
H
. Wyka»emy, »e naprawd¦ (
a
m
) =
H
. We¹my dowolny
element z
H
; musi on mie¢ posta¢
a
k
,
0
¬
k < n
. Podzielmy
k
przez
m
:
k
=
mq
+
r,
0
¬
r < m
. Wtedy
a
r
=
a
k
(
a
m
)
−
q
2
H.
Ze sposobu wyboru liczby
m
wynika, »e
r
= 0, a wi¦c
a
k
2
(
a
m
). Dla grupy
niesko«czonej dowód jest analogiczny.
Dowód (iii). Niech
n
=
dl
. Na mocy (ii)
|
a
k
|
=
l
wtedy, i tylko wtedy, gdy
nwd(
k,n
) =
d
. Zatem liczba elementów rz¦du
l
jest liczb¡ tych
k
¬
n
, »e
nwd(
k,n
) =
d
. Ale gdy
k
=
dh
, to nwd(
k,n
) =
d
,
nwd(
dh,dl
) =
d
,
nwd(
h,l
) = 1.
Przykł
ad
.
Rozwa»my grup¦C
n
pierwiastków stopnia
n
z 1, generowan¡ prz
e
z
"
1
= e
i
2
n
. Przykładowo we¹my
n
= 12; wtedy generatorem jest liczba e
i
6
.
Grupa ma 12 elementów:
C
12
=
{
e
k/
6
:
k
= 0
,
1
,
2
,...,
11
}
.
Dzielnikami 12 s¡ 1, 2 ,3, 4, 6, 12.
l
1
2
3
4
6
12
'
(
l
)
1
1
2
2
2
4
e
e
i
2
3
,
e
i
4
3
e
i
2
,
e
i
3
2
e
i
3
,
e
i
5
3
e
i
6
,
e
i
5
6
,
e
i
7
6
,
e
i
11
6
liczby
1
Przykład.
Jak wiadomo, mno»enie przez liczb¦ e
i
'
mo»na interpretowa¢ jako
obrót płaszczyzny zespolonej o k¡t
'
. Grup¦C
n
mo»emy wi¦c zast¡pi¢ grup¡
O
n
obrotów płaszczyzny, generowan¡ przez obrót
o
2
/n
. Poprzedni przykład
”transponujemy” nast¦puj¡co: dla
n
= 12 generatorem grupy obrotów jest obrót
o k¡t
6
. Grupa ma 12 elementów:
O
12
=
{
o
k/
6
:
k
= 0
,
1
,
2
,...,
11
}
.
Dzielnikami 12 s¡ 1, 2 ,3, 4, 6, 12.
l
1 2 3 4 6 12
'
(
l
) 1 1 2 2 2 4
obroty
id o
o
2
/
3
,o
4
/
3
o
/
2
,o
3
/
2
o
/
3
,o
5
/
3
o
/
6
,o
5
/
6
,o
7
/
6
,o
11
/
6
Twierdzenie 4. (podstawowe teorii grup abelowych)
Je»eli G jest grup¡
abelow¡ generowan¡ przez sko«czenie wiele elementów, to G jest sum¡ prost¡
grup cyklicznych.
Wniosek 1.
Ka»da sko«czona grupa abelowa jest sum¡ prost¡ grup cyklicznych
postaci C
p
r
, gdzie p jest liczb¡ pierwsz¡, a r
2
N
.
7. Homomorfizmy
Niech
G,G
0
b¦d¡ grupami. Odwzorowanie
f
:
G
−!
G
0
nazywamy
homomorfi-
zmem
, gdy dla dowolnych
a,b
2
G
spełniony jest warunek:
f
(
ab
) =
f
(
a
)
f
(
b
)
.
Homomorfizm ró»nowarto±ciowy nazywamy
monomorfizmem
; je»eli obrazem
G
jest cała
G
0
, to mówimy o
epimorfizmie
. Homomorfizm, który jest monomorfi-
zmem i epimorfizmem nazywamy
izomorfizmem
. Je±li
G
=
G
0
, to homomorfizm
nazywamy
endomorfizmem
; endomorfizm, który jest izomorfizmem, nazywamy
automorfizmem
.
5
  [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

diabelki.xlx.pl