Congruences

A congruence relation (or simply congruence) is an equivalence relation.

For a given positive integer n, two integers a and b are called congruent modulo.  

 

i.e., 27 ≡ 47 (mod 10)

Since, 27  – 47 = -20, which is multiple of 10.equivalently since both 27 and 47 have same remainder when divided by 10.

---

DEFINITION: 

Let a, b, m € Z and m ≥ 2. Then ‘a’ is said to be congruent to ‘b’ modulo m if m|(a – b) i.e., a ≡ b (mod m) ⇔ m|(a – b) 

Clearly,  when we divide a and b by m, they should leave the same remainder. Therefore,

Let a, b, m € Z and m ≥ 2. Then ‘a’ is said to be congruent to ‘b’ modulo m if m|(a – b) i.e., a ≡ b (mod m) ⇔ (a and b should leave the same remainder on division by m)

For example:

111 ≡ 15 (mod 6) ; 6| (111 – 15) = 96

---

PROPERTIES OF CONGRUENCE: 

1. The relation ‘congruence modulo n’ is an equivalence relation on Z.

Reflexive: Let a be any integer. Then a ≡ a (mod m)

m|(a – a) = 0 [i.e., m|0]

∴ ‘≡’ is reflexive.

Symmetric: Let a ≡ b (mod m) ⇒ m|(a – b)

∴ m|-(a-b) i.e., m|(b-a) ⇒ b ⇒ a(mod m)

∴ ‘≡’ is symmetric.

Transitive: Let a ≡ b (mod m) and b ≡ c (mod m) 

⇒ m|(a-b) and m|(b-c)

⇒ m|[(a-b)+(b-c)]

i.e., m|[a-b+b-c]

⇒m|[a-c]

⇒ a ≡ c (mod m)

‘≡’ is transitive.

---

2. IF a ≡ b (mod m)  and  x  is an integer. (i) (a + x) ≡ (b + x) (mod m) (ii) (a – x) ≡ (b – x) (mod m) (iii) ax ≡ bx (mod m)

Proof: 

(i) a ≡ b (mod m) ⇒ m|(a-b) 

∴ m|(a+x)-(b+x) 

i.e., (a+x)  ≡ (b+x) (mod m)

(ii) a ≡ b (mod m) ⇒ m|(a-b) 

∴ m|(a-x)-(b-x)

i.e., (a-x)  ≡ (b-x) (mod m)

(iii) a ≡ b (mod m) ⇒ m|(a-b) 

∴ m|(ax)-(bx)

i.e., ax  ≡ bx (mod m)

---

3. If a ≡ b (mod m) and   c ≡ d (mod m),

(i)  (a+c) ≡ (b+d) (mod m)

(ii) (a-c) ≡ (b-d) (mod m)

(iii)  ac ≡ bd (mod m)

Proof:

We know, a ≡ b (mod m) ⇒ m|(a-b)  and  c ≡ d (mod m) ⇒ m|(c-d) 

(i) m|[(a-b)+(c-d)] i.e., m|[(a+c)-(b+d)]

∴ (a+c)  ≡ (b+d) (mod m)

(ii) m|[(a-b)-(c-d)] i.e., m|[(a-c)-(b-d)]

∴ (a-c) ≡ (b-d) (mod m)

(iii) m|(a – b) and m|(c – d) ⇒ m|[(a-b)c + (c-d)b] = m|[ac – bc + cb -bd]

i.e., m|(ac-bd) ⇒ ac ≡ bd (mod m)

---

4. If ca ≡ cb (mod m) and (c,m) ≡ 1, then a ≡ b (mod m) (Cancellation law)

Proof:

ca ≡ cb (mod m) 

⇒ m|((ca-cb)

⇒ m|(a – b)

⇒ a ≡ b (mod m)

---

5. If a ≡ b (mod m) and n>1 is a positive divisor of m, a ≡ b (mod n)

Proof:

a ≡ b (mod m) ⇒ m|(a – b)—–(1)

n is a positive divisor of m ⇒ n|m ————–(2)

From (2) and (1)

n|(a – b) by transitive property of divisibility

n|(a – b) by transitive property of divisibility

∴ a ≡ b (mod n)

---

6. a ≡ b (mod m) ⇒ a and b leave the same remainder when divided by m.

Proof:

Applying division algorithm for a and m, we get

a = mq₁ + r₁ , 0 < r₁ < m

Similarly, applying division algorithm for b and m, we get b = mq₂ + r₂ , 0 < r₂ < m

Subtracting (a – b) ≡ m(q₁ – q₁) + (r₁ – r₂) ………*

As a ≡ b (mod m) ⇒ m|(a – b) and (*) implies m|(r₁ – r₂)

But 0 ≤ (r₁ – r₂) ≤ m ⇒ (r₁ – r₂) = 0

r₁ = r₂

---