Worksheet 3

Please work on the following problems. If you do not get to these problems in class, you *must* do them before the quiz next week.

1. Define a relation on the integers by $a\equiv b (mod n)$ if $b-a=nk$ for some $k\in \mathbb{Z}$. Prove that this is an equivalence relation.
   1. Reflexive: $a\equiv a (mod\ n)$ since $a-a=n(0)$ and $0\in \mathbb{Z}$.
   2. Symmetric: If $a\equiv b (mod n)$ then $b-a=nk$ for some integer $k$. Then $a-b=n(-k)$. Hence $b\equiv a (mod\ n)$.
   3. Transitive: If $a\equiv b (mod n)$ and $b\equiv c (mod\ n)$ then $b-a=nk$ and $c-b=nt$ for some integers $k$ and $t$. Then $c-a=c-b+b-a=nt+nk=n(t+k)$, so $a\equiv c (mod\ n)$.
   Let ${\mathbb{Z}}/n$ be the set of equivalence classes under this relation. We proved in class that ${\mathbb{Z}}/n=\{ [0]_n,\ldots , [n-1]_n\}$.
2. Define a binary operation on ${\mathbb{Z}}/n$ by $[a]_n+[b]_n=[a+b]_n$.
   1. Is this binary operation well defined? That is, if $[a]_n\equiv [a_1]_n$ and $[b]_n\equiv [b_1]_n$, is $[a+b]_n\equiv [a_1+b_1]_n$? (Make sure you understand why proving this proves that $+$ is well defined.) If $[a]_n=[a_1]_n$ and $[b]_n=[b_1]_n$ then $a\equiv a_1 (mod\ n)$ and $b\equiv b_1 (mod\ n)$. That is, there are integers $k$ and $t$ with $a_1-a=nk$ and $b_1-b=nt$. So, $(a+b)-(a_1+b_1)=(a-a_1)+(b-b_1)=nk+nt= n(k+t)$. Thus, $a+b\equiv a_1+b_1 (mod\ n)$ and $[a+b]_n = [a_1+b_1]_n$.
   2. Prove that $([a]_n+[b]_n)+[c]_n=[a]_n+([b]_n+[c]_n)$.
      
      $$([a]_n+[b]_n)+[c]_n=[(a+b)+c]_n= [a+(b+c)]_n=[a]_n+([b]_n+[c]_n)$$
      
      

   3. Prove that $([a]_n+[0]_n)=[a]_n=([0]_n+[a]_n)$.
      
      $$([a]_n+[0]_n)=[a+0]_n=[a]_n=[0+a]_n=([0]_n+[a]_n)$$
      
      

   4. Prove that $[a]_n+[-a]_n=[0]_n=[-a]_n+[a]_n$.
      
      $$[a]_n+[-a]_n=[a-a]_n=[0]_n=[-a+a]_n=[-a]_n+[a]_n$$
      
      

   5. What can you conclude about the set ${\mathbb{Z}}/n$ under the binary operation $+$? You can conclude that $({\mathbb{Z}}/n, +)$ is a monoid, and also a group.