Modular arithmetic

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

Definition

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

$a=bmodn$ iff $n|(a-b)$

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

Examples

If $n=6$ then

$13=1mod6$

$10=4mod6$

$1=13mod6$

If $n=13$ then

$26=0mod13$

$42=3mod13$

Calculation

An easy way to calculate in mod{n} is $a=bmodn⟺$ 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=amodn$.

Symetry

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

Transitivity

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