If $ \scriptstyle n $ is prime, then we know that $ \scriptstyle Z_n $ is a field, completely defined by $ \scriptstyle\{0,1,\ldots,n-1\} $, such that every element is a unit. In the product $ \scriptstyle (n-1)! $, by pairing up every element with its multiplicative inverse, we are left with those elements which are their own inverse. Namely, $ \scriptstyle1 $ and $ \scriptstyle n-1 $. So $ \scriptstyle(n-1)!\ mod\ n\ =\ 1\cdot(n-1)\ =\ n-1 $.
Consider the predicate $ \scriptstyle(n-1)!\ mod\ n\ =\ n-1 $ when $ \scriptstyle n $ is composite. One of the numbers $ \scriptstyle2,3,\ldots,n-1 $ must then divide $ \scriptstyle n $, and $ \scriptstyle(n-1)!\ mod\ n\ =\ 0 $, contradicting our initial assumption. It's clear that the condition is both necessary and sufficient. $ \scriptstyle\Box $
- --Nick Rupley 06:20, 2 April 2009 (UTC)
