同値関係どうちかんけいequivalence relationと合同式ごうどうしきcongruence 基本きほん演習えんしゅう

1対応たいおうする講義こうぎ

2取とり組くむ順序じゅんじょ

「同値関係どうちかんけいと剰余類じょうよるい」の後あとは問題もんだい1と、後半こうはんの証明演習しょうめいえんしゅうの小問しょうもん1〜4に取とり組くめる。「合同式ごうどうしきと mod 演算えんざん」の後あとに問題もんだい2・3、最初さいしょの証明演習しょうめいえんしゅう、および後半こうはんの小問しょうもん5・6へ進すすむ。このページの prerequisites は全問題ぜんもんだいに取とり組くむための最終到達点さいしゅうとうたつてんを表あらわす。

3関連かんれん演習えんしゅう

これらは後続こうぞくの商群しょうぐん・商環しょうかんの講義こうぎを学まなんだ後あとに取とり組くむ。

4問題もんだい1：剰余類じょうよるいresidue classを書かく

$$[2{]}_5$$[2]_5 を集合しゅうごうsetとして書かけ。

4.1解答かいとう

である。

4.2解説かいせつ

剰余類じょうよるいresidue classは一ひとつの整数せいすうintegerではなく、同おなじ余あまりremainderを持もつ整数全体せいすうぜんたいの集合しゅうごうsetである。

5問題もんだい2：合同式ごうどうしきcongruenceを判定はんていする

$$37\equiv 12\text{[PARSE ERROR: Undefined("Command("pmod")")]}5$$37\equiv 12\pmod 5 は成立せいりつするか。

5.1解答かいとう

$$37-12=25$$37-12=25 であり、$$5\mid 25$$5\mid25 なので成立せいりつする。

5.2解説かいせつ

合同式ごうどうしきcongruenceは余あまりremainderの比較ひかくとしても読よめるが、定義ていぎは $$n\mid (a-b)$$n\mid(a-b) である。

6問題もんだい3：逆元ぎゃくげんを求もとめる

$$\mathbb{Z}/11\mathbb{Z}$$\mathbb Z/11\mathbb Z で $$\left[4\right]$$[4] の乗法逆元じょうほうぎゃくげんを求もとめよ。

6.1解答かいとう

$$4·3=12\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}11$$4\cdot3=12\equiv1\pmod{11} なので、逆元ぎゃくげんは $$\left[3\right]$$[3] である。

6.2解説かいせつ

逆元ぎゃくげんを探さがす前まえに、$$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(4,11)=1$$\gcd(4,11)=1 であるため逆元ぎゃくげんが存在そんざいすることが分わかる。ここでは実際じっさいに掛かけ算ざんで確認かくにんした。

7証明しょうめい演習えんしゅう：合同式ごうどうしきcongruenceが加法かほうと乗法じょうほうで保存ほぞんされること

7.1問題もんだい

$n$n を正せいの整数せいすうintegerとする。$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$a\equiv b\pmod n、$c\equiv d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$c\equiv d\pmod n なら、$a+c\equiv b+d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$a+c\equiv b+d\pmod n、$ac\equiv bd\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$ac\equiv bd\pmod n であることを証明しょうめいせよ。

7.2解答かいとう

$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\mid \left(\right(a+c)-(b+d\left)\right)$n\mid((a+c)-(b+d)) である。よって $a+c\equiv b+d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$a+c\equiv b+d\pmod n である。

また、

であり、右辺うへんは $n$n で割わり切きれる二ふたつの項こうの和わである。したがって $ac\equiv bd\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$ac\equiv bd\pmod n である。

7.3解説かいせつ

ここでは $n$n による除算じょざんではなく、$n$n が差さを割わり切きることを使つかっている。この保存性ほぞんせいが、代表元だいひょうげんを変かえても剰余類じょうよるいの和わと積せきが変かわらないこと、すなわち well-definedness を保証ほしょうする。

8証明しょうめい演習えんしゅう：同値関係どうちかんけいから well-definedness まで

$$n\text{[PARSE ERROR: Undefined("Command("ge")")]}2$$n\ge2 を固定こていし、整数せいすう $$a,b$$a,b に対たいして $$a\sim b⟺n\mid (a-b)$$a\sim b\Longleftrightarrow n\mid(a-b) と定さだめる。

1. $$\sim$$\sim が反射性はんしゃせい・対称性たいしょうせい・推移性すいいせいを満みたすことを示しめせ。
2. $$a\sim b$$a\sim b と $$\left[a\right]=\left[b\right]$$[a]=[b] が同値どうちであることを示しめせ。
3. $$F\left(\right[a\left]\right)=a$$F([a])=a という規則きそくが $$\mathbb{Z}/n\mathbb{Z}$$\mathbb Z/n\mathbb Z から $$\mathbb{Z}$$\mathbb Z への写像しゃぞうを定さだめないことを、二ふたつの代表元だいひょうげんを使つかって示しめせ。
4. $$\left[a\right]=\left[a^{\prime }\right]$$[a]=[a']、$$\left[b\right]=\left[b^{\prime }\right]$$[b]=[b'] なら $$[a+b]=[a^{\prime }+b^{\prime }]$$[a+b]=[a'+b'] かつ $$\left[ab\right]=\left[a^{\prime }{b}^{\prime }\right]$$[ab]=[a'b'] であることを示しめせ。
5. $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) が群ぐんであることを、閉包性へいほうせい、結合法則けつごうほうそく、単位元たんいげん、逆元ぎゃくげんを明示めいじして示しめせ。
6. $$2·1\equiv 2·4\text{[PARSE ERROR: Undefined("Command("pmod")")]}6$$2\cdot1\equiv2\cdot4\pmod6 だが $$1\text{[PARSE ERROR: Undefined("Command("not")")]}\equiv 4\text{[PARSE ERROR: Undefined("Command("pmod")")]}6$$1\not\equiv4\pmod6 であることを確認かくにんせよ。また、$$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 なら $$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv b\pmod n であることを示しめせ。

8.1解答かいとう

1. $$a-a=0$$a-a=0 かつ $$n\mid 0$$n\mid0 なので反射的はんしゃてきである。$$n\mid (a-b)$$n\mid(a-b) なら $$b-a=-(a-b)$$b-a=-(a-b) より $$n\mid (b-a)$$n\mid(b-a) なので対称的たいしょうてきである。$$n\mid (a-b)$$n\mid(a-b) かつ $$n\mid (b-c)$$n\mid(b-c) なら $$a-c=(a-b)+(b-c)$$a-c=(a-b)+(b-c) より $$n\mid (a-c)$$n\mid(a-c) なので推移的すいいてきである。
2. $$a\sim b$$a\sim b とする。$$x\in \left[a\right]$$x\in[a] なら $$x\sim a\sim b$$x\sim a\sim b なので $$x\in \left[b\right]$$x\in[b] である。逆ぎゃくに $$x\in \left[b\right]$$x\in[b] なら、対称性たいしょうせいより $$b\sim a$$b\sim a であり、$$x\sim b\sim a$$x\sim b\sim a から $$x\in \left[a\right]$$x\in[a] である。よって $$\left[a\right]=\left[b\right]$$[a]=[b] である。逆ぎゃくに $$\left[a\right]=\left[b\right]$$[a]=[b] なら、$$a\in \left[a\right]=\left[b\right]$$a\in[a]=[b] だから $$a\sim b$$a\sim b である。
3. $$\left[0\right]=\left[n\right]$$[0]=[n] だが、代表元だいひょうげんを 0 と選えらべば $$F\left(\right[0\left]\right)=0$$F([0])=0、$$n$$n と選えらべば $$F\left(\right[n\left]\right)=n$$F([n])=n となる。同おなじ剰余類じょうよるいから異ことなる値あたいが出でるので、この規則きそくは well-defined でない。
4. $$n\mid (a-a^{\prime })$$n\mid(a-a')、$$n\mid (b-b^{\prime })$$n\mid(b-b') である。$$(a+b)-(a^{\prime }+b^{\prime })=(a-a^{\prime })+(b-b^{\prime })$$(a+b)-(a'+b')=(a-a')+(b-b') と $$ab-a^{\prime }{b}^{\prime }=a(b-b^{\prime })+b^{\prime }(a-a^{\prime })$$ab-a'b'=a(b-b')+b'(a-a') はともに $$n$$n の倍数ばいすうなので、求もとめる二ふたつの類るいの等式とうしきを得える。
5. 閉包性へいほうせいは $$\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(\right[a]+[b\left]\right)+\left[c\right]=\left[\right(a+b)+c]=[a+(b+c\left)\right]=\left[a\right]+\left(\right[b]+[c\left]\right)$$([a]+[b])+[c]=[(a+b)+c]=[a+(b+c)]=[a]+([b]+[c]) である。$$\left[0\right]$$[0] が単位元たんいげんで、$$\left[a\right]$$[a] の逆元ぎゃくげんは $$[-a]$$[-a] である。したがって群ぐんである。
6. $$2\equiv 8\text{[PARSE ERROR: Undefined("Command("pmod")")]}6$$2\equiv8\pmod6 なので最初さいしょの合同式ごうどうしきは成立せいりつするが、6 は $$1-4=-3$$1-4=-3 を割わらない。$$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1 なら $$\left[c\right]$$[c] は逆元ぎゃくげんを持もつので、$$\left[c\right]\left[a\right]=\left[c\right]\left[b\right]$$[c][a]=[c][b] の両辺りょうへんに $$[c{]}^{-1}$$[c]^{-1} を掛かけて $$\left[a\right]=\left[b\right]$$[a]=[b] を得える。