Editing Wilson's theorem (section)

===Composite modulus===
Suppose that <math>n</math> is composite.  Therefore, it is divisible by some prime number <math>q</math> where <math>2 \leq q < n</math>. Because <math>q</math> divides <math>n</math>, there is an integer <math>k</math> such that <math>n = qk</math>. Suppose for the sake of contradiction that <math>(n-1)! </math> were congruent to <math>-1</math> modulo <math>{n}</math>. Then <math>(n-1)!</math> would also be congruent to <math>-1</math> modulo <math>{q}</math>: indeed, if <math>(n-1)! \equiv -1 \pmod{n}</math> then <math>(n-1)! = nm - 1 = (qk)m - 1 = q(km) - 1</math> for some integer <math>m</math>, and consequently <math>(n-1)!</math> is one less than a multiple of <math>q</math>.  On the other hand, since <math>2 \leq q \leq n - 1</math>, one of the factors in the expanded product <math>(n - 1)! = (n - 1) \times (n - 2) \times \cdots \times 2 \times 1</math> is <math>q</math>.  Therefore <math>(n - 1)! \equiv 0 \pmod{q}</math>.  This is a contradiction; therefore it is not possible that <math>(n - 1)! \equiv -1\pmod{n}</math> when <math>n</math> is composite.

In fact, more is true. With the sole exception of the case <math>n = 4</math>, where <math>3! = 6 \equiv 2 \pmod{4}</math>, if <math>n</math> is composite then <math>(n - 1)!</math> is congruent to 0 modulo <math>n</math>. The proof can be divided into two cases: First, if <math>n</math> can be factored as the product of two unequal numbers, <math>n = ab</math>, where <math>2 \leq a < b < n</math>, then both <math>a</math> and <math>b</math> will appear as factors in the product <math>(n - 1)! = (n - 1)\times (n - 2) \times \cdots \times 2 \times 1</math> and so <math>(n - 1)!</math> is divisible by <math>ab = n</math>.  If <math>n</math> has no such factorization, then it must be the square of some prime <math>q</math> larger than 2. But then <math>2q < q^2 = n</math>, so both <math>q</math> and <math>2q</math> will be factors of <math>(n-1)!</math>, and so <math>n</math> divides <math>(n-1)!</math> in this case, as well.