# Prove $(a + b) \bmod n = (a \bmod n + b \bmod n) \bmod n$

I find I am in trouble to prove:

$$(a + b) \bmod n = (a \bmod n + b \bmod n) \bmod n ?$$

Can anyone help?

Let $a = hn + (a \bmod n)$, $b = kn + (b \bmod n)$, $h,k\in \mathbb Z$. Then the left hand side

\begin{align*} (a+b)\bmod n =& [a+b-(h+k)n]\bmod n\\ =& [(hn +a\bmod n) + (kn+b\bmod n) - hn - kn]\bmod n\\ =& (a\bmod n + b\bmod n)\bmod n \end{align*}

• But could you explain a little more about the last `equal' or tell me what background knowledge I need to know? Thank you! Commented Nov 27, 2013 at 2:49
• Modified, is it clearer now? Commented Nov 27, 2013 at 2:53
• OK, no need, I got it... Thank you! Commented Nov 27, 2013 at 2:54
• @peterwhy: this solution assumes what you're trying to prove. Commented Jan 18, 2021 at 19:52
• @peterwhy I think he meant when you did $(a+b)modn=(a+b-(h+k)n)modn$ because $(amodn+bmodn)=(a+b-n(h+k))$, so you assumed what you were supposed to prove. Commented Sep 12, 2021 at 5:52

There is a simple proof using the following: $$$$x\bmod{n}=y\bmod{n} \Longleftrightarrow n \mid (x-y).$$$$

Let $$r = a\bmod{n}$$ and $$s=\bmod{n}$$. By the Division Algorithm, there are integers $$p$$ and $$q$$ such that $$a = pn + r$$ and $$b = qn + s$$. Adding these equations and rewriting yields $$n(p+q) = (a + b) -(r + s)$$. The result now follows by the fact above.