Please Login to access more options.


Exercise (A Homomorphism From $\mathbb{Z}_n$ to $\mathbb{Z}_d$ when $d$ is a divisor of $n$)

Consider the map $f:\mathbb{Z}_{n}\to \mathbb{Z}_d$ defined by $f(x)=x\pmod d$ where $d$ is a divisor of $n$. Show that $f$ is a homomorphism.

Click to see a solution

We need to show that $((x+y)\pmod n)\pmod d = (x\pmod d+y\pmod d)\pmod d$. We know that $a\pmod d=b\pmod d$ if and only if $a-b$ is a multiple of $d$ (does this look like the coset property that says $Ha=Hb$ if and only if $ab^{-1}\in H$?). We just need to show that $(x+y)\pmod n - (x\pmod d+y\pmod d)$ is a multiple of $d$. To do this, first note that using the division algorithm we can write $x\pmod d = x-q_xd$ and $y\pmod d = y-q_yd$ for some integers $q_x$ and $q_y$, and we can write $(x+y)\pmod n = (x+y)-qn$ for some integer $q$. Since we know $d$ is a divisor of $n$, we can also write $n=md$ for some integer $m$. We then compute $$\begin{align} (x+y)\pmod n - (x\pmod d+y\pmod d) &=(x+y-qn)-(x-q_xd)-(y-q_yd)\\ &=-qmd+q_xd+q_yd\\ &=d(q_x+q_y-qm), \end{align}$$ which is a multiple of $d$ as desired.