**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 = q_{1}n + r and b = q_{2}n + r with same remainder r (0 ≤ r < n).

Then a – b = (q_{1}n + r) – (q_{2}n + r) = (q_{1} – q_{2}) 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 a^{k} ≡ b^{k}(mod m), for all k ≥ 1 but if a^{k} ≡ b^{k} (mod n) for k ≥ 2, then a ≡ b (mod n) may not be true.