You are currently browsing the tag archive for the ‘Modular Arithmetic’ tag.

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.