# modular arithmetic

• Mar 16th 2010, 10:53 PM
james121515
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
• Mar 16th 2010, 11:01 PM
Drexel28
Quote:

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$
• Mar 16th 2010, 11:17 PM
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?
• Mar 16th 2010, 11:36 PM
james121515
In general, is it true that $\displaystyle (a\star b)\text{ mod } n = [a\text{ mod }n]\star [b \text{ mod }n]$?
• Mar 16th 2010, 11:45 PM
Drexel28
Quote:

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 (Wink)
• Mar 16th 2010, 11:46 PM
Drexel28
Quote:

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

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?
• Mar 18th 2010, 08:22 AM
novice
Quote:

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$
Quote:

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

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)$.