Modular Arithmetic

Deals with arithmetic of cyclical numbers
Wikipedia

Topics

Definitions

$a\equiv b\left(\text{mod }n\right)\leftrightarrow a=kn+b\leftrightarrow a=pn+r\wedge b=qn+r,k,p,q\in \mathbb{R}$

• Reads: $a$ is congruent to $b$ modulo $n$, or $n$ divides $a-b$
• $r$ is the remainder of $\frac{a}{n}$ and $\frac{b}{n}$

$r=\text{mod}\left(a,n\right)=a\text{ mod }n=a\%n\leftrightarrow a=pn+r,p\in \mathbb{R}$

• $r$ is the remainder of $\frac{a}{n}$

$0\le r<n$

• $r$ is the remainder of a division by $n$

$a+b\equiv 0\left(\text{mod }n\right)\to a=b^{-1}\text{ on }n$

• $a$ and $b$ are inverses of each other on $n$ if their sum congruent to $0$

Properties

1. Reflexivity
   1. $a\equiv a\left(\text{mod }n\right)$
2. Symmetry
   1. $a\equiv b\left(\text{mod }n\right)\leftrightarrow b\equiv a\left(\text{mod }n\right)$
3. Transitivity
   1. $a\equiv b\left(\text{mod }n\right)\wedge b\equiv c\left(\text{mod }n\right)\to a\equiv c\left(\text{mod }n\right)$
4. $\text{mod}\left(a,n\right)\approx n-\text{mod}\left(-a,n\right)$
   1. They are equal except for when $\text{mod}\left(a,n\right)=0$, in which case the right hand side is equal to $n$

Applications

• Date to Day