合同式ごうどうしきcongruenceと mod 演算えんざんoperation

合同式ごうどうしきを「余あまりが同おなじ」という計算けいさん規則きそくだけで見みると、何故なぜ足たし算ざんや掛かけ算ざんが正当化せいとうかされるのかが見みえにくい。抽象代数ちゅうしょうだいすうでは、合同式ごうどうしきを剰余類じょうよるいの等号とうごうとして見みる。

とは、

という意味いみであり、同時どうじに $$a$$a と $$b$$b が同おなじ剰余類じょうよるいに属ぞくするという意味いみでもある。

1剰余類じょうよるい全体ぜんたい

$$n\text{[PARSE ERROR: Undefined("Command("ge")")]}2$$n\ge 2 とする。整数全体せいすうぜんたいを $$n$$n で割わった余あまりによって分類ぶんるいすると、商集合しょうしゅうごう

が得えられる。この集合しゅうごうの元げんは整数せいすうではなく、整数せいすうの同値類どうちるいである。

ここでの商集合しょうしゅうごうとは、同おなじ余あまりを持もつ整数せいすうを一ひとつの類るいにまとめ、その類るいを元げんとして扱あつかう集合しゅうごうである。

この講義こうぎでは法ほう $$n$$n を固定こていし、$$[a{]}_n$$[a]_n を $$\left[a\right]$$[a] と略記りゃくきする。法ほうを変かえると剰余類じょうよるいも変かわるので、複数ふくすうの法ほうを同時どうじに扱あつかうときは添字そえじを戻もどす。

2足たし算ざんと掛かけ算ざん

剰余類じょうよるいの加法かほうと乗法じょうほうを

で定義ていぎする。

ここで重要じゅうようなのは、右辺うへんが代表元だいひょうげんの選えらび方かたによらないことである。もし $$a\equiv a^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv a'\pmod n、$$b\equiv b^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$b\equiv b'\pmod n なら、

は $$n$$n の倍数ばいすうである。また、

も $$n$$n の倍数ばいすうである。したがって和わと積せきは代表元だいひょうげんによらず定さだまる（well-defined である）。

3加法かほうについて群ぐんになること

代表元だいひょうげんによらず和わが定さだまったので、$$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) の群ぐんの条件じょうけんを確認かくにんできる。閉包性へいほうせいは $$\left[a\right]+\left[b\right]=[a+b]\in \mathbb{Z}/n\mathbb{Z}$$[a]+[b]=[a+b]\in\mathbb Z/n\mathbb Z から従したがう。結合法則けつごうほうそくは

である。$$\left[0\right]$$[0] が単位元たんいげんであり、$$\left[a\right]$$[a] の逆元ぎゃくげんは $$[-a]$$[-a] である。さらに $$\left[a\right]+\left[b\right]=[a+b]=[b+a]=\left[b\right]+\left[a\right]$$[a]+[b]=[a+b]=[b+a]=[b]+[a] なので可換かかんである。したがって $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) は可換群かかんぐんである。

乗法じょうほうについても、整数せいすうの法則ほうそくを剰余類じょうよるいへ移うつせる。たとえば結合法則けつごうほうそくと左分配法則ひだりぶんぱいほうそくは

である。同様どうように乗法じょうほうの可換性かかんせいと右分配法則みぎぶんぱいほうそくも従したがい、$$\left[1\right]$$[1] は乗法じょうほうの単位元たんいげんである。ただし、すべての元げんが乗法逆元じょうほうぎゃくげんを持もつわけではない。この加法かほうと乗法じょうほうの構造こうぞうは、後あとで環かんの公理こうりとして整理せいりする。

4逆元ぎゃくげんがある条件じょうけん

剰余類じょうよるい $$\left[a\right]$$[a] が乗法逆元じょうほうぎゃくげんを持もつとは、ある $$\left[x\right]$$[x] が存在そんざいして

となることである。これは

と同おなじである。

この合同式ごうどうしきが解かいを持もつための必要十分条件ひつようじゅうぶんじょうけんは

である。実際じっさい、$$ax\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ax\equiv1\pmod n なら $$ax-1=kn$$ax-1=kn となる整数せいすう $$k$$k がある。$$a$$a と $$n$$n の公約数こうやくすうは $$ax-kn=1$$ax-kn=1 も割わるので、$$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1 である。逆ぎゃくに $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1 なら、ベズーの等式とうしきにより整数せいすう $$x,y$$x,y が存在そんざいして

となる。したがって $$ax\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ax\equiv1\pmod n であり、$$\left[x\right]$$[x] が $$\left[a\right]$$[a] の逆元ぎゃくげんになる。

この条件じょうけんは代表元だいひょうげんにもよらない。$$a^{\prime }=a+kn$$a'=a+kn なら、$$a$$a と $$n$$n の公約数こうやくすうは $$a^{\prime }$$a' も割わり、$$a^{\prime }$$a' と $$n$$n の公約数こうやくすうは $$a=a^{\prime }-kn$$a=a'-kn も割わる。したがって $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a^{\prime },n)$$\gcd(a,n)=\gcd(a',n) である。

ここでは文字もじで割わり算ざんをするのではなく、最大公約数さいだいこうやくすうが 1 であることから逆元ぎゃくげんの存在そんざいを示しめしている。したがって、割わる操作そうさを行おこなう場面ばめんでは、逆元ぎゃくげんが存在そんざいする条件じょうけんを先さきに確認かくにんする必要ひつようがある。

5合同式ごうどうしきでは常つねに約分やくぶんできるとは限かぎらない

は成立せいりつするが、$$1\text{[PARSE ERROR: Undefined("Command("not")")]}\equiv 4\text{[PARSE ERROR: Undefined("Command("pmod")")]}6$$1\not\equiv4\pmod6 である。したがって整数せいすうの等式とうしきのように 2 を無条件むじょうけんに約分やくぶんすることはできない。

一般いっぱんに $$ca\equiv cb\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ca\equiv cb\pmod n で $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1 なら、$$\left[c\right]$$[c] は乗法逆元じょうほうぎゃくげんを持もつ。両辺りょうへんに $$[c{]}^{-1}$$[c]^{-1} を掛かければ $$\left[a\right]=\left[b\right]$$[a]=[b]、すなわち $$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv b\pmod n を得える。したがって $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1 は、$$c$$c による約分やくぶんを正当化せいとうかする十分じゅうぶんな条件じょうけんである。

6フェルマーの小定理しょうていりへの接続せつぞく

$$p$$p が素数そすうなら、0 でない剰余類じょうよるいは全すべて逆元ぎゃくげんを持もつ。0 でない剰余類じょうよるい全体ぜんたいを

と書かく。この集合しゅうごうには $$\left[1\right],\dots ,[p-1]$$[1],\ldots,[p-1] の $$p-1$$p-1 個この元げんがある。上うえで示しめしたように、0 でない各元かくげんは逆元ぎゃくげんを持もつ。0 でない $$\left[a\right],\left[b\right]$$[a],[b] の積せきが $$\left[0\right]$$[0] だとすると、両辺りょうへんに $$[a{]}^{-1}$$[a]^{-1} を掛かけて $$\left[b\right]=\left[0\right]$$[b]=[0] となり矛盾むじゅんする。したがって乗法じょうほうで閉とじている。結合法則けつごうほうそくは整数せいすうの乗法じょうほうから従したがい、$$\left[1\right]$$[1] が単位元たんいげんである。よってこれは位数いすう $$p-1$$p-1 の群ぐんである。ここに後あとで学まなぶラグランジュの定理ていりを適用てきようすると、$$p\nmid a$$p\nmid a のとき $$[a{]}^{p-1}=[1]$$[a]^{p-1}=[1]、すなわち

が導みちびかれる。これがフェルマーの小定理しょうていりである。

この節せつは後あとの群ぐんとラグランジュの定理ていりへの見通みとおしである。このページの本流ほんりゅうでは、剰余類じょうよるいの演算えんざんが well-defined であることと、逆元ぎゃくげんの存在条件そんざいじょうけんだけを使つかう。

7証明しょうめい補足ほそく：合同式ごうどうしきが加法かほうと乗法じょうほうで保存ほぞんされる理由りゆう

$n$n を正せいの整数せいすうとする。合同式ごうどうしき

が成立せいりつするなら、

である。

加法かほうについて証明しょうめいする。$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$a\equiv b\pmod n は $n\mid (a-b)$n\mid(a-b)、$c\equiv d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$c\equiv d\pmod n は $n\mid (c-d)$n\mid(c-d) という意味いみである。したがって

も $n$n で割わり切きれる。よって $a+c\equiv b+d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$a+c\equiv b+d\pmod n である。

乗法じょうほうについては

と変形へんけいする。$n\mid (a-b)$n\mid(a-b) かつ $n\mid (c-d)$n\mid(c-d) なので、右辺うへんの二ふたつの項こうはどちらも $n$n で割わり切きれる。したがって $n\mid (ac-bd)$n\mid(ac-bd) であり、$ac\equiv bd\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$ac\equiv bd\pmod n である。

ここでは $n$n で割わるのではなく、$n$n が差さを割わり切きることを使つかっている。したがって文字式もじしきの除算じょざんに伴ともなう 0 除算じょざんの問題もんだいは生しょうじない。ただし、$\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$\pmod n の記法きほうでは $n$n を正せいの整数せいすうとして固定こていしている。

8演習えんしゅうリンク

9まとめ

合同式ごうどうしきは、剰余類じょうよるいの等号とうごうである。mod 演算えんざんが正当化せいとうかされるのは、剰余類じょうよるい上じょうの加法かほうと乗法じょうほうが代表元だいひょうげんによらず定さだまるからである。$$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) は可換群かかんぐんである。乗法逆元じょうほうぎゃくげんは常つねにあるわけではなく、$$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1 が必要十分条件ひつようじゅうぶんじょうけんである。