Understanding Congruent Modulos: A Guide

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

 

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

 

[tacman]

Congruent modulos can definitely be confusing at first, so don't worry, you're not alone! Essentially, congruent modulos (or congruence) is a way of comparing two numbers and seeing if they have the same remainder when divided by a certain number (also known as the modulus). In your examples, the modulus is p (2, 5, or 3) and the numbers being compared are a and b.

So when we say a = b (mod p), we mean that a and b have the same remainder when divided by p. For example, in the first equation you listed -1 = 1 (mod 2), this means that both -1 and 1 have a remainder of 1 when divided by 2. Similarly, in the second equation -12 = 3 (mod 5), this means that both -12 and 3 have a remainder of 3 when divided by 5.

Now, when it comes to negative numbers, it's important to remember that the remainder will always be a positive number. So in your example of -12/5, the remainder would not be -2, but rather 3 (since -12 divided by 5 gives a remainder of 3). The same goes for -1/2, the remainder would be 1, not -1.

In terms of solving for something, congruent modulos are often used in number theory and cryptography to solve equations involving remainders. For example, if we have an equation like 3x = 1 (mod 7), we can use congruence to find the value of x that satisfies this equation. In this case, x = 5, since 3*5 = 15, and 15 divided by 7 gives a remainder of 1.

I hope this helps clarify things a bit! Remember, congruent modulos can take some time to fully understand, so don't be too hard on yourself. Keep practicing and it will become easier over time. Good luck!