 # 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*}\oplus  &== \\ \oplus  &== \\  \odot  &= = \\  \odot  &= =\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  = [a] = \oplus [a] \mbox{ (additive identity) }$
5. $\mbox{ For each } [a]\in \mathbb{Z}\mbox{, the equation }[a]\oplus x =  \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 =[a]=\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 $^4==1$.

##### General Problems \begin{align*}\mbox{For } \mathbb{Z}_5 & & x^2\oplus = \\ x= & & x^2\oplus =\ne \\ x=& & x^2\oplus =\ne \\ x=& & x^2\oplus =\\ x=& & x^2\oplus =\\ x=& & x^2\oplus ==\ne  \end{align*}

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

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

No. $[a]=$ has no solution, yet $[a]=$, if $x=$, $\odot ==$

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

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