剰余類環のソースを表示

{{otheruses|自然数を法とする合同関係に関する整数の剰余類の成す代数系|環をイデアルで割って得られる一般の剰余類環|剰余環}}
{{出典の明記|date=2016年4月}}
[[数学]]において、[[自然数]] {{mvar|n}} を法とする'''合同類環'''（ごうどうるいかん）あるいは'''剰余'''（'''類'''）'''環'''（じょうよ[るい]かん、{{lang-en-short|''residue'' [''class''] ''ring'' modulo {{mvar|n}}}}, {{lang-de-short|''Restklassenring'' modulo {{mvar|n}}}}）は、[[整数]]を {{mvar|n}} で割った「剰余」を抽象的な類別として捉えたものである。

本項は剰余類環 {{math|'''Z'''/''n'''''Z'''}} の代数的な定義と性質について述べる。合同類別に関するより平易な導入については[[整数の合同]]を参照のこと。

== 定義 ==
{{math|''n'' &ge; 2}} を自然数とする。{{mvar|n}} で[[除法|割]]った剰余が等しい整数をすべて集めたものを、「{{mvar|n}} を法とする」'''合同類'''あるいは'''[[剰余類]]'''と呼ぶ。したがって、ふたつの整数が同じ剰余類に属するのは、それらの差が {{mvar|n}} で整除されるときであり、かつそのときに限る。{{mvar|n}} を法とする剰余類の全体は、以下に述べる加法と乗法に関して {{mvar|n}} を法とする'''合同類環'''あるいは'''剰余類環'''と呼ばれる環を成す。剰余類環はしばしば {{math|'''Z'''/{{mvar|n}}'''Z''', '''Z'''/{{mvar|n}}, '''Z'''<sub>''n''</sub>}} などで表される。

剰余類に対する加法および乗法は、'''代表元''' ({{lang|en|representive}}, {{lang|de|Vertreter}}) とも呼ばれる、各剰余類に属する任意の元（これは通常の整数）に対して整数としての加法および乗法を行い、その結果として得られる和および積の属する剰余類を対応させるものである。これは {{mvar|a}} の属する剰余類を {{math|&#x005b;''a''&#x005d;}} と表せば
:<math> [a]+[b]:=[a + b], \quad [a]\times [b]:=[a\times b]</math>

と表せる。ここで、この演算が「剰余類に対する[[二項演算|演算]]」として[[well-defined|きちんと定義されている]]ことは、結果（和や積）として求まる剰余類が[[同値関係|代表元]]の取り方に依らないこと、すなわち、{{math|''a''<sub>1</sub>, ''b''<sub>1</sub>, ''a''<sub>2</sub>, ''b''<sub>2</sub>}} を {{math|&#x005b;''a''<sub>1</sub>&#x005d; {{=}} &#x005b;''b''<sub>1</sub>&#x005d;}} かつ {{math|&#x005b;''a''<sub>2</sub>&#x005d; {{=}} &#x005b;''b''<sub>2</sub>&#x005d;}} を満たす任意の整数とすれば、

:<math>[a_1 + a_2] = [b_1 + b_2], \quad [a_1\times a_2] = [b_1\times b_2]</math> 
が成り立つことから確認できる。

== 表記と慣例について ==
{{math|'''Z'''<sub>''n''</sub>}} と書くと、素数 {{mvar|p}} に対する[[p進数| {{mvar|p}}-進整数]]全体の成す環 {{math|'''Z'''<sub>''p''</sub>}} と混同のおそれがあり、剰余類環を {{math|'''Z'''<sub>''n''</sub>}} で表すことを好む文脈では、{{mvar|p}}-進整数の全体は <math>\hat{\mathbb{Z}}_p</math> で表すこともある。しかし、{{math|'''Z'''/''n'''''Z'''}} と書く<ref>あるいは {{math|'''Z'''/''n'''''Z'''}} と書く代わりに {{math|'''Z'''/(''n'')}} と書くこともある。これは一般に、環 {{mvar|R}} の元 {{mvar|a}} が生成する {{mvar|R}} の単項両側イデアルはしばしば {{math|(''a'')}} で表され、それにしたがえば {{math|'''Z'''}} のイデアルとして {{math|''n'''''Z''' {{=}} (''n'')}} となることによる。</ref>のが、面倒だがもっとも誤解は少ないだろう。また、{{math|'''Z'''/''n''}} という表記もあるが稀であり、加えて
:<math>{1\over n}\mathbb{Z} := \left\{{k\over n};\ k\in\mathbb{Z}\right\}</math>
なる集合と紛らわしい。

[[記号の濫用]]だが、記述の面倒を避けるため慣例的に、同値類を表すのに代表元に施す[[ブラケット|角括弧]]をしばしば省略して、代表元とそれが属する合同類とを同じ文字で表す。したがってこのとき、同じ合同類を表すのに無数の符牒が与えられていることになる。たとえば、{{math|''n'' {{=}} 0}} および {{math|''n'' &minus; 1 {{=}} &minus;1}} は {{math|'''Z'''/''n'''''Z'''}} に属する合同類の間の関係式と考えれば有効な式である。また、慣例的に合同類を表す符牒が無数にあるという不定性を除くために、各合同類から「標準的」{{lang|en|(canonical)}} な代表元を選んで、それと合同類とを同一視することもよく行われる。

このような慣例的規約に従えば、剰余類環 {{math|('''Z'''/''n'''''Z''', +, &times;)}} は {{math|0, 1, ..., ''n'' &minus; 1}} の {{mvar|n}} 個の元からなる。また、次の式
:<math>(a + b) \bmod n, \quad (a\times b) \bmod n</math>

は整数環 {{math|'''Z'''}} における演算から得られる合同類を表すものであるけれども、規約に従えば、それと同時に {{math|'''Z'''/{{mvar|n}}'''Z'''}} における演算そのものを表しているものと、直ちに解釈することができる。また、剰余類環における（和や積といった）算術演算を繰り返す計算（すなわち、{{math|'''Z'''/{{mvar|n}}'''Z'''}} 係数の多項式 {{math|''p''(''X'')}} の、{{math|'''Z'''/{{mvar|n}}'''Z'''}} の任意の元 {{math|''k''}} における値 {{math|''p''(''k'')}} の評価）は、それを整数と見て計算した結果について、法 {{mvar|n}} に関する剰余を取ればよい。この最後の操作をモジュラー簡約 {{lang|en|(modular reduction)}} などともいう。ただし、モジュラー簡約の操作は整数と見ての計算の途中のどんな場所でも行ってよい。

[[2の冪|2-冪]] {{math|''n'' {{=}} 2<sup>''k''</sup>}} に対しては、{{math|0}} に関して対称な代表系
: <math>\left\{-{n\over 2},\ldots,-1,0,1,\ldots,{n\over 2}-1\right\}</math>
をとることもできる。これはつまりビット列としての整数の表示、いわゆる二進表示に対応するものである。

== 性質 ==

任意の自然数 {{math|''n'' &ge; 2}} に対して {{math|'''Z'''/{{mvar|n}}'''Z'''}} は、{{math|{{mvar|n}}'''Z'''}} を零元、{{math|1 + {{mvar|n}}'''Z'''}} を単位元とする[[可換環]]を成す。

{{mvar|p}} が[[素数]]ならば剰余類環 {{math|'''Z'''/{{mvar|p}}'''Z'''}} は、{{mvar|p}} を法とする[[剰余体]]とも呼ばれる、位数 {{mvar|p}} の[[有限体]]を成し、（体を表す英語 {{lang|en|"field"}} の頭文字をとって）{{math|'''F'''<sub>''p''</sub>}} とも書かれる。各元の[[乗法逆元|乗法に関する逆元]]は[[ユークリッドの互除法]]を用いて簡単に計算することができる。

一方、{{mvar|n}} が素数でないならば、{{mvar|n}} の任意の約数が[[零因子]]となって乗法逆元を持たないので、{{mvar|n}} を法とする剰余環は[[可換体|体]]にはならない。{{mvar|n}} との[[最大公約数]] {{math|(''a'', ''n'')}} が {{math|1}} である（つまり {{mvar|n}} と[[互いに素 (整数論)|互いに素]]である）ような整数 {{mvar|a}} に対し、合同類 {{math|''a'' + {{mvar|n}}'''Z'''}} は、法 {{mvar|n}} に関する[[既約剰余類]]または既約合同類と呼ばれる。既約剰余類の全体は{{仮リンク|既約剰余類群|en|Multiplicative group of integers modulo n}}と呼ばれる群 {{math|('''Z'''/{{mvar|n}}'''Z''')<sup>&times;</sup>}} を成す。これは環 {{math|'''Z'''/{{mvar|n}}'''Z'''}} の[[単数群]]であり、その位数は[[オイラーのφ函数|オイラー数]] {{math|&phi;(''n'')}} である。

== 例 ==

=== 時計の文字盤の表示 ===
[[file:Clock group.svg|thumb|{{math|12}} を法として計算される時計の針]]
合同類における算術の一つの例を[[アナログ時計]]の文字盤を使って図示することができる。時計の文字盤には「時間」に応じて 1 から 12 までの番号が振られていて「12時」は「0時」と同一であり、「0時」から始めて「1時間」加えるごとに順番に、12の数字のそれぞれを辿ることができる。

「時間」を足し算するには、加えられるほうの時間を起点にして、加えたい時間ぶんだけ時計を進めればよい。たとえば {{math|4 + 5}} がいくつになるのか知りたければ、「4時」のところを起点にして「5時間」後にいる場所が「9時」のところなので {{math|4 + 5 {{=}} 9}} という具合である。これで {{math|9 + 5}} がいくつになるか計算してみよう。同様に「9時」のところを基点に、針を「5時間」進めると「2時」のところにいるはずである。つまり、この系のなかでは {{math|9 + 5 {{=}} 2}} ということになる。さて、どうしてこうなるのか少し考えてみよう。単純に {{math|5}} と {{math|9}} とを足し合わせると {{math|14}} となるのだが、時計の盤面では「14時」は「2時」と一致するから、ここでは {{math|14 {{=}} 2}} であったわけで、ここでの加法はふつうの和を計算してから12を引けるだけ引いたものということになる。これは {{math|12}} を法とする剰余類に相当し、このタイプの足し算は「{{math|12}} を法とする加法（{{math|modulo 12}} の加法）」と呼ばれる。このとき、{{math|12}} を加えることは、どの「時間」{{math|''x''}} についても {{math|12 + ''x'' {{=}} ''x''}} となるから、何の変化ももたらさない。これで「12時」の数字が「0時」のところに配置される理由を説明できる。

乗法は加法から得られる。例えば、{{math|3 &times; 4}} を計算したければ、これを {{math|3 + 3 + 3 + 3}} という和の形に書き直して、{{math|12}} を引けばよい。{{math|4 &times; 4}} なら「16時」は {{math|modulo 12}} で「4時」なので {{math|4 &times; 4 {{=}} 4}} となる。

そういうわけで、「時間」にこのような加法や乗法を考えたものとして剰余類環 {{math|('''Z'''/12'''Z''', +, &times;)}} を表すことができる。

本節で {{math|12}} としていたところを、任意の自然数 {{mvar|n}} に置き換えても同じことができる。たとえば {{math|'''Z'''/4'''Z''' {{=}} {0, 1, 2, 3} }}においては {{math|1 {{=}} 1, 2 {{=}} 1 + 1, 3 {{=}} 1 + 1 + 1, 0 {{=}} 1 + 1 + 1 + 1}} である。

=== 2 を法とする剰余類環 ===
整数を {{math|2}} で割った剰余は {{math|0}} か {{math|1}} となるから、{{math|'''Z'''/2'''Z''' {{=}} {0, 1} }}であり、これはすべての剰余類環のなかで位数最小のものである。また、{{math|2}} は素数なのでこれは位数最小の有限体 {{math|'''F'''<sub>2</sub>}} とも一致する。

=== 3 を法とする剰余類環 ===

法 {{math|3}} に関する剰余類は
* <math>\mathbf{0} := [0] = \{\ldots, -6, -3; 0, 3, 6, 9, 12, \ldots\}</math>: {{math|3}} で割り切れるもの
* <math>\mathbf{1} := [1] = \{\ldots, -5, -2; 1, 4, 7, 10, 13,\ldots\}</math>: {{math|3}} で割って {{math|1}} 余るもの
* <math>\mathbf{2} := [2] = \{\ldots, -4, -1; 2, 5, 8, 11, 14,\ldots\}</math>: {{math|3}} で割って {{math|2}} 余るもの

の三種類である。ここでたとえば、{{math|'''1''' + '''2'''}} を計算したいときは、{{math|4 &isin; '''1'''}} および {{math|8 &isin; '''2'''}} で {{math|4 + 8 {{=}} 12 &isin; '''0'''}} だから {{math|'''1''' + '''2''' {{=}} '''3'''}} とすればよい。このようにして {{math|'''Z'''/3'''Z''' {{=}} {'''0''', '''1''', '''2'''} }}における演算表

{| style="margin: 1ex auto 1ex auto;"
|-
|
{| class="wikitable" 
|+ '''加法'''
|-
! + !! ''0'' !! ''1'' !! ''2''
|-
! ''0''
| '''0''' || '''1''' || '''2'''
|-
! ''1'' 
| '''1''' || '''2''' || '''0'''
|-
! ''2'' 
| '''2''' || '''0''' || '''1'''
|}
||
{| class="wikitable" 
|+ '''乗法'''
|-
! &times; !! ''0'' !! ''1'' !! ''2''
|-
! ''0'' 
| '''0''' || '''0''' || '''0'''
|-
! ''1'' 
| '''0''' || '''1''' || '''2'''
|-
! ''2'' 
| '''0''' || '''2''' || '''1'''
|}
|}

が得られる。{{math|('''Z'''/3'''Z''', +, &times;)}} は環であり、この場合さらに[[可換体|体]]となり、{{math|'''F'''<sub>3</sub>}} で表される（英語で体を意味する {{lang|en|"field"}} に由来）。

=== 4 を法とする剰余類環 ===

もうひとつ、法 4 に関する剰余類を考えよう。{{math|'''Z'''/4'''Z''' {{=}} {'''0''', '''1''', '''2''', '''3'''} }}は
* <math>\mathbf{0} = \{\ldots, -4; 0, 4, 8, 12, 16,\ldots\}</math>
* <math>\mathbf{1} = \{\ldots, -3; 1, 5, 9, 13, 17,\ldots\}</math>
* <math>\mathbf{2} = \{\ldots, -2; 2, 6, 10, 14, 18,\ldots\}</math>
* <math>\mathbf{3} = \{\ldots, -1; 3, 7, 11, 15, 19,\ldots\}</math>

で与えられる。この剰余類の乗法では {{math|'''2''' &times; '''2''' {{=}} '''0'''}} となり、{{math|'''2'''}} は[[零因子]]である。したがって、{{math|'''Z'''/4'''Z''' &#x2216; {'''0'''} }}は乗法について閉じていない。このことから、代数系 {{math|('''Z'''/4'''Z''', +, &times;)}} は（{{math|4}} を法とする剰余類環として）可換環を成すのみで、零因子が[[逆元|乗法逆元]]を持たないため体にはならない（位数 {{math|4}} の有限体 {{math|'''F'''<sub>4</sub>}} は存在するにもかかわらず、である）。

=== 計算機 ===
[[コンピュータ]]など[[計算機]]において多用される固定長の[[整数型]]の演算は、剰余類環における演算である。たとえば16ビットの場合 {{math|2<sup>16</sup> {{=}} 65536}} であるから（しばしば short integer として扱われる）16ビット整数の全体は剰余類環 {{math|'''Z'''/65536'''Z'''}} を成す。たとえば、足し算 {{math|65535 + 1}} の結果として計算機は {{math|0}} を返し、{{math|32768&times;2}} も同様に {{math|0}} になる（以上は符号無し（unsigned）の場合）。

== 一般化 ==
剰余類の概念は整数環ではないほかの環に対しても考えることができる。[[イデアル (環論)|イデアル]]の概念を定義して、イデアルを法とする剰余類を構成すれば、それらの全体は再び環を成し、環のイデアルによる[[剰余環|剰余（類）環]]あるいは商環と呼ばれる。

== 脚注 ==
{{Reflist}}

{{DEFAULTSORT:しようよるいかん}}
[[Category:初等整数論]]
[[Category:合同算術]]
[[Category:数学に関する記事]]