Congruences

a ≡ b (mod m): Given integers a, b, m with m > 0, a is congruent to b module m, [a ≡ b (mod m)], if m divides the difference a - b. The number m is called modulus of the congruence.

• a ≡ 0 (mod m) iff m/a.
• a ≡ b (mod m) iff a - b ≡ 0 (mod m).
• Congruence is an equivalence relation.

         (a) a ≡ a (mod m) (reflexivity).
         (b) a ≡ b (mod m) ⇒ b ≡ a (mod m) (symmetry)
         (c) a ≡ b (mod m) and b ≡ c (mod m) 
          ⇒ a ≡ c (mod m)              (transivity).

• If a ≡ b (mod m) and α ≡ β (mod m) then

         (a) ax + αy ≡ bx + βy (mod m) for all integers x and y.

         (b) aα ≡ bβ (mod m).

         (c) aⁿ ≡ bⁿ (mod m) for every positive integer n.

         (d) f(a) ≡ f(b) (mod m) for every polynomial f with integer coefficients.

• If c > 0 then a ≡ b (mod m) iff ac ≡ bc (mod mc).
• Cancellation law: If ac ≡ bc (mod m) and d =(m, c) then a ≡ b (mod m/d).
• Assume a ≡ b (mod m). If d/m and d/a then d/b.
• If a ≡ b (mod m) then (a, m) = (b, m).
• If a ≡ b (mod m) and if 0 ≤ |b - a| < m then a = b.
• a ≡ b (mod m) iff a and b give the same remainder when divided by m.
• a ≡ b (mod m) and a ≡ b (mod n) where (m, n) =1, a ≡ b (mod mn).

Linear Congruences:
Solution of congruence: A integer x satisfying a polynomial congruence f(x) ≡ 0 (mod m) is called a solution of the congruence.

• Assume (a, m) - 1. Then the linear congruence ax ≡ b (mod m) has exactly one solution.
• Assume (a, m) =d. Then the linear congruence ax ≡ b (mod m) has solution iff d/b.
• Assume (a, m) =d and d/b. Then the linear congruence ax ≡ b (mod m) has exactly d solutions modulo m. These are given by

          t, t + (m/d), t + (2m/d), ... , t + (d - 1)(m/d), where t is the solution, unique modulo m/d, of the linear congruence 
                     (a/d)x ≡ (b/d) (mod m/d).

• If (a, b) = d there exist integers x and y such that 

                                       ax + by = d.