Modular arithmetic

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

Definition

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

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

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

Examples

If $n=6$ then

$13=1\mod {6}$

$10=4\mod {6}$

$1=13\mod {6}$

If $n=13$ then

$26=0\mod {13}$

$42=3\mod {13}$

Calculation

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

Equivalence

Congruence modulo n is an equivalence relation.

Reflexivity

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

Symetry

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

Transitivity

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