• 追加された行はこの色です。
  • 削除された行はこの色です。
  • 剰余類 へ行く。

*目次 [#cf70e3bc]

#contents


*剰余類 [#p2f7bd67]

 「a≡b (mod m)」は「a=b+km,k∈Z」と同じ意味である。この関係を一般化した概念が、''剰余類(residue class)''と呼ばれる。

[定義]~
&mimetex("\{ b| b \equiv a \, (mod\, m ) \} = a+mZ");を、「a mod mの剰余類」と呼ぶ。

例:

-「1 mod 3の剰余類」={1,1±3,1±2・3,1±3・3,…}={1,-2,4,-5,7,10,…}
-「0 mod 2の剰余類」=「偶数全体の集合」
-「1 mod 2の剰余類」=「奇数全体の集合」

*剰余系 [#fa6d9d22]

 mod mの剰余類全体の集合は[[類別]]の概念を使えば、&mimetex("\mathbb{Z}");の&mimetex("m \mathbb{Z}");による類別と言い換えられる。つまり、&mimetex("\mathbb{Z}/m\mathbb{Z}");であり、これは''剰余系''と呼ばれ、&mimetex("\mathbb{Z}_m");とも表記される。

&mimetex("\mathbb{Z}/m\mathbb{Z} = \mathbb{Z}_m= \{A_0,A_1,\cdots,A_{m-1}\}");

[補講]&mimetex("\mathbb{Z}_m");は有限集合なので、扱いやすい。 ◇

**剰余系に演算を定義 [#s96a8043]

*剰余系と合同式 [#g24aa432]
**剰余系と合同式 [#g24aa432]

 剰余系は実質的に合同式と同じ。

&mimetex("a+b \equiv c \pmod{n}");

と述べるか

&mimetex("\mathbb{Z}/n\mathbb{Z}");において&mimetex("a+b=c");

と述べるかの違いである。

||合同式|剰余系|
|集合|&mimetex("\mathbb{Z}");(無限集合)|&mimetex("\mathbb{Z}/n\mathbb{Z}");(有限集合)|

ただし、&mimetex("\mathbb{Z}/n\mathbb{Z}");の元である各集合ASUB{i};は無限集合である。

[補講]&mimetex("\mathbb{Z}");と&mimetex("\mathbb{Z}/n\mathbb{Z}");は意味がまったく異なる。しかし、演算の満たす性質という観点ではとても似ている。 ◇



*剰余類群 [#p53790a3]

 &mimetex("\mathbb{Z}_m");は&mimetex("\{A_0,A_1,\cdots,A_{m-1}\}=m");なので、m個の要素を持つ。

&mimetex("\sharp (\mathbb{Z}_m)= \sharp \{A_0,A_1,\cdots,A_{m-1}\}=m");

 この&mimetex("\mathbb{Z}_m");は(加法に対して)群構造を持つので、''剰余類群''と呼ばれる。

[補講]剰余類群と巡回群

 &mimetex("\mathbb{Z}");の&mimetex("n \mathbb{Z}");による類別、即ち剰余類群&mimetex("\mathbb{Z} / n \mathbb{Z} (= \mathbb{Z}_n)");は加法巡回群である。

 各元を何度か演算して、すべての元が生成されることを確かめられればよい。

例:&mimetex("\mathbb{Z}_3=\{ A_0,A_1,A_2 \}");とし、&mimetex("(\mathbb{Z}_3;+)");が加法巡回群であることを調べる。

 単位元は&mimetex("A_0");である。

-&mimetex("1A_0=A_0");
-&mimetex("1A_1=A_1,\; 2A_1=A_1+A_1=A_2,\; 3A_1=A_1+A_1+A_1=A_3=A_0");
-&mimetex("1A_2=A_2,\; 2A_2=A_2+A_2=A_4=A_1,\; 3A_2=A_2+A_2+A_2=A_6=A_0");

より、&mimetex("\mathbb{Z}_3");は&mimetex("A_1");または&mimetex("A_2");を生成元とする巡回群である。 ◇


*法が素数の剰余系から要素0を取り除いた集合 [#cf38739f]

[定義]~
pを素数とするとき、&mimetex("\mathbb{Z}/p\mathbb{Z} = \{ 0,1, \cdots, p-1 \}");から要素0だけを取り除いた集合&mimetex("\{1,2,\cdots,p-1\}");を&mimetex("(\mathbb{Z}/p \mathbb{Z})^{*}");で表す。
**積について閉じている [#nbcb554c]

 ここで定義した集合&mimetex("(\mathbb{Z}/p \mathbb{Z})^{*}");は積について閉じている。

&mimetex("\mathbb{Z}/p\mathbb{Z}");は整域~
⇔&mimetex("a,b \in \mathbb{Z}/p\mathbb{Z}; ab=0 \Rightarrow a=0 \vee b=0");~
⇔&mimetex("a,b \in \mathbb{Z}/p\mathbb{Z}; a \not{=} 0 \wedge b \not{=} 0 \Rightarrow ab \not{=}0"); (∵対偶)

ここで、&mimetex("(\mathbb{Z}/p \mathbb{Z})^{*} \not{\ni} 0");より、&mimetex("a,b \in (\mathbb{Z}/p\mathbb{Z})^{*}; ab \not{=}0");

よって、&mimetex("ab \in (\mathbb{Z}/p \mathbb{Z})^{*}"); □


**写像fSUB{a};が全単射 [#n073f782]

&mimetex("a \in (\mathbb{Z}/p \mathbb{Z})^{*}");とする。

ここで、&mimetex("a \in (\mathbb{Z}/p \mathbb{Z})^{*}");から&mimetex("a \in (\mathbb{Z}/p \mathbb{Z})^{*}");のfSUB{a};=axを定める。

&mimetex("(\mathbb{Z}/p \mathbb{Z})^{*}");は積について閉じているので、fSUB{a};は写像である。

[定理]~
p:素数~
&mimetex("\forall a \in (\mathbb{Z}/p \mathbb{Z})^{*} ; f_a : (\mathbb{Z}/p \mathbb{Z})^{*} \rightarrow (\mathbb{Z}/p \mathbb{Z})^{*}");は単射

[証明]背理法を用いる。

&mimetex("x_1,x_2 \in (\mathbb{Z}/p \mathbb{Z})^{*} \wedge x_1 \not{=} x_2; f_a(x_1)=f_a(x_2)");が成り立つと仮定する。

&mimetex("ax_1=ax_2");~
&mimetex("ax_1-ax_2=0");~
&mimetex("a(x_1-x_2)=0");~
&mimetex("x_1-x_2=0"); (∵Z/pZ:整域∧a≠0)~
∴&mimetex("x_1=x_2");

矛盾。

よって、&mimetex("x_1,x_2 \in (\mathbb{Z}/p \mathbb{Z})^{*} \wedge x_1 \not{=} x_2");~
⇒&mimetex("f_a(x_1) \not{=} f_a(x_2)");~
⇒fSUB{a};:単射 □

[定理]~
p:素数~
&mimetex("\forall a \in (\mathbb{Z}/p \mathbb{Z})^{*} ; f_a : (\mathbb{Z}/p \mathbb{Z})^{*} \rightarrow (\mathbb{Z}/p \mathbb{Z})^{*}");は全単射

[証明]上記の結果より、fSUB{a};は単射

また、fSUB{a};は有限集合&mimetex("(\mathbb{Z}/p \mathbb{Z})^{*}");からそれ自身への写像である。

よって、fSUB{a};は全単射である。 □


**逆元の存在 [#l016a2ed]

[定理]~
p:素数、&mimetex("a \in (\mathbb{Z}/p\mathbb{Z})^{*}");とする。
このとき、&mimetex("\exists x \in (\mathbb{Z}/p\mathbb{Z})^{*} \, s.t. \, ax=1");

 これは次のようにも言い換えられる。

[定理]~
p:素数とする。
このとき、&mimetex("(\mathbb{Z}/p\mathbb{Z})^{*}");の要素は、&mimetex("(\mathbb{Z}/p\mathbb{Z})^{*}");において逆元を持つ。

[証明]&mimetex("A=B=(\mathbb{Z}/p\mathbb{Z})^{*}");とおく。

&mimetex("f_a : A \rightarrow B");は全単射

また、「1∈B∧fSUB{a};:全射」より、&mimetex("\exists x \in A \, s.t. \, f_a(x)=1");

さらに、fSUB{a};は単射より、このようなxはただ一つのみである。 □


**フェルマーの小定理 [#d2440d0d]

 [[フェルマーの小定理]]を&mimetex("\mathbb{Z}/p\mathbb{Z}");で表現すると次のようになる。

[定理]~
p:素数、&mimetex("a \in (\mathbb{Z}/p\mathbb{Z})^{*}");とすると、&mimetex("a^{p-1} = 1");が成り立つ。


[証明]fSUB{a};は全単射より、&mimetex("f_a(1),f_a(2),\cdots,f_a(p-1)");は、&mimetex("(\mathbb{Z}/p\mathbb{Z})^{*}");の要素&mimetex("\{ 1,2,\cdots, p-1 \}");の並べ替えに過ぎない。

&mimetex("f_a(1) \times f_a(2) \times \cdots \times f_a(p-1) = 1 \times 2 \times \cdots \times (p-1)");~
&mimetex("(a \cdot 1) \times (a \cdot 2) \times \cdots \times (a \cdot (p-1)) = 1 \times 2 \times \cdots \times (p-1)");~
&mimetex("a^{p-1} \cdot (p-1)! = (p-1)!");~
&mimetex("a^{p-1} \cdot (p-1)! - (p-1)!=0");~
&mimetex("(a^{p-1} -1)(p-1)!=0");~
&mimetex("a^{p-1} -1=0"); (∵「Z/pZ:整域」∧「(p-1)!≠0」)~
&mimetex("a^{p-1} =1"); □

*剰余系の要素のうち法と素なものを集めた集合 [#n5062ab5]

[定義]&mimetex("\mathbb{Z}/m\mathbb{Z}");の要素のうちmと互いに素なものだけを集めた集合を&mimetex("(\mathbb{Z}/m\mathbb{Z})^{*}");と表記する。

 すると、&mimetex("(\mathbb{Z}/p\mathbb{Z})^{*}");(pは素数)のときと同様に、&mimetex("(\mathbb{Z}/m\mathbb{Z})^{*}");(mは素数あるいは合成数)は積について閉じている。

 この&mimetex("(\mathbb{Z}/m\mathbb{Z})^{*}");についても、&mimetex("(\mathbb{Z}/p\mathbb{Z})^{*}");と同様なストーリーでフェルマーの小定理まで示すことができるのだろうか?

1:&mimetex("a \in (\mathbb{Z}/m\mathbb{Z})^{*}");に対して、fSUB{a};が単射であることを示す。

2:fSUB{a};有限集合から自身への単射なので、fSUB{a};は全単射

3:&mimetex("\sharp \{ (\mathbb{Z}/m\mathbb{Z})^{*} \} := l");として、&mimetex("(\mathbb{Z}/m\mathbb{Z})^{*} = \{ a_1,\cdots,a_l \}");と表すことにする。

 fSUB{a};は全単射より、&mimetex("f_a(a_1),\cdots,f_a(a_l)");は&mimetex("a_1,\cdots,a_l");の並べ変えに過ぎない。

&mimetex("K(a^l-1)=0"); (&mimetex("K=a_1 \times \cdots \times a_l");とおく)

4:等式から&mimetex("\mathbb{Z}/m\mathbb{Z}");において、&mimetex("a^l = 0");がいえればよい。

 これは言い換えると、&mimetex("a^l \equiv 1 \pmod{m}");に対応する。

 このストーリーにおける問題はステップ1である。まずステップ1を考察する。

&mimetex("x_1,x_2 \in (\mathbb{Z}/m\mathbb{Z})^{*} \wedge x_1 \not{=} x_2 \Rightarrow f_a(x_1)=f_a(x_2)");と仮定する。

(&mimetex("\mathbb{Z}/m\mathb{Z}");において)&mimetex("ax_1=ax_2");~
&mimetex("a(x_1-x_2)=0");~
&mimetex("x_1-x_2=0"); (ここで&mimetex("(a,m)=1");ならば)~
∴&mimetex("x_1=x_2");

矛盾するので、fSUB{a};は単射になる。 □

 以上により、&mimetex("(a,m)=1");ならば、&mimetex("a^l=1");が成り立つ。これを''[[オイラーの定理]]''という。

 さらに、lは[[久留島・オイラー関数]]と一致する。

&mimetex("l = \phi (m)");

 したがって、次のように言い換えられる。

[定理]オイラーの定理~
&mimetex("(a,m)=1 \Rightarrow a^{\phi (m)} \equiv 1 \pmod{m} ");