# modular arithmetic

• Mar 16th 2010, 11:53 PM
james121515
modular arithmetic
How would you go about proving that

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

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

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

These equations imply that

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

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

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

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

Thanks for any help,

james
• Mar 17th 2010, 12:01 AM
Drexel28
Quote:

Originally Posted by james121515
How would you go about proving that

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

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

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

These equations imply that

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

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

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

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

Thanks for any help,

james

I disagree. $(2+2)\text{ mod }4=0,2\text{ mod }4+2\text{ mod }4=4$
• Mar 17th 2010, 12:17 AM
james121515

I guess that $19\text{ mod } 2 \not= 11 \text{ mod }3 + 8 \text{ mod }3$ would be another valid counterexample as well?
• Mar 17th 2010, 12:36 AM
james121515
In general, is it true that $(a\star b)\text{ mod } n = [a\text{ mod }n]\star [b \text{ mod }n]$?
• Mar 17th 2010, 12:45 AM
Drexel28
Quote:

Originally Posted by james121515
In general, is it true that $(a\star b)\text{ mod } n = [a\text{ mod }n]\star [b \text{ mod }n]$?

What the heck is $\star$? If you mean multiplication, try looking at the same example (Wink)
• Mar 17th 2010, 12:46 AM
Drexel28
Quote:

Originally Posted by james121515

I guess that $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.
• Mar 17th 2010, 09:59 AM
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?
• Mar 17th 2010, 03:39 PM
Drexel28
Quote:

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 $(a+b)\text{ mod }n=\left(a\text{ mod }n+b\text{ mod }n\right)\text{ mod }n$.
• Mar 18th 2010, 08:32 AM
novice
Quote:

Originally Posted by Drexel28
You've showed that $(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 $n \not= p+q$, the LHS $\not=$RHS.

Yah?
• Mar 18th 2010, 09:22 AM
novice
Quote:

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

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

$(2+2)\text{ mod }4 = 0\text{ mod }4 \not = 0$
Quote:

$2\text{ mod }4+2 \text{ mod }4=4$
This part here seems to look like

$(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?
• Mar 18th 2010, 09:33 AM
novice
Quote:

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