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

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

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.

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.

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:

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.

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