第7章 剰余類

第 7 章 剰余類
7.1
7.1.1
合同の性質
同値関係
命題 7.1 自然数 n と整数 a、b、c について
(1)
a ≡ a (mod n),
(3)
a ≡ b (mod n),
(2)
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 の倍数である。（証明終）
7.2
剰余類
n を法として合同である、という関係を用いて、整数の集合を分類する。
定義 7.2 自然数 n と整数 a に対して、n を法として a と合同な整数の全体を a の 剰余類といい、C(a) で表わす。す
なわち、
def.
C(a) := {b ∈ Z | b ≡ a (mod n)}.
このとき、a を C(a) の 代表元という。
例 : n = 2 を法として考えるとき、a = 1 の剰余類は
C(1) = {b ∈ Z | b ≡ 1 (mod 2)}
で、
b ≡ 1 (mod 2)
⇐⇒
b − 1 = 2k (k : 整数)
⇐⇒
だから、C(1) は奇数の集合になる。同様に C(0) は偶数の集合。（例終）
38
b = 2k + 1 (k : 整数)
注意 : C(a) の表わし方は一通りではない。例えば、3 を法としたとき、
· · · = C(−1) = C(2) = C(5) = C(8) = · · ·
である。（終）
7.2.1
剰余類の表わし方
定義 7.3 自然数 n の倍数の全体を nZ と書くことにする。
def.
nZ := {nk | k ∈ Z}.
さらに、整数 a に対して、a と、n の倍数の和の形に表わされる整数の全体を a + nZ で書く。
def.
a + nZ := { a + nk | k ∈ Z }
定義より、次の命題はほぼ明らかだと思う。
命題 7.4 自然数 n を法とし、 整数 a を代表元とする剰余類 C(a) は、C(a) = a + nZ で表わせる。
（証明）(i) C(a) ⊂ a + nZ であること : b ∈ C(a) =⇒ b ∈ a + nZ を示せばよい。b ∈ C(a) ならば、b ≡ a (mod n)。
よって、b − a = nk （k ∈ Z）と表せる。これより、b = a + nk （k ∈ Z）となるので b ∈ a + nZ。
(ii) C(a) ⊃ a + nZ であること : (i) と同様に、b ∈ a + nZ =⇒ b ∈ C(a) を示せばよい。練習問題。（証明終）
問題 : b ∈ a + nZ =⇒ b ∈ C(a) を示せ。
命題 7.5 自然数 n と整数 a、b に対して、次の (1)、(2)、(3) は同値。
(1) a ≡ b (mod n)。
(2) n を法として C(a) = C(b)。
(3) n を法として b ∈ C(a)。
（証明） (1)、(2)、(3) が同値であることを示すには、
「(1) ならば (2)」、
「(2) ならば (3)」、
「(3) ならば (1)」を示せばよ
い。これを示すと、例えば、「(2) ならば (1)」は、「(2) ⇒ (3) ⇒ (1)」のように考えれば、成立していることがわかる。
(1) ⇒ (2) : 仮定 (1) のもとで 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) も同様に示せる。
(2) ⇒ (3) : 命題 7.1 (1) より、a ∈ C(a)。ゆえに、仮定 (2) より a ∈ C(b) となる。
(3) ⇒ (1) : a ∈ C(b) より、a ≡ b (mod n) 。これに、命題 7.1 (2) を用いれば、b ≡ a (mod n) がいえる。（証明終）
系 7.6 整数 a、b が 自然数 n を法として合同でないとき、C(a)、C(b) に共通に含まれる整数は存在しない。
（証明） もし、c ∈ C(a) かつ c ∈ C(b) なる 整数 c が存在したとすると、命題 7.5 の (3) ⇒ (2) より、C(c) = C(a) かつ
C(c) = C(b) となる。ゆえに C(a) = C(b) となる。これと、命題 7.5 の (2) =⇒ (1) より、a ≡ b (mod n) となる。
（証明終）
39
系 7.7 自然数 n に対し、次の (1) − (3) が成立。
(1) n を法とする剰余類 C(0)、C(1)、· · · 、C(n − 1) は互いに相異なる。
(2) n を法とする任意の剰余類 C(a) は、C(0)、C(1)、· · · 、C(n − 1) のいずれかと一致する。
(3) 特に、n を法とする剰余類はちょうど n 個ある。
（証明） (1) もし、ある整数 r、r′ が、
C(r) = C(r′ )
0 ≤ r′ < n
0 ≤ r < n,
を満たすとする。命題 7.5 の (2) ⇒ (1) より、r ≡ r′ (mod n) となる。つまり、r − r′ は n の倍数。ここで、0 ≤ r, r′ ≤ n
なので。0 ≤ |r − r′ | < n。よって、r − r′ = 0。
(2) a を n で割り算して、
0≤r<n
a = qn + r,
と表わせたとする。a − r = qn は n の倍数なので、a ≡ r (mod n) となる。命題 7.5 の (1) ⇒ (2) より、C(a) = C(r)
となり、C(a) は、C(0)、· · · 、C(n − 1) のいずれかと一致する。
(3) (1)、(2) より明らか。（証明終）
定義 7.8 自然数 n を法とする剰余類全てからなる集合を Z/nZ と書く。
def.
Z/nZ := {C(0), C(1), · · · , C(n − 1)}.
7.3
どうしてそんなことを気にするのか
なぜ、前節で示した合同の性質が大事なのかについて説明しておく。後で詳しく調べるが、今考えている集合の元同士
の関係 a ∼ b があり、命題 7.1 のように、
(1) a ∼ a,
(3) a ∼ b,
(2)
a ∼ b =⇒ b ∼ a
a′
b ∼ c =⇒ a ∼ c
a”
b
のような関係を持つ場合、a は ∼ で辿って得られる要素
a ∼ b ∼ c ∼ d ∼ · · · の全てに対し、a ∼ a、a ∼ b、b ∼ a、
a ∼ c、c ∼ a a ∼ d、d ∼ a · · · のように関係を持ち合うが、
a と関係を持たない要素 a′ が存在したとして、a′ が他の要
素と関係 a′ ∼ b′ ∼ c′ ∼ d ∼ · · · を持つならば、a は、a′ 、
b′ 、c′ 、d′ 、のいずれとも関係を持たない。これより、考え
ている集合の中で、互いに関係を持たない a、a′ 、a′′ 、· · ·
があったとき、それぞれに関係を持つ元の集合は、共通部
分を持たないので、
「a と関係を持つ集合」、
「a′ と関係を持
つ集合」、
「a′′ と関係を持つ集合」、· · · で全体を分類するこ
とができる。(1)、(2)、(3) を満たす関係を 同値関係という。
40
a
b”
b′
c
d
c′