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}$ .

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.