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

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

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

1Corresponding lectures

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

2Related exercises

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

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

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

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

3.1解答かいとう

である。

3.1Answer

3.2解説かいせつ

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

3.2Explanation

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

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

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

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

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

4.1解答かいとう

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

4.1Answer

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

4.2解説かいせつ

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

4.2Explanation

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

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

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

5Problem 3: find an inverse

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

5.1解答かいとう

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

5.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].

5.2解説かいせつ

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

5.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.

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

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

6.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 であることを証明しょうめいせよ。

6.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.

6.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 である。

6.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.

6.3解説かいせつ

ここでは $n$n による除算じょざんではなく、$n$n が差さを割わり切きることを使つかっている。

6.3Explanation

The proof証明しょうめい does not divide by $$n$$n. It uses the fact that $$n$$n divides the relevant differences.