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:
- 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)
- 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 = mq1 + r1 , 0 < r1 < m
Similarly, applying division algorithm for b and m, we get b = mq2 + r2 , 0 < r2 < m
Subtracting (a – b) ≡ m(q1 – q1) + (r1 – r2) ………*
As a ≡ b (mod m) ⇒ m|(a – b) and (*) implies m|(r1 – r2)
But 0 ≤ (r1 – r2) ≤ m ⇒ (r1 – r2) = 0
r1 = r2
What is the practical application of congruence nowadays?
LikeLiked by 1 person
First of all I liked your question. Actually it gave me an idea of adding real life applications of mathematical concepts to my site! Thank you!
Please click on https://breathmath.com/2016/07/25/what-is-the-practical-application-of-congruence-nowadays/
LikeLiked by 1 person