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

1Corresponding lectures

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.

3Related exercises

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

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

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

4.1Answer

4.2Explanation

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

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

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

5.1Answer

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

5.2Explanation

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

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

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

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

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