Half of Wilson’s Theorem

Let n be a natural number. Prove that if (n-1)! \equiv -1 \mod n, then n is prime.

Suppose n is composite; say n = p_1p_2 \cdots p_k, where the p_i are pairwise coprime and greater than 1. (Say each p_i is the highest power of some prime dividing n.) If k \geq 2, each of the p_i is represented in the set \{1,2,\ldots,n-1\}. Thus we have (n-1)! \equiv 0 \mod n. If on the other hand n = q^t is a prime power, and t \geq 3, then q and q^{t-1} are in the set \{1,2,\ldots,n-1\}, so that (n-1)! \equiv 0. If n = q^2 and q > 2, then q,2q \in \{1,2,\ldots,n-1\}, and (n-1)! \equiv 0 \mod n. If n = 4, then (4-1)! = 6 \equiv 2 \mod 4.

So n must be prime.

Post a comment or leave a trackback: Trackback URL.

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

%d bloggers like this: