In considering modular arithmetic (see

here for review if needed), we can divide all integers into congruence classes modulo

n.

Definition 1: Congruence class modulo n: [i]Let

[i] represent the set of all integers such that

[i] = { ..., i-2n, i-n, i, i+n, i+2n, ... }To make this definition even clearer, let's consider the following lemma.

Lemma 1: x ∈ [i] if and only if x ≡ i (mod n)Proof:

(1) Assume

x ≡ i (mod n)(2) Then

n divides

x - i(3) So, there exists an integer

a such that

an = x - i(4) So that

x = an + i(5) Assume that

x ∈ [i](6) Then, there exists

a such that

x = i + an(7) This shows that

an = x - i and further that

n divides

x - i.

(8) Therefore, we have

x ≡ i (mod n)QED

Lemma 2: There are only n distinct congruence classes modulo nProof:

(1) To prove this, I will show that for all

x ∈ Z, there exists

i such that:

x ≡ i (mod n)and

0 ≤ i ≤ n-1(2) For

x ∈ Z, there exists

k such that

x ≡ k (mod n)(3) We can assume that

k is positive since if

k is negative,

k ≡ -k (mod n) since

n divides

k + -k.

(4) We can further assume that

k ≤ n-1, since if

k ≥ n, it follows that

k ≡ (k-n) (mod n) since

n divides

(k - [k-n]) = k -k + n = n.

QED

We can now consider the set of congruence classes modulo

n as the set

Z/nZ.

Definition 2: set of congruence classes modulo n: Z/nZZ/nZ = { [0], ..., [n-1]}Example 1:

Z/3ZZ/3Z = { [0], [1], [2] }For purposes of showing the relationship between

Z and

Z/nZ, I will from this point on view

Z/nZ = {0, ..., n-1}.

So that

Z/3Z will also be represented as

{0, 1, 2}Lemma 3: Z/nZ is a commutative ringProof:

(1)

Z/nZ has

commutative rule for additionFor all

a,b ∈ Z/nZ: a+b ≡ b + a (mod n)(2)

Z/nZ has

associative rule for additionFor all

a,b,c ∈ Z/nZ: (a + b) + c ≡ a + (b + c) (mod n)(3)

Z/nZ has

additive identity rule0 ∈ Z/nZ and for all

a ∈ Z/nZ: a ≡ a + 0 (mod n)(4)

Z/nZ has

additive inverse rule:

(a) Let

a be any congruence class modulo

n such that

a ∈ Z/nZ(b) Assume

a ≠ 0 for if

a = 0, then

a + a ≡ 0 (mod n) and

a is its own additive inverse.

(c) Let

b = n - a(d)

b ∈ Z/nZ since

1 ≤ b ≤ n-1(e)

a + b ≡ n ≡ 0 (mod n)(5)

Z/nZ has an

associative rule for multiplication:

For all

a,b,c ∈ Z/nZ: (ab)c ≡ a(bc) (mod n)(6)

Z/nZ has a

distributive rule:

For all

a,b,c ∈ Z/nZ: a(b+c) ≡ ab + ac ≡ (b + c)a (mod n)(7)

Z/nZ has a

commutative rule for multiplicationFor all

a,b ∈ Z/nZ: ab ≡ ba (mod n)(8) Thus,

Z/nZ is a

commutative ring. [See Definition 2,

here]

QED

Lemma 4: if p is a prime, then Z/pZ is a fieldProof:

(1)

Z/pZ has a

multiplicative identity rule.

1 ∈ Z/pZ and for all

a ∈ Z/pZ 1*a ≡ a*1 ≡ a (mod p)(2)

Z/pZ has a

multiplicative inverse rule since:

(a) Let

a be any nonzero element of

Z/pZ(b) If

p = 2, then

a is its own inverse and

a*a ≡ 1*1 ≡ 1 (mod 2).

(c) If

p ≥ 3, then let

b = a^{p-2}(d) Then

a*b ≡ a*(a^{p-2}) ≡ a^{p-1} ≡ 1 (mod p). [See Fermat's Little Theorem,

here]

(3) Thus,

Z/pZ is a

field. [See Definition 3,

here]

QED

Lemma 5: if

p is prime and

ab ≡ 0 (mod p), then

a ≡ 0 (mod p) or

b ≡ 0 (mod p)Proof:

(1) Assume

a is not

≡ 0 (mod p)(2) Since

ab ≡ 0 (mod p), it follows that

p divides

ab.

(3) If

a is not

≡ 0 (mod p), then it follows that

p does not divide

a.

(4) So, using Euclid's Lemma (see Lemma 2,

here), it follows that

p divides

b.

(5) And equivalently,

b ≡ 0 (mod p)QED

References