Discrete Math Congruences

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.

Explanation:

• 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 a ⋮ b

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.

Explanation:

$a \equiv b \pmod{m}$

• In the notation:

  • 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}$

Example

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

$17 \equiv 5 \pmod{6}$

$6 \text{ divides } 17 - 5 = 12$

Solution:

$17 \equiv 5 \pmod{6} \text{ because } 6 \text{ 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:

$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:

$\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:

$\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.$