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

equivalence relations同値関係どうちかんけい and congruences合同式ごうどうしき: basic exercises

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

1Corresponding lectures

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

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

2Suggested order

After “Equivalence relations and cosets,” complete Problem 1 and Parts 1–4 of the later proof exercise. After “Congruences and modular arithmetic,” continue with Problems 2–3, the first proof exercise, and Parts 5–6 of the later proof exercise. The page prerequisites describe what is needed to complete the whole page.

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

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

3Related exercises

Attempt these after the later lectures on quotient groups and quotient rings.

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

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

4Problem 1: write a residue class剰余類じょうよるい

Write $$[2{]}_5$$[2]_5 as a set.

4.1解答かいとう

である。

4.1Answer

4.2解説かいせつ

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

4.2Explanation

A residue class剰余類じょうよるい is not one integer. It is the set of all integers with the same remainder.

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

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

5Problem 2: decide a congruence合同式ごうどうしき

Does $$37\equiv 12\text{[PARSE ERROR: Undefined("Command("pmod")")]}5$$37\equiv 12\pmod 5 hold?

5.1解答かいとう

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

5.1Answer

Since $$37-12=25$$37-12=25 and $$5\mid 25$$5\mid25, the congruence合同式ごうどうしき holds.

5.2解説かいせつ

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

5.2Explanation

A congruence合同式ごうどうしき can be read as a comparison of remainders, but its definition定義ていぎ is $$n\mid (a-b)$$n\mid(a-b).

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

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

6Problem 3: find an inverse

Find the multiplicative inverse of $$\left[4\right]$$[4] in $$\mathbb{Z}/11\mathbb{Z}$$\mathbb Z/11\mathbb Z.

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.1Answer

Since $$4·3=12\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}11$$4\cdot3=12\equiv1\pmod{11}, the inverse is $$\left[3\right]$$[3].

6.2解説かいせつ

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

6.2Explanation

Before searching for an inverse, we know it exists because $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(4,11)=1$$\gcd(4,11)=1. Here we verified it directly by multiplication.

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

7Proof exercise: congruence合同式ごうどうしき is preserved by addition and multiplication

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.1Problem

Let $$n$$n be a positive integer. Prove that if $$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv b\pmod n and $$c\equiv d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$c\equiv d\pmod n, then $$a+c\equiv b+d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a+c\equiv b+d\pmod n and $$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.2Answer

The statement $$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv b\pmod n means $$n\mid (a-b)$$n\mid(a-b), and $$c\equiv d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$c\equiv d\pmod n means $$n\mid (c-d)$$n\mid(c-d).

Therefore $$n\mid \left(\right(a+c)-(b+d\left)\right)$$n\mid((a+c)-(b+d)), so $$a+c\equiv b+d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a+c\equiv b+d\pmod n.

Also,

The right-hand side is a sum of two terms divisible by $$n$$n. Hence $$ac\equiv bd\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ac\equiv bd\pmod n.

7.3解説かいせつ

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

7.3Explanation

The proof does not divide by $$n$$n. It uses the fact that $$n$$n divides the relevant differences. This preservation is exactly what guarantees that changing representatives does not change the sum or product of residue classes, that is, their 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 であることを示しめせ。

8Proof exercise: from an equivalence relation to well-definedness

Fix $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}2$$n\ge2 and define a relation on the integers by $$a\sim b⟺n\mid (a-b)$$a\sim b\Longleftrightarrow n\mid(a-b).

1. Prove that $$\sim$$\sim is reflexive, symmetric, and transitive.
2. Prove that $$a\sim b$$a\sim b if and only if $$\left[a\right]=\left[b\right]$$[a]=[b].
3. Use two representatives to show that the rule $$F\left(\right[a\left]\right)=a$$F([a])=a does not define a map from $$\mathbb{Z}/n\mathbb{Z}$$\mathbb Z/n\mathbb Z to $$\mathbb{Z}$$\mathbb Z.
4. Prove that $$\left[a\right]=\left[a^{\prime }\right]$$[a]=[a'] and $$\left[b\right]=\left[b^{\prime }\right]$$[b]=[b'] imply both $$[a+b]=[a^{\prime }+b^{\prime }]$$[a+b]=[a'+b'] and $$\left[ab\right]=\left[a^{\prime }{b}^{\prime }\right]$$[ab]=[a'b'].
5. Prove that $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) is a group, explicitly identifying closure, associativity, the identity, and inverses.
6. Verify that $$2·1\equiv 2·4\text{[PARSE ERROR: Undefined("Command("pmod")")]}6$$2\cdot1\equiv2\cdot4\pmod6 but $$1\text{[PARSE ERROR: Undefined("Command("not")")]}\equiv 4\text{[PARSE ERROR: Undefined("Command("pmod")")]}6$$1\not\equiv4\pmod6. Then prove that $$ca\equiv cb\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ca\equiv cb\pmod n and $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1 imply $$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] を得える。

8.1Answer

1. The relation is reflexive because $$a-a=0$$a-a=0 and $$n\mid 0$$n\mid0. It is symmetric because $$n\mid (a-b)$$n\mid(a-b) and $$b-a=-(a-b)$$b-a=-(a-b) imply $$n\mid (b-a)$$n\mid(b-a). It is transitive because divisibility of both $$a-b$$a-b and $$b-c$$b-c, together with $$a-c=(a-b)+(b-c)$$a-c=(a-b)+(b-c), implies $$n\mid (a-c)$$n\mid(a-c).
2. Suppose $$a\sim b$$a\sim b. If $$x\in \left[a\right]$$x\in[a], then $$x\sim a\sim b$$x\sim a\sim b, so $$x\in \left[b\right]$$x\in[b]. Conversely, if $$x\in \left[b\right]$$x\in[b], symmetry gives $$b\sim a$$b\sim a, so $$x\sim b\sim a$$x\sim b\sim a and $$x\in \left[a\right]$$x\in[a]. Thus $$\left[a\right]=\left[b\right]$$[a]=[b]. Conversely, if $$\left[a\right]=\left[b\right]$$[a]=[b], then $$a\in \left[a\right]=\left[b\right]$$a\in[a]=[b], so $$a\sim b$$a\sim b.
3. We have $$\left[0\right]=\left[n\right]$$[0]=[n], but choosing representative 0 gives $$F\left(\right[0\left]\right)=0$$F([0])=0, while choosing representative $$n$$n gives $$F\left(\right[n\left]\right)=n$$F([n])=n. The same residue class would have two different values, so the rule is not well-defined.
4. We have $$n\mid (a-a^{\prime })$$n\mid(a-a') and $$n\mid (b-b^{\prime })$$n\mid(b-b'). Both $$(a+b)-(a^{\prime }+b^{\prime })=(a-a^{\prime })+(b-b^{\prime })$$(a+b)-(a'+b')=(a-a')+(b-b') and $$ab-a^{\prime }{b}^{\prime }=a(b-b^{\prime })+b^{\prime }(a-a^{\prime })$$ab-a'b'=a(b-b')+b'(a-a') are multiples of $$n$$n, proving the two required class equalities.
5. Closure follows from $$\left[a\right]+\left[b\right]=[a+b]\in \mathbb{Z}/n\mathbb{Z}$$[a]+[b]=[a+b]\in\mathbb Z/n\mathbb Z. Associativity follows from $$\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]). The identity is $$\left[0\right]$$[0], and the inverse of $$\left[a\right]$$[a] is $$[-a]$$[-a]. Hence this is a group.
6. Since $$2\equiv 8\text{[PARSE ERROR: Undefined("Command("pmod")")]}6$$2\equiv8\pmod6, the first congruence holds, but 6 does not divide $$1-4=-3$$1-4=-3. If $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1, then $$\left[c\right]$$[c] has an inverse. Multiplying $$\left[c\right]\left[a\right]=\left[c\right]\left[b\right]$$[c][a]=[c][b] by $$[c{]}^{-1}$$[c]^{-1} gives $$\left[a\right]=\left[b\right]$$[a]=[b].