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

```
KaTeX parse error: Expected 'EOF', got '\
' at position 166: …ve integer } m.\̲
̲
```

### Looking to contribute?

- Learn more about how to get involved.
- Edit this page on GitHub to fix an error or make an improvement.
- Submit feedback to let us know how we can improve Docs.