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

Next: Permutations Up: MT2002 Algebra Previous: Groups - definition and   Contents

Edmund F Robertson

11 September 2006