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

wilson_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 2Hint: What is the order of 3 in this group? Look at (2+1)^n via the binomial theorem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s