The group consists of the elements with addition mod n as the operation. You can also 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 ) Construct a multiplication table for .
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 ) What are the elements of if p is a prime number?
Construct a multiplication table for .
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) List the elements of in .
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
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.
Theorem. ( Fermat's Theorem) If a and p are integers, p is prime, and , then
Proof. If p is prime, then
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,
Example. 157 is prime. Reduce to a number in .
By Fermat's Theorem, . So
Here is a result which is related to Fermat's Theorem.
Theorem. ( Wilson's Theorem) p is prime if and only if
Proof. If p is prime, consider the numbers in . Note that if , then , so
Hence, , and by Euclid's lemma either and or and .
In other words, the only two numbers in which are their own multiplicative inverses are 1 and . The other numbers in this set pair up as a and with . Hence, the product simplifies to
On the other hand, if p is not prime, then p is composite. If where , then
The only other possibility is that , where q is a prime.
If , then
Then both and q appear in the set , so the product contains a factor of . Once again, .
The final case is and . Then
Example. 131 is prime. Reduce to a number in .
By Wilson's Theorem, . So
Bruce Ikenaga's Home Page
Copyright 2018 by Bruce Ikenaga