離散数学及び演習 講義11

環（復習）


離散数学及び演習
講義11 2014. 7. 3（木）代数系（R，＋，・） は環である

 次の（1）～（7）が成り立つ．
（1） 任意の x，y，z∈R に対して， x＋（y＋z） ＝ （x＋y）＋z（加法の結合則（associative law））（2） c∈R が存在して，任意の x∈R に対して，x＋c＝c＋x＝x（加法の単位元の存在）
 c … 加法の単位元（unit element，identity element）（零元）（3） 任意の x∈R に対して， y∈R が存在して，x＋y＝y＋x＝c（加法の逆元の存在）
 y＝－x… x の加法の逆元（inverse element）（4） 任意の x，y∈R に対して， x＋y ＝ y＋x（加法の交換則（commutative law））

環（続き）（教科書 pp.161-164）
群（教科書 pp.168-170）
教科書･･･野崎昭弘：離散系の数学、近代科学社

2環（復習）（続き）


可換環（復習）代数系（R，＋，・） は環である



次の（1）～（7）が成り立つ．
（5） 任意の x，y，z∈R に対して， x・（y・z） ＝ （x・y）・z（乗法の結合則（associative law））（6） e∈R が存在して，任意の x∈R に対して，x・e＝e・x＝x（乗法の単位元の存在） e …
乗法の単位元（unit element，identity element）（7） 任意の x，y，z∈R に対して，
x・（y＋z） ＝ （x・y）＋（x・z），（x＋y）・z ＝ （x・z）＋（y・z）（分配則（distributive law））


代数系（R，＋，・） は可換環である

 （R，＋，・） は環で，かつ，次の（8）が成り立つ．
（8） 任意の x，y∈R に対して， x・y ＝ y・x（乗法の交換則（commutative law））



条件（1）～（7） … 環の公理（axiom）
34体（field）
体（続き）

代数系（F，＋，・，c，e） は体（可換体）である

例：（Q，＋，・，0，1）… 有理数体（R，＋，・，0，1）… 実数体
 （C，＋，・，0，1）… 複素数体 （Q［i］ ，＋，・，0，1）… Gauss の数体
 Q［i］＝{ x＋yi｜x，y∈Q }（F，＋，・，c，e） は環で，かつ，次の（8），（9）が成り立つ．
（8） 任意の x，y∈F に対して， x・y ＝ y・x（乗法の交換則（commutative law））（9） 任意の x∈F （x≠c）に対して， y∈F が存在して，
x・y ＝ y・x ＝e（乗法の逆元の存在）－1 … x の乗法の逆元（inverse element）
 y＝x
 x は可逆（invertible）である









明らかに， （Q［i］ ，＋，・，0，1）は環である．
明らかに，乗法の交換則が成り立つ．
 任意の x＋yi ∈ Q［i］ （ x＋yi ≠0 ）に対して，



1
x
y
i  Q [i ]x  yi x 2  y 2 x 2  y 2

すなわち，乗法の逆元が存在する．

代数系（F，＋，・，c，e） は斜体（skew field）である
（F，＋，・，c，e） は環で，かつ，上の（9）が成り立つ．



整数環（Z，＋，・，0，1）は体でない51

任意の n∈Z （n≠0）に対して， 1／n∈Z であるとは限らない．

6

離散数学及び演習 講義11

定理

証明

p が素数であるとき，かつそのときに限り，（ Zp，＋p，・p ） は体である．

0

1

2

Zp （ p は素数）
… p 元体（field with p elements） Fp

0

0

0

0

1

0

1

2

p∈Z に対して，Zp＝{0，1，…，p－1}… p∈Z を法とする完全剰余系
 x＋p y＝mod（ x＋ y，p ）x ・p y ＝mod（ x・ y，p ） （ Zp，＋p，・p ，0 ，1 ） は可換環．

2

0

2

1







任意の x∈Zp （x≠0）に対して，
y＝x－1 ∈ Zp が存在して，x・y ＝ y・x ＝1Z3＝{0，1，2}
Z5＝{0，1，2，3，4}
Z4＝{0，1，2，3}

p が素数であるとき，かつそのときに限り，（Zp，＋p，・p ）は体である．

乗算表（p＝3）・3a）「 p が素数ならば，（ Zp，＋p，・p ） は体である」を示す．
b）「 （ Zp，＋p，・p ） が体ならば， p は素数である」を示す．
a） p は素数であると仮定して，乗法の逆元が存在することを示す．
 「任意の k∈Zp（k≠0）に対して，y∈Zpが存在して，k・p y＝1」を示す．

乗算表（p＝4）
・4

0

1

2

3

0

0

0

0

0

1

0

1

2

3

2

0

2

0

2

2

1

（乗法の逆元の存在）
30
3
1－1＝1，2－1＝2
－1
－1
－1
－1
1 ＝1，2 ＝3，3 ＝2，4 ＝4
1－1＝1，2－1：存在しない，3－1＝3a） p は素数であると仮定する．
（Zp，＋p，・p）は可換環である．
また，任意の k∈Zp （k≠0）に対して，1 k＜p．
ゆえに，gcd（k，p）＝1．
このとき，合同方程式 ky≡1 （mod p）の解 y∈Zp が存在する．
すなわち， y∈Zp が存在して，k・p y＝1．
乗法の逆元が存在するので，（Zp，＋p，・p）は体である．
78

有限体（finite field）

証明
p が素数であるとき，かつそのときに限り，（Zp，＋p，・p ）は体である．


体（F，＋，・） は有限体（Galois 体）である
b）「 （ Zp，＋p，・p ） が体ならば， p は素数である」を示す．
 （ Zp，＋p，・p ） が体であるとき，p は素数でないと仮定して，矛盾を導く．

b） （ Zp，＋p，・p ） は体であると仮定する．
さらに， p は素数でないと仮定する．
このとき，p は合成数だから，k，s∈Z （1＜ k，s ＜p ）が存在して，p＝k・s．
k∈Zp （k≠0）だから，k の逆元 y∈Zp が存在して，k・p y＝1．
ゆえに，q∈Z が存在して，ky－1＝q・p＝q・k・s だから，
k（y－q・s）＝1．
y－q・s ∈Z だから，1＜k に矛盾する．

F は有限集合である｜F｜ … 有限体の位数（order）
位数 q の有限体 … GF（q）

例： p 元体 Fp は位数 p の有限体



符号理論，暗号理論への応用

E. Galois（仏，1811-1832）910

零因子（zero divisor）

定理
体（F，＋，・）に対して，次の（1）～（4）が成り立つ．
（1） 加法の単位元は唯一である．
（2） 加法の逆元は唯一である．
（3） 乗法の単位元は唯一である．
（4） 乗法の逆元は唯一である．



環（R，＋，・，c，e） において，x∈R は零因子である
y∈R （y≠c）が存在して，x・y＝y・x＝c例：
 環 （ Z6，＋6，・6 ，0，1）
 2∈Z6 は零因子
 3∈Z6 （3≠0） に対して，2・6 3＝3・6 2＝0
 任意の環（ R，＋，・，c，e ） 零元 c∈R は零因子
 任意の y∈R （ y≠c） に対して，c・y＝y・c＝c体は環でもあるから，（1）～（3）が成り立つのは明らか．
 （4）は（2）と同様に示せる．


11

12

2

離散数学及び演習 講義11

整域（integral domain）


整域（続き）

代数系（R，＋，・，c，e） は整域である

例：（R，＋，・，c，e） は可換環で，かつ，次の（10）が成り立つ．
（10） 任意の x，y∈R に対して，
x・y ＝ c ならば，x＝c または y＝c

整数環（Z，＋，・，0，1）


任意の x，y∈Z に対して，x・y ＝ 0 ならば，x＝0 または y＝0多項式環（R［x］，＋，・，0，1）
 p 元体 （ Fp，＋p，・p，0，1 ）（p は素数）


（零元でない零因子の非存在）

任意の x，y∈Fp に対して，x・p y ＝ 0 ならば，x＝0 または y＝0
任意の x，y∈Fp に対して，x・y ≡0 （mod p） ならば，x≡0 （mod p） または y≡0 （mod p） ．



一般に，環（ Zp，＋p，・p，0，1 ）は整域でない（10’） 任意の x，y∈R に対して，
x・y ＝ c かつ x≠c ならば，y＝c

零元でない零因子が存在する．

13

14

定理

証明
可換環（R，＋，・，c，e）が整域であるとき，かつそのときに限り，次が成り立つ．
任意の x，y，z∈R に対して， x・z ＝ y・z かつ z≠c ならば，x＝y．

可換環（R，＋，・，c，e） が整域であるとき，かつそのときに限り，次が成り立つ．
任意の x，y，z∈R に対して，
x・z ＝ y・z かつ z≠c ならば，x＝y．
z・x ＝ z・y かつ z≠c ならば，x＝y．

a）「R が整域であるとき， x・z ＝ y・z かつ z≠c ならば x＝y 」を示す．
b）「x・z ＝ y・z かつ z≠c ならば x＝y であるとき， R は整域である」を示す．

a） R は整域であると仮定する．
また，任意の x，y，z∈R に対して， x・z ＝ y・z かつ z≠c と仮定する．
このとき， x・z ＋（－（ y・z ））＝ y・z ＋ （－（ y・z ））＝c．
分配則から， （x ＋（－ y））・z ＝c．
R は整域で， z≠c だから，x ＋（－ y）＝c．
したがって，x＝－（－y）＝y．
b） 任意の x，y，z∈R に対して， x・z ＝ y・z かつ z≠c ならば x＝y と仮定する．
ここで，y＝c とおくと， x・z ＝ c・z かつ z≠c ならば，x＝c ．
ゆえに，x・z ＝ c かつ z≠c ならば，x＝c．
すなわち，R は整域である．

（消去則）

15

16

定理

証明

次の（1），（2）が成り立つ．
（1） 体は整域である．
（2） 有限な整域は体である．
環
可換環
体
乗法の逆元の存在（1） 体は整域である．



環
可換環
整域

零元でない零因子は存在しないことを示す．
「任意の x，y∈F に対して，x・y ＝c かつ x≠c ならば，y＝c」 を示す．

（F，＋，・，c，e）を体とする．
任意の x，y∈F に対して，x・y＝c かつ x≠c とする.
このとき， F は体だから， x－1∈F が存在する.
ここで， x－1・（x・y）＝ x－1・c ＝c．
一方，x－1・（x・y） ＝（x－1・x）・y＝e・y＝y．
したがって，y＝c.

零元でない零因子の非存在

体
有限整域

17

18

3

離散数学及び演習 講義11

証明（続き）

整域における整除関係（2） 有限な整域は体である．

整域（R，＋，・）と x，y∈R に対して，
 x は y の約元（factor）である
y は x の倍元（multiple）である
x は y を割り切る（divide）（ y は x で割り切れる（divisible））… x｜y q∈R が存在して，y＝q・x

乗法の逆元が存在することを示す．
 「任意の x∈F （x≠c）に対して， y∈F が存在して，x・y ＝ y・x ＝e」
を示す．

（F，＋，・，c，e）を有限な整域とする．
まず，任意の x∈F（x≠c）を考える．
関数 f ：F→F を任意の u∈F に対して f（u）＝x・u と定義する．
任意の u1，u2∈F に対して， f（u1）＝ f（u2） とする．このとき，x・u1＝x・u2．
ゆえに，x・u1＋（－（x・u1））＝ x・u2＋（－（x・u1））だから，c ＝ x・（u2＋（－u1））．
x≠c で， F は整域だから， u2＋（－u1）＝c．
ゆえに， u2＝u1 であり， f は単射である．
F は有限集合だから，f は全射でもある．
さらに，F＝{u1，…，un} とおくと，f は全単射だから，
F＝{ f（u1），…， f（un）} ＝{ xu1，…，xun }．
e∈F だから， ui∈F が存在して， xui＝e.
すなわち，任意の x∈F（x≠c）に対して，乗法の逆元 ui が存在する．
19

20

公約元

定理

整域（R，＋，・）と x，y∈R に対して，
 d∈R は x，y の公約元（common factor）である


整域（R，＋，・）と任意の a，b∈R に対して，
x，y∈R が存在して，a・x＋b・y＝gcd（a，b）．

d｜x かつ d｜y ．

d∈R は x，y の最大公約元（greatest common factor）
である… d＝gcd（ x，y）＝（ x，y ）d は x，y の公約元で，かつ， x，y の任意の公約元 d’に対して，d’｜d （d’ は d の約元） ．

21

22

素元（prime element）

素元分解整域

整域（R，＋，・，c，e）に対して，
 p∈R は素元である

p は次の（1）～（3）を満たす．
（1） p は可逆元でない（p－1 ∈R は存在しない）．
（2） p≠c（3） x・ y∈R に対して，p｜x・y ならば，p｜x または p｜y．
例：
 整域（Z，＋，・，0，1）


代数系 （R，＋，・，c，e） は素元分解整域（prime factorization domain）である（R，＋，・，c，e） は整域で，かつ，任意の x∈R （x≠c）は，可逆元でなければ，有限個の素元 p1，p2，…，pr に対して，
x＝p1・ p2・…・pr の形（素元の積の形）で表すことができる．


x＝p1・ p2・…・pr の形 … 素元分解（prime factorization）

正の素元は素数．

整域（R［x］，＋，・，0，1）


素元は既約多項式．
23

24

4

離散数学及び演習 講義11

Euclid 域（Euclidean domain）

定理


素元分解整域における素元分解の表現は，一意的である．


素元分解整域 … 一意分解整域（unique factorization domain，UFD）

素元分解整域において，最大公約元は必ず存在する．

代数系（R，＋，・，c，e）は Euclid 域である
 （R，＋，・，c，e）は整域で，かつ，関数 v ： R → N－｛0｝が存在して，次の（1），（2）が成り立つ．
（1） 任意の x，y∈R（ x，y≠c ） に対して，v（x・y） v（x）．
（2） 任意の x，y∈R（ y≠c） に対して，q，r∈R が存在して，
次の a），b） が成り立つ．
a） x＝q・y＋rb） r＝c または v（r）＜v（y）

 関数 v… R 上の付値（valuation）
例： （Z，＋，・，0，1 ）… v（ x ）＝｜x｜ （R［x］，＋，・，0，1 ）… v（P（x））＝deg（P（x））
 （Z［i］，＋，・，0，1 ）… v（ x＋yi ）＝x2＋y2
25

26

定理




半群，モノイド

Euclid 域は素元分解整域である．



 次の（1）が成り立つ．
（1） 任意の x，y，z∈G に対して， x・（y・z） ＝ （x・y）・z（結合則（associative law））

Euclid 域（R，＋，・，c，e）と任意の x，y，r，s∈Rに対して，x＝q・y＋r ならば，gcd（x，y）＝gcd（y，r）．


代数系 （G，・） は半群（semigroup）である

Euclid の互除法により，最大公約元を求められる．


代数系 （G，・） はモノイド（monoid）（単位半群，
unitary semigroup）である

 （G，・） は半群で，かつ，次の（2）が成り立つ．
（2） e∈G が存在して，任意の x∈G に対して，x・e＝e・x＝x



（単位元の存在）e … 単位元（unit element，identity element）

27

28

群（group）
群（続き）

代数系 （G，・） は群である



（G，・） はモノイドで，かつ，次の（3）が成り立つ．
（3） 任意の x∈G に対して， y∈G が存在して，x・y＝y・x＝e

（逆元の存在）

代数系 G は群である

G 上に 1 つの演算が定義されている．
（演算は G 上で閉じている）
 次の（1）～（3）（群の公理）が成り立つ．
（1） 結合則（2） 単位元の存在（3） 逆元の存在

y＝x－1 … 逆元（inverse element）

29

30

5

離散数学及び演習 講義11

可換群（commutative group）

群（続き２）例： モノイド （Z，＋，0） （R，＋，0） （Z，・，1）
 （R，・，1）

代数系 （G，・） は可換群（Abel 群（Abelian group））
である

 （G，・） は群で，かつ，次の（4）が成り立つ．
（4） 任意の x，y∈R に対して， x・y ＝ y・x（交換則（commutative law））

群（Z，＋，0）（R，＋，0） （R－{0}，・，1）


N. H. Abel
（ノルウェー，1802-1829）3132

乗法群，加法群
群（G，・，e）

群と環… 乗法群（multicative group）



単位元 e
－1
 x∈G の逆元 x

可換群（G，＋，c）

環（R，＋，・）の公理（1） 加法の結合則（2） 加法の単位元の存在（3） 加法の逆元の存在（4） 加法の交換則（5） 乗法の結合則（6） 乗法の単位元の存在（7） 分配則… 加法群（additive group）

単位元 c （零元） x∈G の逆元 －x（R，＋）は加法群（R，・）はモノイド

3334

置換群（permutation group）

群と体

体（F，＋，・）の公理（1） 加法の結合則（2） 加法の単位元の存在（3） 加法の逆元の存在（4） 加法の交換則（5） 乗法の結合則（6） 乗法の単位元の存在（9） 乗法の逆元の存在（8） 乗法の交換則（7） 分配則

正三角形の回転における頂点の対応

（F，＋）は加法群

3

σ3＝ 1 2 3
3 1 2

1
σ3

σ2＝ 1 2 3
2 3 1

2

σ2
σ1

1

（F－{c}，・）は可換乗法群

2

2

3

3

1

σ1＝ 1 2 3
1 2 3


35

σi … 頂点集合 {1，2，3} 上の置換
366

離散数学及び演習 講義11

置換群（続き）置換群（続き２）正三角形の反転における頂点の対応

2

σ6＝ 1 2 3
2 1 3

σ5＝ 1 2 3
3 2 1

1

σ6

1

3



正三角形の回転・反転の合成における頂点の対応
σ4＝ 1 2 3
1 3 2

3

σ5

σ4
1

1
2

2

置換群（続き４）






1

S（3）＝ {



σ5



2

σ3・σ4＝ 1 2 3
3 1 2



2

3

1

1 2 3 ＝ 1 2 3 ＝σ5
1 3 2
3 2 1



39

定理

… 置換群

演算・は S（3）上で閉じている
演算・の結合則は成り立つ
単位元 σ1
逆元
σ1－1＝σ1 ，σ2－1＝σ3 ，σ3－1＝σ2 ，σ4－1＝σ4 ，σ5－1＝σ5 ，σ6－1＝σ6
演算・は非可換
σ3・σ4＝σ5
σ4・σ3＝σ6
σ3・σ4≠σ4・σ3

乗積表（群表）σ1

σ2 σ3 σ4 σ5 σ6

σ1 σ1

・

σ2 σ3 σ4 σ5 σ6σ2 σ2σ3 σ1 σ6 σ4 σ5σ3 σ3

σ1 σ2 σ5 σ6 σ4σ4 σ4σ5 σ6 σ1 σ2 σ3

σ5 σ5
σ6 σ6

σ6 σ4 σ3 σ1 σ2
σ4 σ5 σ2 σ3 σ140定理
代数系（G，・）が次の（1）～（3）を満たすとき，かつそのときに限り，（G，・）は群である．
（1） 任意の x，y，z∈G に対して， x・（y・z） ＝ （x・y）・z（結合則（associative law））

次の（1）～（3）が成り立つ．
（1） モノイドの単位元は唯一である．
（2） 群の単位元は唯一である．
（3） 群の逆元は唯一である．


集合 {1，2，3} 上のすべての置換からなる集合（ S（3），・ ） は群である


2

1 2 3
i j k ｜{i，j，k}＝{1，2，3} }＝ {σ1，σ2，σ3，σ4，σ5，σ6 }σ3＝ 1 2 3
3 1 2
3

3

1 2 3 ＝ 1 2 3
1 3 2
3 2 1
38

正三角形の回転・反転の合成における頂点の対応

1

1

37

置換群（続き３）σ4＝ 1 2 3
1 3 2

2

3
σ4

σ3・σ4＝ 1 2 3
3 1 2

3



2

3

σ4＝ 1 2 3
1 3 2

3

σ3

1
2

3

2

σ3＝ 1 2 3
3 1 2

1（2） e∈G が存在して，任意の x∈G に対して，x・e＝x（右単位元の存在）
 e … 右単位元（right unit element，right identity element）

環の単位元，逆元の唯一性と同様に示せる．

（3） 任意の x∈G に対して， y∈G が存在して，x・y＝e（右逆元の存在） y … 右逆元（right inverse element）
41

42

7

離散数学及び演習 講義11

証明

証明（続き）

代数系（G，・）が次の（1）～（3）を満たすとき，かつそのときに限り，（G，・）は群である．
（1） 任意の x，y，z∈G に対して， x・（y・z） ＝ （x・y）・z （結合則）（2） e∈G が存在して，任意の x∈G に対して，x・e＝x （右単位元の存在）（3） 任意の x∈G に対して，y∈G が存在して，x・y＝e （右逆元の存在） a）「（G，・）が（1）～（3）を満たすならば，（G，・）は群である」を示す．
 b）「（G，・）は群ならば，（G，・）は（1）～（3）を満たす」を示す．
a）「代数系（G，・）が（1）～（3）を満たすならば，（G，・）は群である」を示す．
 a-2）「逆元が存在する」を示す．
 a-2）「左逆元が存在する」を示す．
a） 代数系（G，・）が（1）～（3）を満たすと仮定する．
a-2）右逆元の存在から，任意の x∈G に対して，y∈G が存在して，x・y＝e．
さらに，この y に対して，z∈G が存在して，y・z＝e．
このとき，y・x ＝ y・（x・e）（右単位元）＝ （y・x）・e（結合則）＝ （y・x）・（y・z）＝ （（y・x）・y）・z（結合則）＝ （y・（x・y））・z（結合則）＝ （y・e）・z＝ y・z（右単位元）＝ e
ゆえに， x・y＝y・x＝e だから，y は x の逆元である．
44

明らか．

a）「（G，・）に対して．群の公理が成り立つ」を示す．
 a-1）「結合則が成り立つ」を示す．
 a-2）「逆元が存在する」を示す．
 a-3）「単位元が存在する」を示す．

a） 代数系（G，・）が（1）～（3）を満たすと仮定する．
a-1）明らかに，結合則は成り立つ．
43

証明（続き）系
代数系（G，・）が次の（1）～（3）を満たすとき，かつそのときに限り，（G，・）は群である．
（1） 任意の x，y，z∈G に対して， x・（y・z） ＝ （x・y）・z（結合則（associative law））

1）「代数系（G，・）が（1）～（3）を満たすならば，（G，・）は群である」を示す．
 a-3）「単位元が存在する」を示す．
 a-3）「左単位元が存在する」を示す．
a） 代数系（G，・）が（1）～（3）を満たすと仮定する．
a-3）逆元の存在から，任意の x∈G に対して，y∈G が存在して，x・y＝ y・x＝e．
このとき，e・x ＝ （x・y）・x＝ x・（y・x）
（結合則）
＝ x・e
＝ x
（右単位元）
ゆえに， x・e＝e・x＝x だから，e は単位元である．

（2） e∈G が存在して，任意の x∈G に対して，e・x＝x（左単位元の存在）
 e … 左単位元（left unit element，left identity element）（3） 任意の x∈G に対して， y∈G が存在して，y・x＝e（左逆元の存在） y … 左逆元（left inverse element）

45

46

まとめ


今日の講義





次回の講義





（1限）部分系，準同型（教科書 pp.164-165，170-173）（2限）商系（教科書 pp.165-168）

次回の演習




環（続き）
群

なし

今日の演習


環（続き），群47

8