Modular arithmetic

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

## Definition

[edit | edit source]

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

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

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

### Examples

[edit | edit source]

If  n = 6 {\displaystyle n=6} then

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

If  n = 13 {\displaystyle n=13} then

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

## Calculation

[edit | edit source]

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

## Equivalence

[edit | edit source]

Congruence modulo n is an equivalence relation.

### Reflexivity

[edit | edit source]

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

### Symmetry

[edit | edit source]

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

### Transitivity

[edit | edit source]

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