A Generalization of Wilson’s Theorem (due to Gauss)

John Wilson (1741-1793) was a well-known English mathematician in his time, whose legacy lives on in his eponymous result, Wilson’s Theorem. To recall, this is the statement that an integer $n >1$ is prime if and only if

$(n-1)! \equiv -1 \mod n.$

(The “if” part is trivial.) As is the case for many historical results, Wilson’s Theorem was not proven by Wilson. Instead, it was Joseph Lagrange who provided the first proof.

The proof, as we see it today, might be phrased as follows:

Proof: Suppose that $p$ is prime. Then each of the nonzero residues modulo $p$ is a unit, so that $(p-1)!$ represents the product over all units in $\mathbb{Z}/p\mathbb{Z}$ . If

$a \not\equiv a^{-1} \mod p$ , i.e. $a^2 \not\equiv 1 \mod p$ ,

then $a$ and its inverse each show up in our list of units. We cancel out such terms in pairs, and conclude that

$\displaystyle (p-1)! \equiv \prod_{a^2 \equiv 1 (p)} a \mod p.$

We have $a^2 \equiv 1 \mod p$ if and only if $p \mid (a-1)(a+1)$ , which by primality of $p$ forces $p \mid (a-1)$ or $p \mid (a+1)$ . In other words, $a \equiv \pm 1 \mod p$ . It follows that

$(p-1)! \equiv 1(-1) \equiv -1 \mod p.$

$\square$

When $n$ is composite, the direct translation of Wilson’s problem gives

$(n-1)! \equiv 0 \mod n.$

The problem, here, is that we’ve multiplied a number of zero divisors together, which can be avoided by only multiplying across the units, $U_n$ , of $\mathbb{Z}/n\mathbb{Z}$ . In this post, we consider the product

$\displaystyle \prod_{a \in U_n} a \mod n,$

determine its value, give credit to Gauss for doing so over two centuries ago, and discuss a few generalizations.

— WILSON’S THEOREM FOR CYCLIC GROUPS —

One particularly tedious proof from elementary number theory is the classification of cyclic unit groups. That is,

Question: When is $U_n$ a cyclic group?

It turns out that $U_n$ is cyclic if and only if $n$ takes one of the following forms:

$n = 1, \, 2, \, 4,\, p^k,\, 2p^k,$

for $p$ an odd prime and $k \geq 1$ . (This can also be proven using the structure theorem for finite abelian groups, which is a bit of overkill but is certainly easier in practice.) If $U_n$ is cyclic, we have a cute proof of Wilson’s Theorem that extends beyond the case $n$ prime:

Theorem: If $U_n$ is cyclic, then

$\displaystyle \prod_{a \in U_n} a \equiv -1 \mod n.$

Proof: If $U_n$ is cylic, it admits a generator $g \in U_n$ . Since $g$ generates all of $U_n$ , we have

$\displaystyle\prod_{a \in U_n} a \equiv \prod_{j=1}^{\varphi(n)} g^j \equiv g^{\frac{\varphi(n)(\varphi(n)+1)}{2}} \mod n.$

We recall that $g^m \equiv 1 \mod n$ if and only if $\varphi(n) \mid m$ . In the case above, this divisibility condition amounts to whether or not $\varphi(n)+1$ is even, ie. if $\varphi(n)$ is odd. This fails except in the case $n=2$ , whereby we see that the product in question cannot be $1$ .

On the other hand, it is clear that our product is a square root of $1$ . (Just look at the expression at right in the line above.) But a cyclic group only admits two square roots of $1$ (again, think about generators), so our product over the units must be the other square root of $1$ , ie. $-1$ . $\square$

— GAUSS’ GENERALIZATION TO ACYCLIC GROUPS —

Question: What about when $U_n$ is not cyclic?

This first occurs in the case $n=8$ , in which we calculate

$1 \cdot 3 \cdot 5 \cdot 7 \equiv 1 \mod 8.$

The next case is $n=12$ , which gives

$1 \cdot 5 \cdot 7 \cdot 11 \equiv 1 \mod 12.$

It’s not too hard to prove that the product over the units in $U_n$ should be a square root of $1$ . Unfortunately, this doesn’t pin down our answer very much in general. For example, every unit in $U_8$ is a square root of $1$ , and the same holds for $U_{12}$ , too! (It’s not always this bad, however.)

In his Disquisitiones Arithmeticae, Gauss proved that the pattern emerging above continues. That is,

Theorem (Gauss): The product over the units in $U_n$ is $-1$ if $U_n$ is cyclic. Otherwise, this product is $1$ .

Proof: Our proof begins with the fundamental theorem of finite abelian groups. If $n = p_1^{k_1} \cdots p_\ell^{k_\ell}$ as a factored product of distinct primes, then

$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p_1^{k_1}\mathbb{Z} \times\cdots \times\mathbb{Z}/p_\ell^{k_\ell}\mathbb{Z}.$

It follows that

$U_n \cong U_{p_1^{k_1}} \times \ldots \times U_{p_\ell^{k_\ell}}.$

For $p_i>2$ , let $g_i$ be a generator of $U_{p_i^{k_i}}$ . Let $h_1,\ldots, h_m$ denote the elements of the acyclic group $U_{2^k}$ . We check that the product over all units is thus

$(h_1\cdots h_m)^{\varphi(n/2^k)} g_1^{\frac{\varphi(n)(\varphi(p_1^{k_1})+1)}{2}} \cdots g_\ell^{\frac{\varphi(n)(\varphi(p_\ell^{k_\ell})+1)}{2}}.$

These powers of $g_i$ will vanish under the assumption that

$\varphi(p_i^{k_i}) \mid \frac{\varphi(n)(\varphi(p_i^{k_i})+1)}{2},$

which is met if and only if $\varphi(n/p_i^{k_i})$ is even. This occurs so long as $n/p_i^{k_i}$ has a prime factor $p>2$ or a factor of $2$ with multiplicity at least $2$ . In other words, this occurs whenever $U_n$ is not cyclic. When $U_n$ is not cyclic, the product over all units in $U_n$ may therefore be written

$(h_1 \cdots h_m)^{\varphi(n/2^k)}.$

It thus suffices to show our claim in the case $n = 2^k$ , with $k \geq 3$ . That is, that

$h_1 \cdots h_m \equiv 1 \mod n.$

We leave it as an Exercise that $U_{2^k} \cong \mathbb{Z}/2^{k-2}\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ . If we let $a$ and $b$ represent generators for these two subgroups, respectively, then the product over units in $U_{2^k}$ may be written

$a^{2^{k-2}(2^{k-2}+1)} b^{2^{k-2}}\equiv (a^{2^{k-2}+1} b)^{2^{k-2}}.$

Since $U_{2^k}$ is acyclic, it has exponent strictly less than its order, $\varphi(2^k)=2^{k-1}$ . Thus the exponent divides $2^{k-2}$ , hence the product above is $1$ , which completes our proof. $\square$

Remarks — I did not examine Gauss’ proof of the preceding Theorem (DA, art. 78) before deriving it independently. I had assumed that Gauss proved this fact using a direct, elementary approach. The opposite is true – Gauss’ proof mirrors ours given above, insofar as both require the structure theorem for finite abelian groups. Need I mention that the structure theorem for finite abelian groups is likewise due to Gauss?

— WILSON’S THEOREM IN FINITE ABELIAN GROUPS —

Nothing stops us from generalizing the proof in the previous section to the case of $G$ , an arbitrary finite abelian group. In this case, our Theorem takes the following form:

Theorem: If $G$ has a unique element $g$ of order $2$ , then the product over the elements in $G$ is exactly $g$ . Otherwise, this product is $1$ .

Proof: Recall that in our very first proof of Wilson’s Theorem, we have characterized this product as the product over all elements in $G$ of order exactly $2$ . If there is a unique such element, say $g$ , the product over all elements in $G$ is clearly $g$ .

The “otherwise” claim is far more interesting. Note that the elements of $G$ with order at most $2$ form a subgroup, which — by the structure theorem of finite abelian groups — is necessarily isomorphic to $(\mathbb{Z}/2\mathbb{Z})^k$ for some integer $k \geq 2$ . Fixing generators $a_1,\ldots, a_k$ for these components, we recognize the product over $(\mathbb{Z}/ 2\mathbb{Z})^k$ as

$a_1^{2^{k-1}}a_2^{2^{k-1}}\cdots a_k^{2^{k-1}} = (a_1\cdots a_k)^{2^{k-1}}=1,$

in which we’ve used that the exponent of $(\mathbb{Z}/2\mathbb{Z})^k$ is $2$ . $\square$

Remark — To recover our earlier results from this very general theorem, we need only prove that $U_n$ has a unique element of order $2$ if and only if $U_n$ is cyclic. This follows from the classification of cyclic unit groups $U_n$ and careful consideration of the Euler phi function; navigating this was the major obstruction in the theorem we credited to Gauss. (Of course, Gauss would not have considered the problem in this way.)

— EXERCISES —

Exercise: Prove Wilson’s Theorem by calculating the number of $p$ -Sylow subgroups of the symmetric group $S_p$ .

Exercise: Deduce Wilson’s Theorem from Burnside’s Lemma by considering the following group action: cyclic permutation of the set of $p$ -cycles in $S_p$ .

Exercise: Prove that $U_{2^k} \cong (\mathbb{Z}/2^{k-2}\mathbb{Z}) \times (\mathbb{Z}/2\mathbb{Z})$ for $k \geq 2$ . Hint: What is the order of $3$ in this group? Look at $(2+1)^n$ via the binomial theorem.

a. w. walker

mathematics and miscellany

A Generalization of Wilson’s Theorem (due to Gauss)

Leave a Reply Cancel reply

Share this:

Like this:

Leave a Reply Cancel reply