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:

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

Example

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:

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