Proof of $[(a \; \text{mod} \; n)+(b \; \text{mod} \; n)] \equiv (a+b)\; \text{mod}\; n$

Question

I'm currently self-studying a course in cryptography, and i understand the importance of understanding modular arithmetic fully. I have proved many operations on modular arithmetic, but one i am stuck on is why:

$[(a \; \text{mod} \; n)+(b \; \text{mod} \; n)]=(a+b)\; \text{mod}\; n$, and the full proof of this.

I have had a few ideas on it, but not proved it fully.It may be obvious, but i am only $15$.

Thanks for any help.

Answer 1

Hint:

It doesn't have to be proved: it's a definition, which is without ambiguity once you've proved this:

If $a\equiv a'\mod n$, and $b\equiv b'\mod n$, then $a+b\equiv a'+b'\mod n$

which results from observing that $a+b\bmod n=(a\bmod n+b\bmod n)\bmod n$.

Answer 2

Let $$a=q_an+r_a$$ $$b=q_bn+r_b$$ for quotients $q_a,q_b$ and remainders $0\le r_a,r_b<n$ of $a,b$ modulo $n$. Then $$\begin{align} a+b&=(q_a+q_b)n+(r_a+r_b)\\ &=\left(q_a+q_b+\delta\right)n +\left(r_a+r_b-\delta n\right) \end{align}$$ for $$\delta=\left\lfloor\frac{r_a+r_b}{n}\right\rfloor$$ where $\lfloor x\rfloor$ is the greatest integer (less than or equal to $x$) or floor function and $$\left(r_a+r_b-\delta n\right)=(a+b)\text{ mod }n.$$ Now equality only holds if $\delta=0$: it is not true in general that $r_a+r_b=r_a+r_b-\delta n$. For example, try $a=b=1,n=2$. What does hold is congruence modulo $n$: $$(a \; \text{mod} \; n)+(b \; \text{mod} \; n) \equiv (a+b)\; \pmod n$$ which we have just proved. In mathematics, we say $$a\equiv b\pmod n \qquad\iff\qquad n | b-a$$ i.e. if their difference is divisible by $n$, but in some computer science contexts, $$r_a=a\text{ mod }n$$ means that $r_a$ is the remainder on dividing $a$ by $n$ using the division algorithm, with either $0\le r_a<n$ or sometimes $-\lfloor\frac n2\rfloor\le r_a<\lfloor\frac n2\rfloor$ or even $-n<r_a<n$, which can be a source of confusion.