2
$\begingroup$

modular arithmetic

How Can I prove (a+b) mod m = (a mod m) + (b mod m)) mod m ?

$\endgroup$

closed as off-topic by user147263, user91500, Surb, N. F. Taussig, graydad Mar 5 '15 at 15:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Community, user91500, Surb, N. F. Taussig, graydad
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Before it can be proven, you have to have a definition for $\rm mod$. What is your definition of it? $\endgroup$ – DanielV Mar 5 '15 at 13:39
  • 1
    $\begingroup$ This question is a bit confusing. You seem to have too many (mod m)s. Are you trying to prove equality in Z of least positive representatives or equality in Z/mZ? $\endgroup$ – SE318 Mar 5 '15 at 13:39
1
$\begingroup$

Let $a\mod m= a_1$ and $b\mod m = b_1$.

Then

$$\begin{cases}m\mid a-a_1\\m\mid b-b_1\end{cases}\implies m\mid a+b-(a_1+b_1)$$

$$\iff a+b\equiv a_1+b_1\pmod{m}\iff (a+b)\mod m=(a_1+b_1)\mod m\\\iff (a+b)\mod m =((a\mod m)+(b\mod m))\mod m\ \ \ \square$$

$\endgroup$
  • $\begingroup$ I am not clear about the notation m|a . please explain. $\endgroup$ – M S Hossain Mar 5 '15 at 13:32
  • $\begingroup$ You need to be careful here. If you say $a mod m= a_1$ then a is an integer and $a_1$ is a set of integers. This causes some problems. $\endgroup$ – SE318 Mar 5 '15 at 13:35
  • $\begingroup$ $m\mid a$ is the notation for "$m$ divides $a$", or "$a$ is divisible by $m$". Formally, $m\mid a\iff \exists k\in\mathbb Z(a=mk)$. $\endgroup$ – user26486 Mar 5 '15 at 13:35
  • $\begingroup$ @SE318 No. See this Wikipedia article. $a\mod m$ is defined to be $r$ such that $a=lm+r$ for some integer $l$, where $r\in\mathbb Z, 0\le r<m$. $\endgroup$ – user26486 Mar 5 '15 at 13:36
  • $\begingroup$ @user314, I see what you're saying. I've never seen it defined in this way in any of my math classes though as this lead to ambiguity as to if you're just finding the remainder, or passing into the quotient space. It's probably just a difference in definitions though, depending on which textbook you use, they can define these things with slight(but important!) differences. $\endgroup$ – SE318 Mar 5 '15 at 13:50
1
$\begingroup$

Using $\,\ c\equiv d\pmod m\color{#c00}\iff \bar c = \bar d,\ $ where $\,\ \bar n := (n\bmod m)\ $

${\rm mod}\ m\!:\,\ a\color{#c00}\equiv \bar a$
$\qquad\qquad\, b\color{#c00}\equiv \bar b$
$\ \, \Rightarrow\,\ a+b\equiv \bar a + \bar b\,\ $ by the $ $ Congruence Sum Rule

$\color{#c00}\Rightarrow\, (a+b)\ {\rm mod}\ m\, \equiv\, (\bar a + \bar b)\ {\rm mod}\ m,\,\ $ which is the titled claim.

Remark $ $ Generally, as above, to prove an identity about mod as an operator it is usually easiest to first convert it into the more flexible congruence form, prove it using congruences, then convert back to operator form.

$\endgroup$
0
$\begingroup$

If $\pmod m$ just means that you subtract or add multiples of $m$ until you end up in the range $0,1,2,...,m-1$ then the RHS is easily compared to the LHS by collecting multiples of $m$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.