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 is prime if and only if
(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 is prime. Then each of the nonzero residues modulo is a unit, so that represents the product over all units in . If
, i.e. ,
then and its inverse each show up in our list of units. We cancel out such terms in pairs, and conclude that
We have if and only if , which by primality of forces or . In other words, . It follows that
When is composite, the direct translation of Wilson’s problem gives
The problem, here, is that we’ve multiplied a number of zero divisors together, which can be avoided by only multiplying across the units, , of . In this post, we consider the product
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 a cyclic group?
It turns out that is cyclic if and only if takes one of the following forms:
for an odd prime and . (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 is cyclic, we have a cute proof of Wilson’s Theorem that extends beyond the case prime:
Theorem: If is cyclic, then
Proof: If is cylic, it admits a generator . Since generates all of , we have
We recall that if and only if . In the case above, this divisibility condition amounts to whether or not is even, ie. if is odd. This fails except in the case , whereby we see that the product in question cannot be .
On the other hand, it is clear that our product is a square root of . (Just look at the expression at right in the line above.) But a cyclic group only admits two square roots of (again, think about generators), so our product over the units must be the other square root of , ie. .
— GAUSS’ GENERALIZATION TO ACYCLIC GROUPS —
Question: What about when is not cyclic?
This first occurs in the case , in which we calculate
The next case is , which gives
It’s not too hard to prove that the product over the units in should be a square root of . Unfortunately, this doesn’t pin down our answer very much in general. For example, every unit in is a square root of , and the same holds for , 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 is if is cyclic. Otherwise, this product is .
Proof: Our proof begins with the fundamental theorem of finite abelian groups. If as a factored product of distinct primes, then
It follows that
For , let be a generator of . Let denote the elements of the acyclic group . We check that the product over all units is thus
These powers of will vanish under the assumption that
which is met if and only if is even. This occurs so long as has a prime factor or a factor of with multiplicity at least . In other words, this occurs whenever is not cyclic. When is not cyclic, the product over all units in may therefore be written
It thus suffices to show our claim in the case , with . That is, that
We leave it as an Exercise that . If we let and represent generators for these two subgroups, respectively, then the product over units in may be written
Since is acyclic, it has exponent strictly less than its order, . Thus the exponent divides , hence the product above is , which completes our proof.
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 , an arbitrary finite abelian group. In this case, our Theorem takes the following form:
Theorem: If has a unique element of order , then the product over the elements in is exactly . Otherwise, this product is .
Proof: Recall that in our very first proof of Wilson’s Theorem, we have characterized this product as the product over all elements in of order exactly . If there is a unique such element, say , the product over all elements in is clearly .
The “otherwise” claim is far more interesting. Note that the elements of with order at most form a subgroup, which — by the structure theorem of finite abelian groups — is necessarily isomorphic to for some integer . Fixing generators for these components, we recognize the product over as
in which we’ve used that the exponent of is .
Remark — To recover our earlier results from this very general theorem, we need only prove that has a unique element of order if and only if is cyclic. This follows from the classification of cyclic unit groups 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 -Sylow subgroups of the symmetric group .
Exercise: Deduce Wilson’s Theorem from Burnside’s Lemma by considering the following group action: cyclic permutation of the set of -cycles in .
Exercise: Prove that for . Hint: What is the order of in this group? Look at via the binomial theorem.