PDF(2)

암호수학II INI230 NOTE05
정규부분군과 잉여군
인터넷미디어공학부
김상진
©Copyright 2004.
1
교육목표
„
„
„
정규부분군
단순군
잉여군
2/18
정규부분군
„
„
„
정의 5.1. 군 G의 부분군 N이 다음 조건을 만족할 때, N를 군 G의
정규부분군(normal
subgroup)이라 한다.
정규부분군
모든 g∈G에 대하여 gN = Ng
N이 G의 정규부분군임을 N◁G 또는 G▷N으로 표기한다.
예5.1) 군 G에서 모든 g∈G에 대해 g{e} = {g} = {e}g이며,
gG = G = Gg이므로 {e}◁G, G◁G이다.
정리 5.1. 아벨군 G의 모든 부분군은 정규부분군이다.
(증명)
증명 아벨군에서는 gN = Ng가 항상 성립하므로 정리가 성립한다.
3/18
정규부분군 - 계속
„
정리 5.2. 군 G의 부분군 N에 대하여 |G:N| = 2이면 N◁G이다.
(증명)
증명 N은 부분군이므로 모든 n∈N에 대해 nN = N = Nn이다. 이 때
|G:N| = 2이면 임의의 x∈G-N에 대해 xN∩N = Nx∩N = Ø이다.
z
„
a∈xN이면 임의의 n∈N에 대해 a = xn이다. 그런데 N은 군이므로
n-1∈N이며, an-1 = x∈N이다. 그러나 이것은 모순이므로
xN∩N = Ø이다.
따라서 G = Nx∪N = N∪xN이며, xN = Nx이다. 그러므로 모든 g∈G에
대하여 gN = Ng이므로 N◁G이다.
정의 5.2. 군 G의 임의의 부분집합 S와 원소 g∈G에 대해 두 집합 g-1Sg,
gSg-1는 각각 다음과 같이 정의된다.
g-1Sg = {g-1xg|x∈S}, g-1Sg = (g-1S)g = g-1(Sg)
gSg-1 = {gxg-1|x∈S}, gSg-1 = (gS)g-1 = g(Sg-1)
4/18
정규부분군 - 계속
„
정리 5.3. 군 G의 부분군 N에 대하여 다음 명제는 서로 동치이다.
z (1) 모든 g∈G에 대하여 gN = Ng, 즉 N◁G 이다.
z (2) 모든 g∈G에 대하여 g-1Ng = N이다.
z (3) 모든 g∈G에 대하여 g-1Ng⊆N이다.
z (2') 모든 g∈G에 대하여 gNg-1 = N이다.
z (3') 모든 g∈G에 대하여 gNg-1⊆N이다.
(증명)
증명
z (1)⇒ (2): 모든 g∈G에 대하여 gN = Ng이면 g-1Ng = g-1gN = N이다.
z (2)⇒ (1): 모든 g∈G에 대하여 g-1Ng = N이면 gN = gg-1Ng = Ng이다.
z (2)⇒ (3): 당연하다.
z (3)⇒ (2): 모든 g∈G에 대하여 g-1Ng⊆N이면 모든 g∈G에 대하여
gNg-1⊆N이다. 따라서 g-1(gNg-1)g = N⊆g-1Ng이다. 그러므로
(3)⇒ (2) 가 성립한다.
5/18
정규부분군 - 계속
„
정리 5.4. 군 G에서
Z(G) = {x∈G | 모든 g∈G에 대하여 xg = gx}
z (1) Z(G)◁G이고 또 N이 N⊆Z(G)인 G의 부분군이면 N◁G이다.
z (2) G가 아벨군일 경우에만 Z(G) = G이다.
(증명)
증명
z (1) 먼저 e∈Z(G)이므로 Z(G) ≠ Ø이다. 또한 x, y∈Z(G)이면 모든
g∈G에 대하여 xg = gx이고 yg = gy이다. 따라서 다음이 성립한다.
(xy)g = x(yg) = x(gy) = (xg)y = (gx)y = g(xy),
g = g ⇒ g = gxx-1 ⇒ g = xgx-1 ⇒ x-1g = x-1xgx-1 ⇒ x-1g = gx-1
즉, x, y∈Z(G)이면 xy, x-1∈Z(G)이다. 따라서 정리 3.2에 의해 Z(G)는
G의 정규부분군이다. N이 N⊆Z(G)인 G의 부분군이면 모든 g∈G와
x∈N에 대해 g-1xg = x∈N 이므로 정리 5.3에 의해 N◁G이다.
z (2) 당연히 성립한다.
6/18
정규부분군 - 계속
„
정의 5.2. 군 G의 정규부분군 Z(G)를 G의 중심(center)이라
하고,
중심
Z(G)에 속하는 원소를 G의 중심원(central
element)이라 한다. 여기서
중심원
Z(G) = {x∈G | 모든 g∈G에 대하여 xg = gx}
= {x∈G | 모든 g∈G에 대하여 g-1xg = x}
= {x∈G | 모든 g∈G에 대하여 gxg-1 = x}
이다.
7/18
정규부분군 - 계속
„
정리 5.5. 군 G의 두 부분군 H와 N에 대해 다음이 성립한다.
z (1) N◁G, N⊆H이면 N◁H이다.
z (2) N◁G이면 HN = NH이므로 HN은 G의 부분군이고,
H∩N◁H, N◁HN이다.
z (3) H◁G, N◁G이면 H∩N◁G, HN◁G이다.
(증명)
증명
z (1) N⊆H이면 N은 H의 부분군이므로 N은 H의 정규부분군이다.
z (2) N◁G이면 모든 h∈H에 대해 hN = Nh이므로 HN = NH이다.
따라서 정리 3.5에 의해 HN은 G의 부분군이다.
H∩N은 H의 부분군이며, 모든 h∈H에 대해 다음이 성립한다.
h-1(H∩N)h = (h-1Hh)∩(h-1Nh) = H∩N
따라서 정리 5.3에 의해 H∩N◁H이다. 또한 N⊆H이므로 (1)에
의해 N◁HN이다.
8/18
정규부분군 - 계속
(증명)
증명
z (3) H◁G, N◁G이면 H∩N과 HN은 G의 부분군이고, 또 모든 g∈G에
대해 다음이 성립한다.
g-1(H∩N)g = (g-1Hg)∩(h-1Nh) = H∩N
g-1(HN)g = g-1HgN = g-1gHN = HN
따라서 정리 5.3에 의해 H∩N◁G, HN◁G이다.
9/18
단순군
„
„
정의 5.3. (단순군)
단순군 군 G(≠{e})에 대하여 G 및 {e} 이외의 정규부분군을
가지지 않을 때, G를 단순군(simple
group)이라 한다.
단순군
정리 5.6. 군 G(≠{e})에 대해 다음 조건은 서로 동치이다.
z (1) 군 G의 위수는 소수이다.
z (2) G는 순환군인 동시에 단순군이다.
z (3) G는 아벨군인 동시에 단순군이다.
(증명)
증명
z (1)⇒ (2): 정리 4.7에 의해 군 G의 위수가 소수이면 G는 순환군이다.
또한 G에서 e를 제외한 모든 원소는 생성자이므로 G의 부분군은
G와 {e} 뿐이다. 따라서 단순군이다.
z (2)⇒ (3): 정리 3.8에 의해 순환군은 아벨군이므로 성립한다.
z (3)⇒ (1): 아벨군의 모든 부분군은 정규부분군이므로 G가 아벨군인
동시에 단순군이면 G의 부분군은 G와 {e}뿐이다. 따라서 정리 4.7에
의해 G의 위수는 소수이다.
10/18
잉여군
„
„
N이 G의 정규부분군이라 하자. 각 잉여류 aN에 속해 있는 원소를 동일
시하여 aN을 새로운 원소로 생각하고 이들 잉여류 전체의 집합을 G/N
으로 나타내자.
G/N = {xN | x∈G}, xN = {xn | n∈N}
aN = bN ⇔ a-1b∈N
G/N 위에 곱셈 ◦을 (aN)◦(bN) = abN으로 정의하면 이 연산은 잘 정의된
(well-defined) 연산이다.
z 잘 정의된 연산이란 모호하지 않은 연산을 말한다.
또한 집합 G/N은 연산 ◦에 대해 군을 형성한다.
z (결합법칙)
결합법칙 (aN◦bN)◦cN = (abN)◦cN = abcN = a(bcN) = aN◦(bN◦cN)
z (항등원)
항등원 aN◦eN = aeN = aN = eN◦aN
z (역원)
역원 aN◦a-1N = aa-1N = eN = a-1N◦aN
11/18
잉여군 - 계속
„
예5.2)
Z*7 = {1, 2, 3,4,5,6}, N = {1,6}
1 N = {1,6}, 2 N = {2,5}, 3 N = {3,4},4 N = {3,4},5 N = {2,5},6 N = {1,6}
Z*7 / N = {1 N , 2 N , 3 N ,4 N ,5 N ,6 N } = {1 N , 2 N , 3 N }
2 N D 3 N = 6 N = {1,6} = 1 N
3 N D 3 N = 2 N = {2,5}
12/18
잉여군 - 계속
„
정의 5.4. (잉여군) 군 G에서 N◁G일 때, G에서 N의 잉여류 전체의
집합을 G/N이라 하자. 즉,
G/N = {xN | x∈G}, xN = {xn | n∈N}
aN = bN ⇔ a-1b∈N
이 때 집합 G/N은 다음과 같이 정의된 연산 ◦에 관하여 군을 형성한다.
(aN)◦(bN) = abN
이와 같이 정의된 군 <G/N, ◦>을 G의 N에 의한 잉여군, 인자군(factor
group), 몫군, 상군(quotient group)이라 한다.
z 잉여군 G/N의 항등원은 eN = N이고, 또 각 원소 aN∈G/N의 역원은
a-1N이다.
13/18
잉여군 - 계속
„
정리 5.7. 군 G에서 N◁G일 때 다음이 성립한다.
z (1) 잉여군 G/N에서 임의의 x∈G와 정수 m에 대하여 (xN)m = xmN
이다.
z (2) G가 유한군이면 잉여군 G/N도 유한군이고 |G/N| = |G|/|N|이다.
z (3) |G:N| = n 일 때 임의의 x∈G에 대하여 xn∈N이다.
(증명)
z (1) 당연히 성립한다.
z (2) |G/N| = |G:N|이며 정리 4.6에 의해 |G/N| = |G|/|N|이다.
z (3) |G:N| = n이면 |G/N| = n이므로 정리 4.6에 의해 잉여군 G/N의
임의의 원소 xN의 위수는 n의 약수이다. 따라서 임의의 x∈G에 대해
(xN)n = N이다. 즉, xnN = N이므로 xn∈N이다.
14/18
잉여군 - 계속
„
정리 5.8. 군 G가 아벨군이면 G의 부분군 N은 모두 정규부분군이고
잉여군 G/N은 아벨군이다. 특히, 군 G가 순환군이면 G의 부분군
N은 모두 정규부분군이고 잉여군 G/N은 순환군이다.
실제로 G = <a>이면 G/N = <aN>이다.
(증명) G가 아벨군이면 잉여군 G/N에서 다음이 성립한다.
(aN)◦(bN) = abN = baN = (bN)◦(aN)
따라서 G/N은 아벨군이다.
G가 순환군이면 G는 아벨군이므로 G의 부분군 N은 모두 정규부분군
이다. 이 때 G = <a>이면 다음이 성립한다.
G/N = {xN | x∈G} = {aiN | i∈]} = {(aN)i | i∈]} = <aN>
따라서 잉여군 G/N은 순환군이다.
15/18
잉여군 - 계속
„
예5.3)
Z*7 = {1, 2, 3,4,5,6}, N = {1,6}
1 N = {1,6}, 2 N = {2,5}, 3 N = {3,4},4 N = {3,4},5 N = {2,5},6 N = {1,6}
Z*7 / N = {1 N , 2 N , 3 N ,4 N ,5 N ,6 N } = {1 N , 2 N , 3 N }
2 N = {2,5}
(2 N )2 = 2 N D 2 N = 4 N = {3,4}
(2 N )3 = 2 N D 2 N D 2 N = 1 N = {1, 2}
Z*7 / N =< 2 N >
16/18
잉여군 - 계속
„
정리 5.9. 군 G에서 N⊆Z(G)인 G의 부분군 N에 대하여 잉여군 G/N이
순환군이면 G는 아벨군이다. 특히 잉여군 G/Z(G)가 순환군이면 G는
아벨군이다.
(증명) 정리 5.4에 의해 N이 N⊆Z(G)인 G의 부분군이면 N◁G이므로
잉여군 G/N이 존재한다. G/N은 잉여군 정의에 의해 잉여류의 전체
집합이므로 G/N의 원소들의 합집합은 G이다. 이 때 G/N = <aN>이면
G/N = {aiN | i∈]}이므로 G = ∪aiN이다.
임의의 두 원소 x, y∈G는 x = ain, y = ajm, (n, m∈N, i, j∈])로 표현할 수
있으며, N⊆Z(G)이므로 다음이 성립한다.
xy = ainajm = aiajnm = ajainm = ajnaim = yx
따라서 G는 아벨군이다.
17/18
잉여군 - 계속
„
정리 5.10. 군 G에서 N◁G이고 H는 N⊆H인 G의 부분군이면
H/N = {hN∈G/N | h∈H}는 잉여군 G/N의 부분군이다. 특히 N⊆H◁G
이면 H/N◁G/N이다.
(증명) N은 G의 부분군이므로 H가 N⊆H인 G의 부분군이면 N은 H의
부분군이다. 따라서 잉여군 G/N의 부분집합 H/N이 존재한다. 이 때
임의의 두 원소 hN, kN∈H/N이면 h, k∈H이며 다음이 성립한다.
(hN)(kN)-1 = (hN)(k-1N) = hk-1N∈H/N
따라서 H/N = {hN | h∈H}는 잉여군 G/N의 부분군이다.
특히, N⊆H◁G이면 임의의 원소 x∈G, h∈H에 대해 x-1hx∈H이므로 다
음이 성립한다.
(xN)-1(hN)(xN) = (x-1N)(hxN) = x-1hxN∈H/N
따라서 정리 5.3에 의해 H/N◁G/N이다.
18/18
잉여군 - 계속
„
예5.4) Z* = {1, 2, 3,4,5,6,7,8,9,10,11,12},
13
N = 12 = {1,12}, H = 4 = {1, 3,4,9,10,12}
1 N = {1,12}, 2 N = {2,11}, 3 N = {3,10},4 N = {4,9},
5 N = {5,8},6 N = {6,7},7 N = {6,7},8 N = {5,8}
9 N = {4,9},10 N = {3,10},11 N = {2,11},12 N = {1,12}
Z*13 / N = {1 N , 2 N , 3 N ,4 N , 5 N ,6 N }
H / N = {1 N , 3 N ,4 N }
1 N D 1 N = 1 N ,1 N D 3 N = 3 N ,1 N D 4 N = 4 N
3 N D 3 N = 9 N = 4 N , 3 N D 4 N = 12 N = 1 N
z
H/N은 Z*13 / N의 부분군이다.
19/18