BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Saturday , July 22 2017

# Congruence

Definition: Let n be a fixed positive integer. Two integers a and b are said to be congruent modulo n, symbolized by

a ≡ b (mod n)

if divides the difference a – b ; that is, provided that a – b = kn for some integer k.

a is in-congruent to b modulo n in this case a ≢ b (mod n)

Theorem: For arbitrary integers a and b, a ≡ b (mod n) if and only if a and b leave the same non negative remainder when divided by n.

Proof: First take a ≡ b (mod n), so that a = b + kn for some integer k. Upon division by n, b leaves a certain remainder r; that is b = qn + r, where 0 ≤ r < n. Therefore a = b + k = (qn + r) + kn = (q + k)n + r

which indicates that a has the same remainder as b.

Conversely, suppose we can write a = q1n + r and b = q2n + r with same remainder r (0 ≤ r < n).

Then a – b = (q1n + r) – (q2n + r) = (q1 – q2) n

When n\(a – b) . In the language of congruences, this says that a ≡ b (mod n)

# Some basic properties of congruence

i) a ≡ a (mod n)

ii) If a ≡ b (mod n) then b ≡ a(mod n)

iii) If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c(mod n)

iv) If a ≡ b (mod n) and c ≡ d (mod n), then a ± c = b ± d (mod n)

v) If a ≡ b (mod n) then ac = bc (mod n)

vi) If a ≡ b (mod n) and a ≡ c(mod n), then b ≡ c (mod n)

vii) If a ≡ b (mod n), then ak ≡ bk(mod m), for all k ≥ 1 but if ak ≡ bk (mod n) for k ≥ 2, then a ≡ b (mod n) may not be true.

## Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...