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

For a given positive integer ** n**, two integers

*and*

**a***are called*

**b****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 = mq_{1} + r_{1} , 0 < r_{1}_{ }< m

Similarly, applying division algorithm for b and m, we get b = mq_{2} + r_{2} , 0 < r_{2}_{ }< m

Subtracting (a – b) *≡* m(q_{1} – q_{1}) + (r_{1} – r_{2}) ………*

As *a **≡** b (mod m) *⇒ m|(a – b) and (*) implies m|(r_{1} – r_{2})

But 0 ≤ (r_{1} – r_{2}) ≤ m ⇒ (r_{1} – r_{2}) = 0

r_{1} = r_{2}

## 6 responses to “Congruences”

[…] Congruences […]

LikeLiked by 1 person

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

[…] to the comment in Congruences, […]

LikeLiked by 1 person