Can anyone give me a rundown on Congruence?

[AndersHermansson]

I've googled for an hour now and I've found a few resources but they all assume you know the terminology. Like for example.

a = b(mod n)

Can anyone explain the modulus operator and congruence to me?

 

[KLscilevothma]

0= 0 χ 5 + 0
1= 0 χ 5 + 1
2= 0 χ 5 + 2
3= 0 χ 5 + 3
4= 0 χ 5 + 4
5= 1 χ 5 + 0
6= 1 χ 5 + 1
.
.
.

We observe that the remainder left when any integer is divided by 5 is one of the five integers 0, 1, 2, 3, 4. We say that two integers a and b are "congruent modulo 5" if they leave the same remainder on division by 5. Thus 2, 7, 22, -3, -8, etc are all congurent modulo 5 since they leave the remainder 2. In general, we say that two integers a and b are congrent modulo d, where d is a fixed integer, if a and b leave the same remainder on division by d. For example, 15 and 1 are congruent modulo 7. We can write 15 ≡ 1 (mod 7)

Defination
Let a and b be integers and let n be a positive integer. We say a is congruent to b modulo n , written
a ≡ b (mod n)

In fact "a ≡ b (mod n)" and "a=b+nd (where d is an integer)" are equilvalent.


Here are more examples
2003 ≡ 3 (mod 1000)
1985 ≡ 85 (mod 100)
1985 ≡ 985 (mod 1000)
121 ≡ 0 (mod 11)
953 ≡ 4 (mod 13)

Here are some properties of congruences. For all integers a, b and c, we have
1) a ≡ a (mod n)
2) a ≡ b (mod n) if and only if b≡ a (mod n)
3) if a ≡ b (mod n) and b ≡ c (mod n), then a≡ c (mod n)
4) n | a if and only of a ≡ 0 (mod n)
5) If a ≡ b (mod n) and x is a natural number, then a^x ≡ b^x (mod n)

 

[AndersHermansson]

Thanks a lot, that really helped!