6

I find I am in trouble to prove:

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

Can anyone help?

Ernie060
  • 6,073
Wei Zhong
  • 457

2 Answers2

6

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*}$$

peterwhy
  • 22,256
  • But could you explain a little more about the last `equal' or tell me what background knowledge I need to know? Thank you! – Wei Zhong Nov 27 '13 at 02:49
  • Modified, is it clearer now? – peterwhy Nov 27 '13 at 02:53
  • OK, no need, I got it... Thank you! – Wei Zhong Nov 27 '13 at 02:54
  • @peterwhy: this solution assumes what you're trying to prove. – Pietro Paparella Jan 18 '21 at 19:52
  • @PietroPaparella you mean the assumption that $a = hn + (a \bmod n)$ and $b=\ldots$, that the dividend and remainder differ by a multiple of the divisor? – peterwhy Jan 18 '21 at 21:48
  • 1
    @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. – Eccentric Tuber Sep 12 '21 at 05:52
  • @EccentricTuber The property of $\bmod$ arithmetic that can be proven separately is

    $$(a+b) \equiv (a+b-n) \equiv (a+b-2n)\equiv \ldots \pmod n$$

    or when considering $\bmod$ as an operator,

    $$(a+b)\bmod n = (a+b-n)\bmod n = (a+b-2n)\bmod n = \ldots$$

    On the first equal sign, I just chose to subtract $n$ multiple times, specifically $(h+k)$ times.

     – peterwhy Sep 12 '21 at 19:51
  • @peterwhy I guess that makes sense, but in your proof it doesn't reference that so I can understand why I thought you were just assuming the result. Thanks for the clarification though. – Eccentric Tuber Sep 13 '21 at 23:12
1

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

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.

Pietro Paparella
  • 3,500
  • 1
  • 19
  • 29