The group consists of the elements with addition mod n as the operation. You can also {\it multiply} elements of , but you do not obtain a group: The element 0 does not have a multiplicative inverse, for instance.
However, if you confine your attention to the units in --- the elements which have multiplicative inverses --- you do get a group under multiplication mod n. It is denoted , and is called the group of units in .
Proposition. Let be the set of units in , . Then is a group under multiplication mod n.
Proof. To show that multiplication mod n is a binary operation on , I must show that the product of units is a unit.
Suppose . Then a has a multiplicative inverse and b has a multiplicative inverse . Now
Hence, is the multiplicative inverse of , and is a unit. Therefore, multiplication mod n is a binary operation on .
(By the way, you may have seen the result when you studied linear algebra; it's a standard identity for invertible matrices.)
I'll take it for granted that multiplication mod n is associative.
The identity element for multiplication mod n is 1, and 1 is a unit in (with multiplicative inverrse 1).
Finally, every element of has a multiplicative inverse, by definition.
Therefore, is a group under multiplication mod n.
Before I give some examples, recall that m is a unit in if and only if m is relatively prime to n.
Example. ( The groups of units in ) consists of the elements of which are relatively prime to 14. Thus,
You multiply elements of by multiplying as if they were integers, then reducing mod 14. For example,
Here's the multiplication table for :
Notice that the table is symmetric about the main diagonal. Multiplication mod 14 is commutative, and is an abelian group.
Be sure to keep the operations straight: The operation in is addition mod 14, while the operation in is multiplication mod 14.
Example. ( The groups of units in ) If p is prime, then all the positive integers smaller than p are relatively prime to p. Thus,
For example, in , the group of units is
The operation in is multiplication mod 11. For example, in . Here's the multiplication table for :
Example. ( The subgroup generated by an element) The elements in which are relatively prime to 18 are the elements of :
The operation is multiplication mod 18.
Since the operation is multiplication, the cyclic subgroup generated by 7 consists of all powers of 7:
I can stop here, because mod 18. So
On the other hand, consider , the cyclic group of order 20. In this group, the operation is addition mod 20. Since the operation is addition, the subgroup generated by an element --- say 8 --- consists of all multiples of 8:
I can stop here, because mod 20. So
For the next result, I'll need a special case of Lagrange's theorem: The order of an element in a finite group divides the order of the group. I'll prove Lagrange's theorem when I discuss cosets.
As an example, in a group of order 10, an element may have order 1, 2, 5, or 10, but it may not have order 8.
Corollary. ( Fermat's Theorem) If a and p are integers, p is prime, and , then
Proof. The elements
of are relatively prime to p, so
In particular, .
Now if , then
Lagrange's theorem implies that the order of an element divides the order of the group. As a result, in . Hence,
Example. ( Using Fermat's Theorem to reduce a power) Compute .
The idea is to use Fermat's theorem to reduce the power to smaller numbers where you can do the computations directly.
97 is prime, and . By Fermat's theorem,
So
Copyright 2008 by Bruce Ikenaga