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:

Theorem 3.10.3 If $p>1$ then $p$ is prime iff $(p-1)!\equiv -1\pmod p$.

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:

Theorem 3.10.5 If $n>0$, and $u$ is relatively prime to $n$, then $$ u^{\phi(n)}\equiv 1\pmod n. $$

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:

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

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