# Modular arithmetic

Modular arithmetic is a type of arithmetic on finite subsets of the natural numbers

## Definition

For ${\displaystyle n\in \mathbb {Z} }$ then

${\displaystyle a=b\mod {n}}$ iff ${\displaystyle n|(a-b)}$

This is read as "a is congruent modulo n to b".

### Examples

If ${\displaystyle n=6}$ then

${\displaystyle 13=1\mod {6}}$
${\displaystyle 10=4\mod {6}}$
${\displaystyle 1=13\mod {6}}$

If ${\displaystyle n=13}$ then

${\displaystyle 26=0\mod {13}}$
${\displaystyle 42=3\mod {13}}$

## Calculation

An easy way to calculate in mod{n} is ${\displaystyle a=b\mod {n}\iff }$ they have the same remainder when divided by ${\displaystyle n}$.

## Equivalence

Congruence modulo n is an equivalence relation.

### Reflexivity

Let ${\displaystyle n,a\in \mathbb {Z} }$. Then ${\displaystyle (a-a)=0}$ and ${\displaystyle n|0}$ so ${\displaystyle n|(a-a)}$. Thus ${\displaystyle a=a\mod {n}}$.

### Symetry

Let${\displaystyle n,x,y\in \mathbb {Z} }$ such that ${\displaystyle x=y\mod {n}}$. Then ${\displaystyle n|(x-y)}$. Since ${\displaystyle (x-y)=(-1)*(y-x),n|(y-x)}$. Thus ${\displaystyle y=x\mod {n}}$.

### Transitivity

Let${\displaystyle n,a,b,c\in \mathbb {Z} }$ such that${\displaystyle x=y\mod {n}\land y=z\mod {n}}$. Then ${\displaystyle n|(x-y)\land n|(y-z)}$. Then ${\displaystyle n|((x-y)+(y-z)}$. Thus ${\displaystyle n|(x-z)}$ and ${\displaystyle x=z\mod {n}}$.