Let a,b∈Z be two integers, and n∈N be a natural number such that n≥2. The integers a and b are said to be congruent with respect to the modulus n if and only if the following equation holds:
amodn=bmodn. In the same way, congruence is an equation “up to congruence”, which means that the equation only needs to hold if we take the modulus of both sides. This is expressed with the following notation:
a≡bmodn. Computational Rules
Suppose that integers a1,a2,b1,b2,k∈Z are given. Then the following arithmetic rules hold for congruences:
a1≡b1modn⇔a1+k≡b1+kmodn (compatibility with translation)
a1≡b1modn⇒k⋅a1≡k⋅b1modn (compatibility with scaling)
gcd(k,n)=1 and k⋅a1≡k⋅b1modn⇒a1≡b1modn
k⋅a1≡k⋅b1modk⋅n⇒a1≡b1modn
a1≡b1modn and a2≡b2modn⇒a1+a2≡b1+b2modn (compatibility with addition)
a1≡b1modn and a2≡b2modn⇒a1⋅a2≡b1⋅b2modn (compatibility with multiplication)