Modular arithmetic

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

Let be a natural number, and consider the set
.
For
define and by performing these
operations in , and the subtracting multiples of
until the result is in
.
(In other words, form the sum and product of and as integers,
divide them by and take the remainders.)
These operations are called the *addition* and
*multiplication modulo *.

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

Therefore, we immediately have

As for the multiplication modulo , we have a more subtle situation. First of all we can notice that is never a group under multiplication modulo , because does not have an inverse. Still, with , and in mind, we may ask whether is a group.

So, a natural question is to try and determine for which the set forms a group under multiplication modulo . 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 and ,
their
*greatest common divisor* is
the largest positive integer which divides (with remainder )
both and .
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 and :

- 1.
*Divide:*.- 2.
*Rename:*, .- 3.
*Loop:*If then go to 1, otherwise is the required greatest common divisor.

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

We now start returning to .

Edmund F Robertson

11 September 2006