# Equivalence relations

## Equivalent Statements

Before proceeding it’s important to remember the following statements are equivalent

- (The | symbol means divides, or is a factor of)
- (where is some integer)

This lets us move back and forth between

**different forms**of expressing the**same idea**.**For example**the following are equivalent:

- , , which is true since
- . We can satisfy this with :

## Congruence Modulo is an Equivalence Relation

Convince yourself that the slices used in the previous example have the following properties:

- Every pair of values in a slice are related to each other
- We will never find a value in more than one slice (slices are mutually disjoint)
- If we combine all the slices together they would form a pie containing all of the values

A pie with slices that have these properties has an

An

**equivalence relation**.An

**equivalence relation**defines how we can**cut up**our pie (how we**partition**our set of values) into slices (**equivalence classes**).In general, equivalence relations must have these properties:

- The pie: A collection of all the
**values we are interested in** - A slice of pie: An
**equivalence class** - How we cut the pie into slices:
**equivalence relation**

Specifically, for our previous example:

- The pie: The collection of
**all integers** - A slice of pie labelled : Equivalence class where all the values
- How we cut the pie into slices: Using the
**congruence modulo C**relation, $\equiv (\text{mod } C)$

This is why we say that

*Congruence modulo C is an equivalence relation*. It partitions the integers into**C different equivalence classes**.## Why do we care that congruence modulo C is an equivalence relation ?

Knowing that congruence modulo C is an equivalence relation lets us know about some properties that it must have.

**Equivalence relations**are relations that have the following properties:- They are
**reflexive**: A is related to A - They are
**symmetric**: if A is related to B, then B is related to A - They are
**transitive**: if A is related to B and B is related to C then A is related to C

Since

**congruence modulo is an equivalence relation for (mod C)**. This means:- if $A \equiv B \ (\text{mod }C)$ then $B \equiv A \ (\text{mod }C)$
- if and then

## Example

Let's apply these properties to a concrete example using

- $3 \equiv 3\ \text{ mod } 5$ (
**reflexive property**) - if $3 \equiv 8\ (\text{mod }5)$ then $8 \equiv 3\ (\text{mod }5)$ (
**symmetric property**) - if $3 \equiv 8\ (\text{mod }5)$ and if $8 \equiv 18\ (\text{mod }5)$ then $3 \equiv 18\ \text{ mod }5$ (
**transitive property**)