# Remainder of sum equals sum of remainders

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.

• What if a and b are negative?
– boaz
Commented May 25, 2021 at 4:57
• I defined the set as the elements $0,1, \ldots, n-1$, so isn't this impossible? (I don't like the definition, and would prefer to use equivalence classes, but this is the one I have to work with for the moment.) Commented May 25, 2021 at 5:00
• Oh I see the point. The map goes from $\mathbb{Z}$ to $\mathbb{Z}/n$ so I can have negative inputs. Is there a way to fix the homomorphism, or must I just define it with equivalence classes? Commented May 25, 2021 at 5:25
• We always have the natural projection onto $\mathbb Z_n$. Is there any specific reason you need $\varphi$ to be a morphism? Commented May 25, 2021 at 5:25
• I prefer the definition, but my professor defined $\mathbb{Z}/n$ differently and claimed that this map is a homomorphism, so I'm trying to verify it that way. Commented May 25, 2021 at 5:42

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 , 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)$$.

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