Results 1 to 11 of 11

Math Help - modular arithmetic

  1. #1
    Junior Member
    Joined
    Dec 2009
    From
    Texas
    Posts
    70
    Awards
    1

    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

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by james121515 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2009
    From
    Texas
    Posts
    70
    Awards
    1
    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?
    Last edited by james121515; March 17th 2010 at 12:27 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Dec 2009
    From
    Texas
    Posts
    70
    Awards
    1
    In general, is it true that (a\star b)\text{ mod } n = [a\text{ mod }n]\star [b \text{ mod }n]?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by james121515 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by james121515 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Sep 2009
    Posts
    502
    (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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by novice View Post
    (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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    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?
    Last edited by novice; March 18th 2010 at 10:01 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Drexel28 View Post
    (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?
    Last edited by novice; March 18th 2010 at 10:06 AM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by james121515 View Post
    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).
    Last edited by novice; March 18th 2010 at 09:47 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 4th 2011, 12:07 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 02:37 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 06:08 AM
  4. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 04:17 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 09:39 PM

Search Tags


/mathhelpforum @mathhelpforum