1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Arithmetic proofs (multiplication and addition mod n)

  1. Sep 7, 2011 #1
    1. The problem statement, all variables and given/known data
    Let n be a fixed positive integer greater than 1. If a (mod n) = a' and b (mod n) = b', prove that (a+b) (mod n) = (a'+b') (mod n) and that (ab) (mod n) = (a'b') (mod n)


    2. Relevant equations
    When a = qn + r
    a mod n = r

    3. The attempt at a solution
    (a'+b') (mod n) = (a (mod n) + b (mod n)) (mod n)
    = ((a+b) (mod n)) (mod n)
    = (a+b) (mod n)
    (a'b') (mod n) = (a (mod n) * b (mod n)) (mod n)
    = ((ab) mod n) mod n
    = (ab) mod n

    Is this a valid approach? My reasoning is that if we treat mod n as an operation on a number, then we can mod n twice and we should get the same thing since any remainder divided by the same number should yield the same number.

    I know that my work isn't very rigorous and I didn't really apply the definition I have directly, can anyone point me in another direction if this is the wrong approach?

    Thank you for your time,
    Elwin
     
  2. jcsd
  3. Sep 7, 2011 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    You might want to show this in a more rigorous way.
     
  4. Sep 7, 2011 #3
    Sorry if this is a bit silly to ask, but how does one show modular arithmetic operations rigorously in general? My text is a bit casual when discussing the material and the closest thing there is to a definition in this section is that "when a = nq+r where q is the quotient and r is the remainder then a mod n = r." Is this all I need then, or is there some formal definitions for additions/multiplication etc. that I'm missing?

    Thank you for your response,
    Elwin
     
  5. Sep 7, 2011 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    I have to admit that I was thinking of something called 'congruence mod n', which is somewhat different, although closely related. You will probably cover it soon, if you haven't already done so.

    The 'mod' you have here appears to be a mathematical operation. You're right that a (mod n) = r means that a = qn +r for some integers, q and r, furthermore, 0 ≤ r < n. Note: this means that 0 ≤ a (mod n) < n, since (a (mod n)) = r.

    It's not necessarily true that (a (mod n) + b (mod n)) = (a + b) (mod n).

    Yes, 0 ≤ a (mod n) < n and 0 ≤ b (mod n) < n, but all that tells you is that 0 ≤ a (mod n) + b (mod n) < 2n .

    Use qa , qb ra & rb & see what you can come up with.

    You will have to look at two cases:

    (Case 1) 0 ≤ a (mod n) + b (mod n) < n

    (Case 2) n ≤ a (mod n) + b (mod n) < 2n
     
  6. Sep 7, 2011 #5
    It's not necessarily true that (a (mod n) + b (mod n)) = (a + b) (mod n).
    ^
    Okay, I've got that part now.
    0 ≤ a (mod n) + b (mod n) < 2n
    Since we're dealing with integers, is it worth strengthening this statement?
    0 ≤ a (mod n) + b (mod n) ≤ 2n-2 since a (mod n) ≤ n - 1 & b (mod n) ≤ n - 1
    Or is that not true?
     
  7. Sep 9, 2011 #6

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    (Sorry, I've been traveling rhe last two days.)

    Yes, it's true, but not important.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Modular Arithmetic proofs (multiplication and addition mod n)
  1. Modular arithmetic (Replies: 2)

Loading...