Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruent Modulo

  1. Jun 19, 2007 #1
    Hey, I'm reading through some notes, and I don't really understand congruent modulos

    I was hoping someone could explain better than the sites I found on google.
    Am I solving for something? I see a bunch of examples, but I don't understand what the problem is, or what I'm solving for... a = b (mod p)

    -1 = 1 (mod 2)
    -12 = 3 (mod 5)

    I don't understand how the negative numbers work.

    22 = 1 (mod 3)
    12 = 2 (mod 5)

    What I'm getting right now is 22/3 is remainder 1. and 12/5 is remainder 2..

    but for -12/5.. wouldn't the remainder be -2?
    and -1/2.. wouldn't the remainder be -1?

    Sorry if this seems like a dumb question, thanks in advance.
  2. jcsd
  3. Jun 20, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Negative numbers work in precisely the same way as positive numbers.

    x is congruent to y mod n if n divides x-y, so 1-(-1)=2, and 2 is divisible by 2, hence 1=-1 mod 2.

    Remainders are defined to be in the range 0 to n-1. To work out the remainder you must subtract or _add_ n until you get a number in the right range. Thus, taking the -12 one, add 5 to get -7, add 5 to get -2, add 5 to get 3, now stop as we're in the range 0,1,2,3,4.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook