Congruence Modulo 'n'

Question 1

What is meant by a ≡ b modulus n?

Answer 1

‘a’ is said to be congruent to ‘b’ (a ≡ b) modulus n if:
1. n|(a - b)
2. a and b have the same remainder when divided by n
3. a = b + kn, where k is some multiple of n.

n ∈ N > 1, and a, b ∈ Z ( N = natural numbers, Z = integers)

Question 2

Prove that congruency is reflexive.

Answer 2

For a relation R to be reflexive, (a, a) ∈ R. Thus this must be true a ≡_n a.
Recall a ≡_n b <=> a = b + kn.
Thus, a ≡_n a <=> a = a + kn.
k, being a multiple of n, can be written as:
a = a + 0•n
Thus a ≡_n a is reflexive.

Question 3

Prove ≡_n is symmetric.

Answer 3

For a relation R to be symmetric:
(a, b) ∈ R => (b, a) ∈ R.
Suppose a ≡_n b, then
a = b + kn
a - b = kn
-a + b = (-k)n
b - a = (-k)n
Since ‘-k’ is still a multiple of n, it can be written as:
b - a = mn
Thus as n|(b -a), a ≡_n b => b ≡_n a, it is symmetric.

Question 4

Prove that congruency is transitive.

Answer 4

For a relation R to be transitive,
(a, b) ∈ R, (b, c) ∈ R => (a, c) ∈ R.
Thus a ≡_n b, b ≡_n c => a ≡_n c.
Notice a ≡_n b <=> a - b = k₁n, b ≡_n c <=> b - c = k₂n, a ≡_n c <=> a - c = k₃n.

Notice also that a - c = (a - b) + (b - c);
a - c = k₁n + k₂n,
=> a - c = (k₁ + k₂)n
As (k₁ + k₂) is still considered a multiple of n, their addition can be written as k₃:

a - c = k₃n.

It is seen that n|a - c. Thus, this is transitive.