目次 †
剰余類 †
「a≡b (mod m)」は「a=b+km,k∈Z」と同じ意味である。この関係を一般化した概念が、剰余類（residue class）と呼ばれる。
[定義]
~\}~=~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の剰余類」＝「奇数全体の集合」
剰余系 †
mod mの剰余類全体の集合は類別の概念を使えば、
の
による類別と言い換えられる。つまり、
であり、これは剰余系と呼ばれ、
とも表記される。
[補講]は有限集合なので、扱いやすい。 ◇
剰余系に演算を定義 †
剰余系と合同式 †
剰余系は実質的に合同式と同じ。
と述べるか
において
と述べるかの違いである。
| 合同式 | 剰余系 |
| 集合 | （無限集合） | （有限集合） |
ただし、の元である各集合Aiは無限集合である。
[補講]とは意味がまったく異なる。しかし、演算の満たす性質という観点ではとても似ている。 ◇
剰余類群 †
は
なので、m個の要素を持つ。
=~\sharp~\{A_0,A_1,\cdots,A_{m-1}\}=m)
このは（加法に対して）群構造を持つので、剰余類群と呼ばれる。
[補講]剰余類群と巡回群
の
による類別、即ち剰余類群)
は加法巡回群である。
各元を何度か演算して、すべての元が生成されることを確かめられればよい。
例：
とし、)
が加法巡回群であることを調べる。
単位元は
である。
より、
は
または
を生成元とする巡回群である。 ◇
法が素数の剰余系から要素0を取り除いた集合 †
[定義]
pを素数とするとき、
から要素0だけを取り除いた集合
を^{*})
で表す。
積について閉じている †
ここで定義した集合は積について閉じている。
は整域
⇔
⇔
（∵対偶）
ここで、^{*}~\not{\ni}~0)
より、^{*};~ab~\not{=}0)
よって、^{*})
□
写像faが全単射 †
^{*})
とする。
ここで、からのfa=axを定める。
は積について閉じているので、faは写像である。
[定理]
p：素数
^{*}~;~f_a~:~(\mathbb{Z}/p~\mathbb{Z})^{*}~\rightarrow~(\mathbb{Z}/p~\mathbb{Z})^{*})
は単射
[証明]背理法を用いる。
^{*}~\wedge~x_1~\not{=}~x_2;~f_a(x_1)=f_a(x_2))
が成り立つと仮定する。
=0)
（∵Z/pZ：整域∧a≠0）
∴
矛盾。
よって、^{*}~\wedge~x_1~\not{=}~x_2)
⇒~\not{=}~f_a(x_2))
⇒fa：単射 □
[定理]
p：素数
は全単射
[証明]上記の結果より、faは単射
また、faは有限集合からそれ自身への写像である。
よって、faは全単射である。 □
逆元の存在 †
[定理]
p：素数、^{*})
とする。
このとき、^{*}~\,~s.t.~\,~ax=1)
これは次のようにも言い換えられる。
[定理]
p：素数とする。
このとき、^{*})
の要素は、において逆元を持つ。
[証明]^{*})
とおく。
は全単射
また、「1∈B∧fa：全射」より、=1)
さらに、faは単射より、このようなxはただ一つのみである。 □
フェルマーの小定理 †
フェルマーの小定理をで表現すると次のようになる。
[定理]
p：素数、とすると、
が成り立つ。
[証明]faは全単射より、,f_a(2),\cdots,f_a(p-1))
は、の要素
の並べ替えに過ぎない。
~\times~f_a(2)~\times~\cdots~\times~f_a(p-1)~=~1~\times~2~\times~\cdots~\times~(p-1))
~\times~(a~\cdot~2)~\times~\cdots~\times~(a~\cdot~(p-1))~=~1~\times~2~\times~\cdots~\times~(p-1))
!~=~(p-1)!)
!~-~(p-1)!=0)
(p-1)!=0)
（∵「Z/pZ：整域」∧「(p-1)!≠0」）
□
剰余系の要素のうち法と素なものを集めた集合 †
[定義]の要素のうちmと互いに素なものだけを集めた集合を^{*})
と表記する。
すると、（pは素数）のときと同様に、（mは素数あるいは合成数）は積について閉じている。
このについても、と同様なストーリーでフェルマーの小定理まで示すことができるのだろうか？
1：^{*})
に対して、faが単射であることを示す。
2：fa有限集合から自身への単射なので、faは全単射
3：^{*}~\}~:=~l)
として、^{*}~=~\{~a_1,\cdots,a_l~\})
と表すことにする。
faは全単射より、,\cdots,f_a(a_l))
は
の並べ変えに過ぎない。
=0)
（
とおく）
4：等式からにおいて、
がいえればよい。
これは言い換えると、
に対応する。
このストーリーにおける問題はステップ1である。まずステップ1を考察する。
^{*}~\wedge~x_1~\not{=}~x_2~\Rightarrow~f_a(x_1)=f_a(x_2))
と仮定する。
（
において）
（ここで=1)
ならば）
∴
矛盾するので、faは単射になる。 □
以上により、ならば、
が成り立つ。これをオイラーの定理という。
さらに、lは久留島・オイラー関数と一致する。
)
したがって、次のように言い換えられる。
[定理]オイラーの定理
=1~\Rightarrow~a^{\phi~(m)}~\equiv~1~\pmod{m})
