1. ## modular arithmetic

How would you go about proving that

$\displaystyle (a+b)\,\mbox{mod}\,n = a\,\mbox{mod}\,n + b\,\mbox{mod}\,n?$

We know by the D.A. that $\displaystyle a = nq + a',\, 0 \leq a' < n$

and $\displaystyle b = nq' + b',\,0 \leq b' < n$

These equations imply that

$\displaystyle a' = a\,\mbox{mod}\, n$

and $\displaystyle b' = b\,\mbox{mod}\,n$

$\displaystyle (a + b) = n(q + q') + (a' + b ')$

If I could show that $\displaystyle (a' + b') < n$, I would be done, right? Since that would imply that $\displaystyle a'+b'$ is the remainder upond dividing $\displaystyle a+ b$ by $\displaystyle n$. How how do we know that for sure?

Thanks for any help,

james

2. Originally Posted by james121515
How would you go about proving that

$\displaystyle (a+b)\,\mbox{mod}\,n = a\,\mbox{mod}\,n + b\,\mbox{mod}\,n?$

We know by the D.A. that $\displaystyle a = nq + a',\, 0 \leq a' < n$

and $\displaystyle b = nq' + b',\,0 \leq b' < n$

These equations imply that

$\displaystyle a' = a\,\mbox{mod}\, n$

and $\displaystyle b' = b\,\mbox{mod}\,n$

$\displaystyle (a + b) = n(q + q') + (a' + b ')$

If I could show that $\displaystyle (a' + b') < n$, I would be done, right? Since that would imply that $\displaystyle a'+b'$ is the remainder upond dividing $\displaystyle a+ b$ by $\displaystyle n$. How how do we know that for sure?

Thanks for any help,

james
I disagree. $\displaystyle (2+2)\text{ mod }4=0,2\text{ mod }4+2\text{ mod }4=4$

I guess that $\displaystyle 19\text{ mod } 2 \not= 11 \text{ mod }3 + 8 \text{ mod }3$ would be another valid counterexample as well?

4. In general, is it true that $\displaystyle (a\star b)\text{ mod } n = [a\text{ mod }n]\star [b \text{ mod }n]$?

5. Originally Posted by james121515
In general, is it true that $\displaystyle (a\star b)\text{ mod } n = [a\text{ mod }n]\star [b \text{ mod }n]$?
What the heck is $\displaystyle \star$? If you mean multiplication, try looking at the same example

6. Originally Posted by james121515

I guess that $\displaystyle 19\text{ mod } 2 \not= 11 \text{ mod }3 + 8 \text{ mod }3$ would be another valid counterexample as well?
Yeah. Take any two odd numbers then their sum together will be zero mod two and their sum separate will be one.

7. (a+b)mod n = a mod n + b mod n

kn + (a+b) = (qn+a) + (pn+b)

kn + (a+b) = (pq)n+(a+b)

Where k=pq, is should be okay, yah?

8. Originally Posted by novice
(a+b)mod n = a mod n + b mod n

kn + (a+b) = (qn+a) + (pn+b)

kn + (a+b) = (pq)n+(a+b)

Where k=pq, is should be okay, yah?
You've showed that $\displaystyle (a+b)\text{ mod }n=\left(a\text{ mod }n+b\text{ mod }n\right)\text{ mod }n$.

9. Originally Posted by Drexel28
You've showed that $\displaystyle (a+b)\text{ mod }n=\left(a\text{ mod }n+b\text{ mod }n\right)\text{ mod }n$.
Oh, I made algebraic mistake. It should be

kn+(a+b)=pn+qn+a+b
nk+(a+b)=n(p+q)+(a+b)

Now suppose that it was stated that k = p+q. I think it should be Okay since the first term on bothside give the same remainder, and it becomes

When k=p+q, (a+b)mod n = (a+b) mod n since bothside have multiple of n. Of course when $\displaystyle n \not= p+q$, the LHS $\displaystyle \not=$RHS.

Yah?

10. Originally Posted by Drexel28
$\displaystyle (2+2)\text{ mod }4=0$
$\displaystyle (2+2)\text{ mod }4 \not = 0$

$\displaystyle (2+2)\text{ mod }4 = 0\text{ mod }4 \not = 0$
$\displaystyle 2\text{ mod }4+2 \text{ mod }4=4$
This part here seems to look like

$\displaystyle (1+1) \cdot 2 \text{ mod }4=4 \text{ mod }4= 0\text{ mod }4 \not = 4$

The remainder of 4 is a multiple of 4, which also is a zero remainder.

It should be okay. Yah?

11. Originally Posted by james121515
I guess that $\displaystyle 19\text{ mod } 2 \not= 11 \text{ mod }3 + 8 \text{ mod }3$ would be another valid counterexample as well?
Of course! $\displaystyle \text{ mod } 2 \not= \text{ mod }3$
Your question says $\displaystyle (a+b) \text{ mod }n = a \text{ mod }n + b \text{ mod }n$, but you did
$\displaystyle (a+b) \text{ mod }n \not= a \text{ mod }(n+1) + b \text{ mod }(n+1)$.