# Section 2.2: Modular Arithmetic

Given any set $\mathbb{Z}_n$, where $n\in\mathbb{Z}$ we define two operations: $\oplus$ and $\odot$.

$\begin{equation}\label{ma_plus} [a] \oplus [b] = [ a+b ] \end{equation}$

and

$\begin{equation}\label{ma_dot}[a] \odot [b] = [ab]\end{equation}$

Modular Arithmetic is a binary operation. That is, a binary operation is where there are two inputs and one output.

Example in $\mathbb{Z}_7$:
\begin{align*}[3]\oplus [5] &=[8]=[1] \\ [10]\oplus [12] &=[22]=[1] \\ [3] \odot [5] &= [15]=[1] \\ [10] \odot [12] &= [120]=[1]\end{align*}

## Theorem 2.6

If $[a]=[b]$ and $[c]=[d]$ in $\mathbb{Z}_n$, then $[a+c]=[bdd]$ and $[ac]=[bd]$.

Example Modular Arithmetic table in $\mathbb{Z}_3$:

Modular Arithmetic has several different types of properties.

Theorem 2.7

1. $[a]\oplus [b] \in \mathbb{Z} \mbox{ (closure under addition) }$
2. $[a]\oplus ([b]\oplus [c] = ([a]\oplus [b]) \oplus [c] \mbox{ (associative) }$
3. $[a]\oplus [b] = [b] \oplus [a] \mbox{ (commutative) }$
4. $[a]\oplus [0] = [a] = [0]\oplus [a] \mbox{ (additive identity) }$
5. $\mbox{ For each } [a]\in \mathbb{Z}\mbox{, the equation }[a]\oplus x = [0] \mbox{ has a solution.}$
6. $[a]\oplus [b] \in \mathbb{Z}_n \mbox{ (closure under multiplication)}$
7. $[a]\odot ([b]\odot [c])=([a]\odot [b])\odot [c] \mbox{ (associative identity)}$
8. $[a]\odot ([b]\oplus [c])=[a]\odot [b] \oplus [a]\odot [c] \mbox{ which is equivalent to the expression } ([a]\oplus [b])\odot [c] = [a]\odot [c] \oplus [b]\odot [c]$
9. $[a]\odot [b]=[b]\odot [a]$
10. $[a] \odot [1]=[a]=[1]\odot [a]$

### Powers

We can further this by putting a congruence set $[a]$ to a power. Say $[a]^n=[a]\odot [a]\odot \ldots \odot [a]$. Jut as with exponents with integers, there are n number of $[a]$ being multiplied.

##### A Power Example

For $\mathbb{Z}_10$ we have $[3]^4=[81]=1$.

##### General Problems

\begin{align*}\mbox{For } \mathbb{Z}_5 & & x^2\oplus [1]=[0] \\ x=[0] & & x^2\oplus [1]=[1]\ne[0] \\ x=[1]& & x^2\oplus [1]=[2]\ne [0]\\ x=[2]& & x^2\oplus [1]=[5]\\ x=[3]& & x^2\oplus [1]=[10]\\ x=[4]& & x^2\oplus [1]=[17]=[2]\ne [0] \end{align*}

Now for $\mathbb{Z}_4$$(x\oplus x)^2=[0]$ $[2 x]^2 = [4 x^2]=[0]$. Every x in $\mathbb{Z}_4$ is a solution of $(x\oplus x)^2=[0]$.

Does there exist $[a]$ in $\mathbb{Z}_10$ such that $[a]\odot x =[1]$?

No.

$[a]=[2]$ has no solution, yet $[a]=[3]$, if $x=[7]$, $[3]\odot [7]=[21]=[1]$

###### Uses of Modular Arithmetic
• Encryption
• Clocks

Note: An analogous setting will reappear when looking at ‘rings’.