next up previous contents
Next: Permutations Up: MT2002 Algebra Previous: Groups - definition and   Contents


Modular arithmetic

In this and the following two sections we introduce some important examples of groups.

Let $n>0$ be a natural number, and consider the set ${\mathbb{Z}}_n=\{ 0,1,\ldots,n-1\}$. For $a,b\in {\mathbb{Z}}_n$ define $a+b$ and $ab$ by performing these operations in $\mathbb{Z}$, and the subtracting multiples of $n$ until the result is in ${\mathbb{Z}}_n$. (In other words, form the sum and product of $a$ and $b$ as integers, divide them by $n$ and take the remainders.) These operations are called the addition and multiplication modulo $n$.


\begin{ex}
Let us work modulo $7$. We have
\begin{eqnarray*}
1+1=2\\
4+6=3\\
3+4=0\\
2\cdot 5=3,
\end{eqnarray*}and so on.
\end{ex}

One can relatively easy see that the addition and multiplication modulo $n$ satisfy the following properties:

\begin{eqnarray*}
&&(x+y)+z=x+(y+z),\ (xy)z=x(yz),\\
&&x+0=0+x=x,\ 1\cdot x=x\c...
...(n-x)=(n-x)+x=x,\\
&&x+y=y+x,\ xy=yx,\\
&&x\cdot 0=0\cdot x=0.
\end{eqnarray*}



Therefore, we immediately have


\begin{thm}
The set ${\mathbb{Z}}_n$\ with the operation of addition modulo $n$\ is
an abelian group.
\end{thm}

As for the multiplication modulo $n$, we have a more subtle situation. First of all we can notice that ${\mathbb{Z}}_n$ is never a group under multiplication modulo $n$, because $0$ does not have an inverse. Still, with $\mathbb{Q}$, $\mathbb{R}$ and $\mathbb{C}$ in mind, we may ask whether ${\mathbb{Z}}_n\setminus\{0\}$ is a group.


\begin{ex}
Let us write down the Cayley table for multiplication modulo $7$on th...
...\mathbb{Z}}_7\setminus\{0\}$\ is a group
under multiplication modulo 7.
\end{ex}


\begin{ex}
Working modulo $10$\ we have, for example,
$2\cdot 5=0$. So we conclu...
...1$, because $2x$\ is always even. Hence, $2$\ does not have an inverse.
\end{ex}

So, a natural question is to try and determine for which $n$ the set ${\mathbb{Z}}_n\setminus\{0\}$ forms a group under multiplication modulo $n$. As the previous two examples show, problems arise when considering closure and inverses. It will actually turn out that the latter is a more serious than the former, and to sort it out we need to make a small detour into elementary number theory.

The first fact is the well known fact about the division of integers with a quotient and remainder.


\begin{thm}
For any two integers $a,b$, with $b> 0$, there are unique
integers $q,r$\ such that $a=bq+r$\ and $0\leq r\leq b-1$.
\end{thm}

Next we recall that for two non-zero integers $a$ and $b$, their greatest common divisor $\gcd (a,b)$ is the largest positive integer which divides (with remainder $0$) both $a$ and $b$. Next we give an alternative description of this number:


\begin{thm}
The greatest common divisor $d$\ of two non-zero integers $a$\ and $...
...
in the form $\alpha a+ \beta b$\ with $\alpha$\ and $\beta$ integers.
\end{thm}


\begin{proof}
Since $d_1=\alpha a+\beta b$, and since $d$\ divides both $a$\ and...
...d\vert d_1$\ and $d\geq d_1$\ we conclude that $d=d_1$,
as required.
\end{proof}

The above proof suggests the following algorithm for finding the greatest common divisor of two numbers $a$ and $b$:

1.
Divide: $a=qb+r$.
2.
Rename: $a:=b$, $b:=r$.
3.
Loop: If $r\neq 0$ then go to 1, otherwise $b$ is the required greatest common divisor.

If at every stage you also keep track how $r$ is expressed as a linear combination of (the original) $a$ and $b$, at the end you will obtain the greatest common divisor expressed in that form as well.


\begin{ex}
Let us compute $\gcd (534,81)$.
\begin{displaymath}
\begin{array}{rcr...
...displaymath}We conclude that $\gcd(534,81)=3=-5\cdot 534 + 33\cdot 81$.
\end{ex}

We now start returning to ${\mathbb{Z}}_n$.


\begin{thm}
For $a\in {\mathbb{Z}}_n$\ there exists $b\in{\mathbb{Z}}_n$such that $ab=1$\ if and only if $\gcd(a,n)=1$.
\end{thm}


\begin{proof}
% latex2html id marker 267If you recall the definition of multip...
...ich is satisfied if and only if $\gcd(a,n)=1$by Theorem \ref{thm14}.
\end{proof}


\begin{ex}
Let us find the multiplicative inverse of $57$\ modulo $100$.
\begin{...
...$(-7)\cdot 57 + 4\cdot 100=1$, so
that $(57)^{-1}=-7=93$\ modulo $100$.
\end{ex}


\begin{thm}
The set $U_n=\{ x\in{\mathbb{Z}}_n\st \gcd(x,n)=1\}$\ is a group
under multiplication modulo $n$.
\end{thm}


\begin{proof}
% latex2html id marker 283Multiplying two numbers co-prime to $n...
... U_n$!).
The existence of inverses follows from Theorem \ref{thm16}.
\end{proof}


\begin{thm}
The set ${\mathbb{Z}}_n\setminus\{0\}$\ is a group under the multiplication
modulo $n$\ if and only if $n$\ is a prime number.
\end{thm}


\begin{proof}
($\Rightarrow$)
Assume that $n$\ is not a prime number, say $n=qr$...
...tarrow$) If $n$\ is a prime then $U_n={\mathbb{Z}}_n\setminus\{0\}$.
\end{proof}


next up previous contents
Next: Permutations Up: MT2002 Algebra Previous: Groups - definition and   Contents

Edmund F Robertson

11 September 2006