Section 2.1: Congruence and Congruence Classes

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)}

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

1. if a is an integer and r is the remainder of a when divided by n, then [a]=[r]
2. 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.