Congruence
The concept of congruence initially may seem a bit confusing. I hope to explain the definition in a way that may be easier to understand.
Definition of Congruence:
Let a, b, n be integers where
. Then it is said that a is congruent to b modulo n on the condition that
integrally.
If one were to write a is congruent to b modulo n it would be in the form a≡b (mod n).
Now what does this mean. First I shall provide a few examples:
9≡-3 (mod 4) because 4 divides 9-(-3)=12
9≡3 (mod 2) because 3 divides 9-3=6
7≡41 (mod 17) because 2 divides 7-41=34
In general: a≡b (mod n) means n divides (a-b).
Congruence exhibits some interesting characteristics:
Theorem 2.1
Given that n is a positive integer, then
1) a≡a (mod n)
2) if a≡b (mod n) then b≡a (mod n)
3) if a≡b (mod n) and b≡c (mod n) then a≡c (mod n)
For all integers a, b, and c.
Theorem 2.2
If a≡b (mod n), c≡d (mod n) then
a + c = b + d (mod n) and
$$a\cdot c=b\cdot d$$ (mod n)
Congruence Class
Definition of Congruence Class
Let a and n be integers with n > 0. The congruence class of a modulo n, written as [a]_n, represents the set of all integers that are congruent to a modulo n.
In other words:
[a]={b|b ∈ Z and b≡a (mod n)}
Now b≡a (mod n) can be written as b-a=m*n where m is an integer. So b=m*n+a; So [a] represents the set of values {a + m*n| for all m in the integers}.
Here is an example:
Say n=6. Then [1] is the set {1, 1 ± 6,1 ± 12, 1 ± 18,…,1 ± k*6} (where k is an integer)
Question: Which integers are congruent to 4 (mod 6)?
Answer: {…,-8,-2,4,10,16,22,…} or in other words [4] or [-8]
There are a few points that assist us in our analysis of Congruence classes:
Corollary 2.4 and 2.5
Two congruence classes modulo n are either disjoint or identical.
Congruence mod n has the following properties
- if a is an integer and r is the remainder of a when divided by n, then [a]=[r]
- There are exactly n distinct congruence classes
[0],[1],][2],[3],…,[n-1] Note that [0] and [n] are in fact the same set.
With congruence classes we can ask ourselves a wide variety of questions.
Based on what has been done so far answer this:
For what values of x is this statement true?
x≡2 (mod 4) and x≡5 (mod 7)
Answering this would be rather difficult, but the Chinese solved this problem a long long time ago.
The Chinese Remainder Theorem
If m and n are positive integers with (m,n)=1 (m and n are relatively prime) then x≡a (mod n), x≡b (mod m) has a solution.
Note that a solution is guaranteed if and only if the integers are relatively prime. Glancing above note that 4 and 7 are relatively prime and so there is a solution.
Proof Sketch of the Chinese Remainder Theorem
If mu≡ 0 (mod m), nv≡1 (mod m) then nv=1-mu.
Likewise mu≡ 1 (mod n), nv≡0 (mod n).
So x=bmu+anv
Check:
mod n
x = 0 + a (mod m)
mod m
x = b + 0 (mod n)
So the first value of x for which the above statement is true is when x = 26.