Congruence

Let a,bZa, b ∈ Z be two integers, and nNn ∈ N be a natural number such that n2n ≥ 2. The integers aa and bb are said to be congruent with respect to the modulus nn if and only if the following equation holds:

amodn=bmodn.a \mod n = b \mod n.

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:

abmodn.a \equiv b \mod n.

Computational Rules

Suppose that integers a1,a2,b1,b2,kZa_1, a_2, b_1, b_2, k ∈ Z are given. Then the following arithmetic rules hold for congruences:

  • a1b1modna1+kb1+kmodna_1 ≡ b_1 \mod n ⇔ a_1 + k ≡ b_1 + k \mod n (compatibility with translation)

  • a1b1modnka1kb1modna_1 ≡ b_1 \mod n ⇒ k · a_1 ≡ k · b_1 \mod n (compatibility with scaling)

  • gcd(k,n)=1 and ka1kb1modna1b1modngcd(k, n) = 1 \text{ and } k · a_1 ≡ k · b_1 \mod n ⇒ a_1 ≡ b_1 \mod n

  • ka1kb1modkna1b1modnk · a_1 ≡ k · b_1 \mod{k · n} ⇒ a_1 ≡ b_1 \mod n

  • a1b1modn and a2b2modna1+a2b1+b2modna_1 ≡ b_1 \mod n \text{ and } a_2 ≡ b_2 \mod n ⇒ a_1 + a_2 ≡ b_1 + b_2 \mod n (compatibility with addition)

  • a1b1modn and a2b2modna1a2b1b2modna_1 ≡ b_1 \mod n \text{ and } a_2 ≡ b_2 \mod n ⇒ a_1 · a_2 ≡ b_1 · b_2 \mod n (compatibility with multiplication)

Last updated