| | |
Suppose we are curious about the nature of multiplicative inverses in a given modulus. We know that, provided the inverse of a given value exists $\pmod{n}$, we can find it -- either by inspection or by using the Euclidean Algorithm in a clever way.
To reduce the complications of non-existent multiplicative inverses, let us assume that we are looking at some prime modulus, $p$. Then we know for sure that $1,2,3,\ldots (p-1)$ will all have multiplicative inverses, as these are all relatively prime to $p$.
To consider a specific example, suppose we are working in $\pmod{7}$. Then the following lists all of the multiplicative inverses therein:
$$1^{-1} \equiv 1, \quad 2^{-1} \equiv 4, \quad 3^{-1} \equiv 5, \quad 4^{-1} = 2, \quad 5^{-1} = 3, \quad \textrm{ and } \quad 6^{-1} = 6$$Note, there seem to be two cases here. We either have pairs of values that are inverses of each other (like $2$ and $4$), or we have values which are their own multiplicative inverses (like $6$).
If we find and organize our findings similarly for some other prime moduli (as shown below), one might notice a peculiar commonality...
$$\begin{array}{llc}
\pmod{7} & \textrm{Inverse pairs:} & \{2,4\}, \{3,5\}\\
&\textrm{Inverses of themselves:} & 1 \textrm{ and } 6\\\\
\pmod{13} &\textrm{Inverse pairs:} & \{2,7\}, \{3,9\}, \{4,10\}, \{5,8\}, \{6,11\}\\
& \textrm{Inverses of themselves:} & 1 \textrm{ and } 12\\\\
\pmod{19} &\textrm{Inverse pairs:} & \{2,10\}, \{3,13\}, \{4,5\}, \{6,16\}, \{7,11\}, \{8,12\}, \{9,17\}\\
& \textrm{Inverses of themselves:} & 1 \textrm{ and } 18
\end{array}$$
It appears that there are always exactly two values that are their own multiplicative inverses: $1$ and $(p-1)$. Can we prove this to be the case?
Presuming $p$ is some prime, suppose $x$ is its own multiplicative inverse, modulo $p$. Equivalently,
$$x^2 \equiv 1 \pmod{p}$$Turning this into a statement about divisibility, we have
$$p \mid (x^2 - 1)$$The expression on the right can be factored, however, and this leads to
$$p \mid (x-1)(x+1)$$Given that $p$ was presumed to be prime, however, we can then conclude that either $p$ divides the factor on the left, or $p$ divides the factor on the right
$$p \mid (x-1) \quad \quad \textrm{ or } \quad \quad p \mid (x+1)$$In the language of congruences, this is the same as saying
$$x \equiv 1 \quad \quad \textrm { or } \quad \quad x \equiv -1 \pmod{p}$$Finally, noting that $-1 \equiv p-1$, we conclude that if $x$ is its own multiplicative inverse, it must either be congruent to $1$ or $(p-1) \pmod{p}$.
While curious in its own right, this result has a most interesting (and useful) corollary:
Wilson's Theorem If $p$ is prime, then $(p-1)! \equiv -1 \pmod{p}$ |
With the previous arguments at our disposal, the proof of Wilson's Theorem is immediate...
Notice the factors of $(p-1)!$ are precisely the non-zero remainders seen modulo $p$.
We know from our above discussion that these values can be separated into two groups: a group consisting of some number of pairs of values that are multiplicative inverses of each other, and a group of exactly two values ($1$ and $p-1$) that are their own multiplicative inverses.
This allows us to greatly simplify $(p-1)! \pmod{p}$, as the example below demonstrates.
$$\begin{array}{rcl} (13-1)! \quad = \quad 12! &=& 1 \cdot (2 \cdot 7) \cdot (3 \cdot 9) \cdot (4 \cdot 10) \cdot (5 \cdot 8) \cdot (6 \cdot 11) \cdot 12\\ &\equiv& 1 \cdot (1) \cdot (1) \cdots (1) \cdot 12\\ &\equiv& 12\\ &\equiv& -1 \pmod{p} \end{array}$$Regardless of the modulus (as long as it is prime), the pairs of multiplicative inverses necessarily vanish, as does the additional value of $1$, leaving only $(p-1) \equiv -1 \pmod{p}$, which is what the theorem claims.
QED.