第4章整数の剰余群

第 4 章整数の剰余群
4.1
4.1.1
整数の剰余類
合同の定義
定義 4.1 n を自然数とするとき、
a ≡ b (mod n)
def.
⇐⇒
a − b ∈ nZ
と定義する。このとき、a と b は n を法として合同であるという。
例 : 127 − 76 = 17 × 3 なので、127 ≡ 76 (mod 17) である。（例終）
命題 4.2 この関係は同値関係になっている。自然数 n と整数 a、b、c について
a ≡ a (mod n),
(i)
(iii))
a ≡ b (mod n),
(ii)
a ≡ b (mod n)
b ≡ c (mod n)
=⇒
=⇒
b ≡ a (mod n)
a ≡ c (mod n)
が成り立つ。
（証明） (1) a − a = 0 = n · 0 より。
(2) a ≡ b (mod n) ならば、ある整数 k により、a − b = n · k と書けることになるが、これより、b − a = n · (−k) とな
るので、b ≡ a (mod n) である。
(3) a ≡ b (mod n)、b ≡ c (mod n) ならば、ある整数 k 、l により、a − b = n · k 、b − c = n · l と書ける。これより、
a − c = a − b + (b − c) = n(k + l)
となるので、a − c も n の倍数である。（証明終）
命題 4.3 n ∈ Z、a1 、a2 、b1 、b2 ∈ Z に対し、a1 ≡ a2 (mod n)、b1 ≡ b2 (mod n) とすると、
(i)
a1 + b1 ≡ a2 + b2 (mod n),
(ii)
a1 b1 ≡ a2 b2 (mod n),
がいえる。
（証明）仮定より、ある k 、l ∈ Z に対し、a1 − a2 = nk 、b1 − b2 = nl と書ける。このとき、
(i) (a1 + b1 ) − (a2 + b2 ) = (a1 − a2 ) + (b1 − b2 ) = nk + nl = n(k + l) ∈ nZ なので、a1 + b1 ≡ a2 + b2 (mod n) がいえる。
(ii) a1 b1 − a2 b2 = a1 b1 − a1 b2 + a1 b2 − a2 b2 = a1 (b1 − b2 ) + (a1 − a2 )b2 = a1 nl + nkb2 = n(a1 l + b2 k) ∈ nZ なので、
a1 b1 ≡ a2 b2 (mod n) がいえる。（証明終）
33
4.1.2
剰余類の定義
n を法として合同である、という関係を用いて、整数の集合を分類する。
定義 4.4 自然数 n と整数 a に対して、n を法として a と合同な整数の全体を a を代表元とする剰余類といい、C(a)
で表わす。すなわち、
def.
C(a) := {b ∈ Z | b ≡ a (mod n)}.
例 : n = 2 を法として考えるとき、a = 1 の剰余類は
C(1) = {b ∈ Z | b ≡ 1 (mod 2)}
で、
b ≡ 1 (mod 2)
⇐⇒
b − 1 = 2k (k : 整数)
⇐⇒
b = 2k + 1 (k : 整数)
だから、C(1) は奇数の集合になる。同様に C(0) は偶数の集合。（例終）
注意 : C(a) の表わし方は一通りではない。例えば、3 を法としたとき、
· · · = C(−1) = C(2) = C(5) = C(8) = · · ·
である。（終）
命題 4.5 自然数 n と整数 a、b に対して、次の (i)、(ii)、(ii) は同値。
(i) a ≡ b (mod n)。
(ii) n を法として C(a) = C(b)。
(iii) n を法として a ∈ C(b)。
（証明） (i)、(ii)、(iii) が同値であることを示すには、
「(i) ならば (ii)」、
「(ii) ならば (iii)」、
「(iii) ならば (i)」を示せば
よい。これを示すと、例えば、
「(ii) ならば (i)」は、
「(ii) ⇒ (iii) ⇒ (i)」のように考えれば、成立していることがわかる。
(i) ⇒ (ii) : 仮定 (i) のもとで C(a) ⊂ C(b) かつ C(a) ⊃ C(b) がいえればよい。まず、C(a) ⊂ C(b) 、すなわち、
c ∈ C(a) =⇒ c ∈ C(b) を示す。c ∈ C(a) ならば、c ≡ a (mod n) である。このとき、仮定より、a ≡ b (mod n) だから
c ≡ b (mod n) がいえる。これより、c ∈ C(b) である。C(a) ⊃ C(b) も同様に示せる。
(ii) ⇒ (iii) : 命題 4.2 (i) より、a ∈ C(a)。仮定 (ii) より C(a) = C(b) だから、a ∈ C(b) となる。
(iii) ⇒ (i) : a ∈ C(b) と、C(b) の定義より。a ≡ b (mod n) がいえる。（証明終）
特に、(iii) ⇒ (ii) より、a ∈ C(b) ならば、C(a) = C(b) がなりたつので、a が属する剰余類は、a 自身を代表元にとっ
て C(a) と書くことが出来ることがわかる。
定義 4.6 n を法とした剰余類全体の集合を Z/nZ で表す。すなわち、
def.
Z/nZ := {C(a) | a ∈ Z} = {C(0), C(1), · · · , C(n − 1)}
である。
34
4.2
4.2.1
剰余類のなす群
加法を演算とする群
def
定義 4.7 C(a)、C(b) ∈ Z/nZ の和を C(a) + C(b) := C(a + b) で定義する。
定理 4.8 (Z/nZ, +) は群。
（証明） (I) (a) 和が一意に定まること : C(a1 )、C(a2 )、C(b1 )、C(b2 ) ∈ Z/nZ に対し、C(a1 ) = C(a2 ),
C(b1 ) = C(b2 )
とすると、C(a1 ) = C(a2 ) より a1 ≡ a2 (mod n)、C(b1 ) = C(b2 ) より b1 ≡ b2 (mod n) がいえるから、a1 + b1 ≡
a2 + b2 (mod n) がいえ、C(a1 + b1 ) = C(a2 + b2 ) がいえる。これと、+ の定義より、C(a1 ) + C(b1 ) = C(a2 ) + C(b2 )
がなりたつ。
(b) 和がもとの集合に含まれること : C(a) + C(b) = C(a + b) で、a + b ∈ Z より、C(a + b) ∈ Z/nZ である。
(II) 結合法則を満たすことは、
{C(a) + C(b)} + C(c) = C(a + b) + C(c)
[∵) 剰余類の和の定義 ]
= C ((a + b) + c)
= C (a + (b + c))
= C(a) + C(b + c)
[∵) 剰余類の和の定義 ]
[∵) 整数の和の結合法則]
[∵) 剰余類の和の定義 ]
= C(a) + {C(b) + C(c)}
[∵) 剰余類の和の定義 ]
よりいえる。
(III’) C(0) が左単位元になる。実際、
(i) 任意の C(a) ∈ Z/nZ に対して、C(0) + C(a) = C(a)
(ii) 0 ∈ Z より、C(0) ∈ Z
(IV’) C(a) ∈ Z/nZ に対し、C(−a) ∈ Z/nZ が左逆元になる。実際、
(i) C(−a) + C(a) = C ((−a) + a) = C(0)
(ii) C(a) ∈ Z/nZ より a ∈ Z。よって、−a ∈ Z だから、C(−a) ∈ Z/nZ である。
以上より、左単位元 C(0) が単位元に、左逆元 C(−a) が逆元になり、(Z/nZ, +) は群になる。（証明終）
4.2.2
乗法を演算とする群
def.
定義 4.9 C(k)、C(l) ∈ Z/nZ の積 · を C(k) · C(l) := C(kl) で定める。
def.
定理 4.10 (Z/nZ)× := { C(a) ∈ Z/nZ | gcd(a, n) = 1 } とする。ただし、gcd(a, n) は a と n との最大公約数である。
このとき、上の積 · を演算とした、((Z/nZ)× , ·) は群。
（証明） (I) (a) 積が一意に定まること : C(a1 )、C(a2 )、C(b1 )、C(b2 ) ∈ (Z/nZ)× に対し、C(a1 ) = C(a2 ),
C(b1 ) =
C(b2 ) とすると、C(a1 ) = C(a2 ) より a1 ≡ a2 (mod n)、C(b1 ) = C(b2 ) より b1 ≡ b2 (mod n) がいえるから、
a1 b1 ≡ a2 b2 (mod n) がいえ、C(a1 b1 ) = C(a2 b2 ) がいえる。これと · の定義より、C(a1 ) · C(b1 ) = C(a2 ) · C(b2 ) がな
35
りたつ。
(b) 積がもとの集合に含まれること : C(a)、C(b) ∈ (Z/nZ)× に対し、C(a) · C(b) = C(ab) で、ab ∈ Z である。また、
a、b の両方が n と互いに素なので、ab も n と互いに素である。よって、C(ab) ∈ (Z/nZ)× である。
(II) 結合法則を満たすことは、
{C(a) · C(b)} · C(c) = C(a · b) · C(c)
= C ((a · b) · c)
= C (a · (b · c))
= C(a) · C(b · c)
= C(a) · {C(b) · C(c)}
[∵) 剰余類の積の定義 ]
[∵) 剰余類の積の定義 ]
[∵) 整数の積の結合法則]
[∵) 剰余類の積の定義 ]
[∵) 剰余類の積の定義 ]
よりいえる。
(III’) C(1) が、(Z/nZ)× の左逆元になる。実際、
(i) 任意の C(a) ∈ (Z/nZ)× に対し、C(1) · C(a) = C(1 · a) = C(a) である。
(ii) 1 ∈ Z で gcd(1, n) = 1 より、C(1) ∈ (Z/nZ)× である。
(IV’) C(a) ∈ (Z/nZ)× に対し、gcd(a, n) = 1 だから、ka + ln = 1 を満たす k, l ∈ Z が存在する。この k を代表元と
する剰余類 C(k) が C(a) の左逆元になる。実際、
(i) ka ≡ 1 (mod n) より、C(k) · C(a) = C(ka) = C(1) である。
(ii) この k ∈ Z に対し、d := gcd(k, n) > 1 とすると、ka + ln は d の倍数であり、これが 1 であることに矛盾する
ので、gcd(k, n) = 1 である。よって、C(k) ∈ (Z/nZ)× がいえる。
以上より、左単位元 C(1) が単位元、左逆元 C(k) が逆元になり、((Z/nZ)× , ·) は群となる。（証明終）
注 : 文献によっては、C(a) のことを、a + nZ、[a]、a と書くものもある。（注終）
例 : (Z/6Z)× = {C(1), C(5)} で、
C(1) · C(1) = C(1),
C(5) · C(1) = C(1) · C(5) = C(5),
である。よって、この群の乗積表は
C(1) C(5)
C(1)
C(1) C(5)
C(5)
C(5) C(1)
のようになる。（例終）
36
C(5) · C(5) = C(25) = C(1)

Download Report