modular arithmetic

**james121515** · March 16th 2010, 10:53 PM

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$

Adding the first two gives:

$(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

**Drexel28** · March 16th 2010, 11:01 PM

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$

Adding the first two gives:

$(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$

**james121515** · March 16th 2010, 11:17 PM

thanks for your help,

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

**james121515** · March 16th 2010, 11:36 PM

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

**Drexel28** · March 16th 2010, 11:45 PM

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

**Drexel28** · March 16th 2010, 11:46 PM

Originally Posted by james121515

thanks for your help,

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.

**novice** · March 17th 2010, 08:59 AM

(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?

**Drexel28** · March 17th 2010, 02:39 PM

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

**novice** · March 18th 2010, 07:32 AM

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?

**novice** · March 18th 2010, 08:22 AM

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$

$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?

**novice** · March 18th 2010, 08:33 AM

Originally Posted by james121515

thanks for your help,

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

[tex]

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

Thread: modular arithmetic

LinkBack

Thread Tools

Display

modular arithmetic

Similar Math Help Forum Discussions

Modular arithmetic

Modular arithmetic

Modular Arithmetic

Modular arithmetic

modular arithmetic

Search Tags