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:

Z_3 Modular Addition
Z_3 Modular Multiplication

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’.

%d bloggers like this: