## 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:

Leta, b, nbe integers where . Then it is said thata is congruent tobmodulonon 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

nis 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 integersa, b,andc.

###### 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$$ (modn)

## 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
ais an integer andris the remainder ofawhen divided byn, then[a]=[r]- There are exactly
ndistinct 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

Ifmandnare positive integers with(m,n)=1(mandnare relatively prime) thenx≡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) thennv=1-mu.

Likewise mu≡ 1 (mod n),nv≡0 (mod n).So

x=bmu+anvCheck:

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.