# Congruent Modulo

1. Jun 19, 2007

### stanners

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. Jun 20, 2007

### matt grime

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.