Published Sep 15, 2023Updated May 15, 2024
Contribute to Docs

Congruences refer to the relationship between two integers, a and b, that have the same remainder after division by a positive integer, m (which is greater than 1).

a divides b

If a and b are integers where a ≠ 0, then a divides b if an integer c exists given that b = ac.


  • When a divides b, it is denoted as a | b.
  • a is termed as a factor or divisor of b, while b is termed as multiple of a.
  • If a | b then b / a is an integer (According to a divides b).
  • If a does not divide b, it is denoted with ab

a is congruent to b mod m

If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m|(a − b). It is termed as Congruence Relation.


  • The notation $$a \equiv b \pmod{m}$$ says that a is congruent to b modulo m.
  • m stands for modulus.
  • Two integers are congruent mod _m_ if and only if they have the same remainder on being divided by _m_.
  • If a is not congruent to b modulo m then it is denoted by $$a \not\equiv b \pmod{m}$$.


Suppose a is 17 and b is 5. To check if a is congruent to b modulo m:

  1. $$17 \equiv 5 \pmod{6}$$
  2. $$6 \text{ divides } 17 - 5 = 12$$

Solution: $$17 \equiv 5 \pmod{6}$$ because 6 divides $$17 - 5 = 12$$

Congruence Properties

Congruence properties pertain to the equivalence relation between integers where two numbers share the same remainder when divided by a fixed positive integer.

Linear Congruences

Linear congruence is a special form of congruence denoted by $$ax \equiv b \pmod{m}$$, where x denotes an integer variable. Similar to previous cases of congruence, a and b are integers and m is modulo.

Here, m is a positive integer. Solution of congruence stands for all the values of integer x which are satisfied.

Reflexive Property

A congruence relation is reflexive if for any integers:

aa(modm)for any integer a and positive integer m.a \equiv a \pmod{m} \text{for any integer } a \text{ and positive integer } m.

Symmetric Property

A congruence relation is symmetric if for any integers:

If ab(modm), then ba(modm) for any integers a,b and positive integer m.\text{If } a \equiv b \pmod{m}, \text{ then } b \equiv a \pmod{m} \text{ for any integers } a, b \text{ and positive integer } m.

Transitive Property

A congruence relation is transitive if for any integers:

If ab(modm) and bc(modm), then ac(modm) for any integers a,b,c and positive integer m.\text{If } a \equiv b \pmod{m} \text{ and } b \equiv c \pmod{m}, \text{ then } a \equiv c \pmod{m} \text{ for any integers } a, b, c \text{ and positive integer } m.

All contributors

Looking to contribute?

Learn Discrete Math on Codecademy