Can anyone give me a rundown on Congruence?

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?
 
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 ax ≡ bx (mod n)
 
Thanks alot, that really helped!
 

Related Threads for: Can anyone give me a rundown on Congruence?

Replies
8
Views
2K
Replies
7
Views
737
Replies
4
Views
5K
Replies
3
Views
1K
  • Posted
Replies
3
Views
2K
  • Posted
Replies
6
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top