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,

So

* Example.* 157 is prime. Reduce to a number in .

By Fermat's Theorem, . So

Next,

Hence, .

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

Thus, .

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

Copyright 2018 by Bruce Ikenaga