Remainder of sum equals sum of remainders

Question

This fact is obvious if I'm allowed to use modular arithmetic, but not without it.

Suppose I define $\mathbb{Z}/n$ as the set $\{0,1, \ldots, n-1\}$ with addition given by $(a,b) \to a + b$ if $a + b < n$ and $a + b - n$ otherwise. I then define a map $\varphi: \mathbb{Z} \to \mathbb{Z}/n$ sending $a$ to $a \text{ mod $n$}$, that is, I send an integer to its remainder after division by $n$. I claim this is a homomorphism of groups, but I can't prove it.

So given $a,b \in \mathbb{Z}$, $\varphi(a + b) = a + b \text{ (mod $n$)}$. If $a + b < n$ in $\mathbb{Z}$, then its remainder is $a + b$, and we're done. If not, then $a + b \text{ (mod $n$)}$ is $a + b - n$. I don't know how to proceed from here.

If I try to use the divison algorithm outright, I get $a = nq_1 + r_1$ and $b = nq_2 + r_2$ where $q_1, q_2, r_1, r_2 \in \mathbb{Z}$ are unique and $0 \leq r_1, r_2 \leq n-1$. Then $$a + b = n(q_1 + q_2) + (r_1 + r_2).$$ But then there's a question of whether $r_1 + r_2$ is divisible by $n$, so I'm stuck again.

Answer 1

Let us denote the addition in $\mathbb{Z}_n$ by $*$. If $\varphi(a)= r_1$ and $\varphi(b) = r_2$, then as you have noticed $$a=nq_1+r_1$$ and $$b=nq_2+r_2,$$ where $0\leq r_1, r_2 \leq n-1$. From the above two, $$a+b = n(q_1+q_2) +r_1+r_2.$$ If $r_1+r_2 <n$, then $\varphi(a+b) = r_1+r_2 = r_1*r_2= \varphi(a)*\varphi(b)$.

If $r_1+r_2\geq n$, then $(r_1+r_2) -n < n$, by the conditions of $r_1$ and $r_2$. Hence, $$a+b= n(q_1+q_2+1) +(r_2+r_2-n).$$ This implies that $$ \varphi(a+b) = r_1+r_2-n = r_1*r_2= \varphi(a) * \varphi(b)$$.

Answer 2

You want to prove the following theorem:

Let $n$ be a positive integer. Then for all $m \in \mathbb{Z}$, there exists a unique $j$ such that $0 \leq j < n$ and $m \equiv j \mod n$.

We can then define $\phi(m)$ to be the $j$ mentioned above.

Note that $\phi(m) \equiv m \mod n$. In fact, $\phi(m)$ is the unique element of $\mathbb{Z}_n$ such that $\phi(m) \equiv m \mod n$. To speak even more strongly, note that $\phi : \mathbb{Z} \to \mathbb{Z}_n$ is a surjection (since for all $m \in \mathbb{Z}_n$, we have $\phi(m) = m$), and that $\phi(a) = \phi(b)$ iff $a \equiv b \mod n$.

Armed with this knowledge, we define the $+$ operator on $\mathbb{Z}_n$ by $a + b = \phi(a + b)$, where the latter $+$ is the $\mathbb{Z}$ $+$ operator.

We wish to show that $\phi(a + b) = \phi(a) + \phi(b)$, the latter $+$ being taken in $\mathbb{Z}_n$. In other words, we wish to show that $\phi(a + b) = \phi(\phi(a) + \phi(b))$. To do so, it suffices to show that $a + b \equiv \phi(a) + \phi(b) \mod n$.

Of course, this is trivial. For we can take $k_a$ such that $a = k_a n + \phi(a)$, $k_b$ such that $b = k_b n + \phi(b)$. Then $a + b = (k_a + k_b) n + \phi(a) + \phi(b)$. Then $a + b \equiv \phi(a) + \phi(b) \mod n$.