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