The defining characteristic of $\U_n$ is that every element has a unique multiplicative inverse. It is quite possible for an element of $\U_n$ to be its own inverse; for example, in $\U_{12}$, $[1]^2=[11]^2=[5]^2=[7]^2=[1]$. This stands in contrast to arithmetic in $\Z$ or $\R$, where the only solutions to $x^2=1$ are $\pm1$. If $n$ is prime, then this familiar fact is true in $\U_n$ as well.

Theorem 3.10.1 If $p$ is a prime, the only elements of $\U_p$ which are their own inverses are $[1]$ and $[p-1]=[-1]$.

**Proof.**
Note that $[n]$ is its own inverse if and only if $[n^2]=[n]^2
= [1]$ if and only if $n^2\equiv 1\pmod p$ if and only if $p\vert
(n^2-1)=(n-1)(n+1)$. This is true if and only if $p\vert (n-1)$ or $p
\vert (n+1)$. In the first case, $n\equiv 1\pmod p$, i.e., $[n]=[1]$.
In the second case, $n\equiv -1\equiv p-1\pmod p$, i.e., $[n] =
[p-1]$.$\qed$

If $p$ is prime, $\U_p=\{[1], [2],…, [p-1]\}$. The elements $[2]$, $[3]$, …, $[p-2]$ all have inverses different from themselves, so it must be possible to pair up each element in this list with its inverse from the list. This means that if we multiply all of $[2]$, $[3]$, …, $[p-2]$ together, we must get $[1]$.

Example 3.10.2 If $p=11$, $$\eqalign{ [2]\cdot[3]\cdot[4]\cdot[5]\cdot[6]\cdot[7]\cdot[8]\cdot[9]&= ([2]\cdot[6]) ([3]\cdot[4])([5]\cdot[9])([7]\cdot[8])\cr &=[1]\cdot[1]\cdot[1]\cdot[1]=[1].\cr} $$ $\square$

This observation suggests the following, called **Wilson's Theorem**:

**Proof.**
If $p$ is prime,
$[(p-1)!]=[p-1]\cdot\left([p-2]\cdots [2]\right)\cdot[1]
=[p-1]\cdot[1]\cdot[1]=[p-1] $, and this means that $ (p-1)!\equiv
p-1\equiv -1 \pmod p $. The other direction is left as an exercise.
$\qed$

Example 3.10.4 $2!=2\equiv -1 \pmod 3$, $4!=24 \equiv -1 \pmod 5$. $\square$

Similar in spirit, and very useful, is **Euler's Theorem**:

**Proof.**
Suppose $k=\phi(n)$ and $[a_1],…, [a_k]$ is a list of the
elements of $\U_n$. By exercise 7 of section 3.4, $[u][a_1],…, [u][a_k]$
also is a list of the elements of $\U_n$. Multiplying these together
gives
$$
[a_1]\cdots [a_k]=[u]\cdot[a_1]\cdots [u]\cdot[a_k]=
[u]^k\cdot [a_1]\cdots [a_k].
$$
Canceling the $[a_i]$ terms gives $[u]^k=[1]$, i.e., $u^{\phi
(n)}\equiv 1\pmod n$.$\qed$

Example 3.10.6 If $n=8$, $u=3$, then $3^4=81\equiv 1\pmod 8$. If $n=14$, $u=5$, then $5^6=15625\equiv 1\pmod{14}$. $\square$

**Fermat's Little
Theorem** follows almost immediately
as a special case of Euler's Theorem.

Corollary 3.10.7 If $p$ is a prime, then for any $a$, $a^p\equiv a\pmod p$.

**Proof.**
If $p\vert a$, the result is clear, and if $p\notdiv a$
then $(a,p)=1$, so by theorem 3.10.5,
$a^p=a^{p-1}a\equiv 1\cdot a = a$.$\qed$

Example 3.10.8 If $p=7$ and $a=3$, then $3^7=2187\equiv 3\pmod 7$. $\square$

## Exercises 3.10

**Ex 3.10.1**
For $p= 13$ and $p=19$ find the pairing of elements
in $\U_p$ used in example 3.10.2
and (implicitly) in the proof of Wilson's Theorem.

**Ex 3.10.2**
The following fact was used in the proof of
theorem 3.10.1: If the prime $p$ divides $ab$, then
it divides either $a$ or $b$. Prove it.

**Ex 3.10.3**
Prove the following converse of exercise 2: If $n>1$ is a number with the property that whenever
$n$ divides $ab$ then $n$ divides $a$ or $n$ divides $b$, then $n$ is a
prime.

**Ex 3.10.4**
Use exercises 2 and
3 to prove: $\Z_n$ has the
property that $[x]\cdot [y]=[0]$ implies either $[x]=[0]$ or $[y]=[0]$
if and only if $n$ is prime.

**Ex 3.10.5**
Prove that if $e>2$, then $\U_{2^{\scriptstyle e}}$
has an element, other than $[2^e-1]$ and $[1]$, which is its own
inverse. (Hint: in $\U_{32}$, $[17]$ is its own inverse.)

**Ex 3.10.6**
Prove that if $p$ is a prime and $e>0$, and $\U_{p^{\scriptstyle
e}}$ has an element, other than $[p^e-1]$ and $[1]$, which is its own
inverse, then $p=2$. (Hint: If $[x]^2=[1]$, show $p\vert (x+1)$ and
$p\vert (x-1)$.)

**Ex 3.10.7**
Find all $n$ which are the products of their proper positive
divisors (e.g., $10=2\cdot 5$ is such a number).

**Ex 3.10.8**
Prove that if $x$ is any composite number other than 4, then
$(x-1)!\equiv 0 \pmod x$.

**Ex 3.10.9**
Verify Euler's Theorem in the following cases:

a) $u=3$, $n=10$

b) $u=5$, $n=6$

c) $u=2$, $n=15$

**Ex 3.10.10**
Suppose $n>0$ and $u$ is relatively prime to $n$.

a) If $\phi(n)\vert m$, prove that $u^m\equiv 1\pmod n$.

b) If $m$ is relatively prime to $\phi(n)$ and $u^m\equiv 1\pmod n$, prove that $u\equiv 1\pmod n$.

**Ex 3.10.11**
Finish the proof of Wilson's Theorem, 3.10.3.