# Wilson's Theorem/Corollary 2

## Theorem

Let $n \in \Z_{>0}$ be a (strictly) positive integer.

Let $p$ be a prime factor of $n!$ with multiplicity $\mu$.

Let $n$ be expressed in a base $p$ representation as:

\(\ds n\) | \(=\) | \(\ds \sum_{j \mathop = 0}^m a_j p^j\) | where $0 \le a_j < p$ | |||||||||||

\(\ds \) | \(=\) | \(\ds a_0 + a_1 p + a_2 p^2 + \cdots + a_m p^m\) | for some $m > 0$ |

Then:

- $\dfrac {n!} {p^\mu} \equiv \paren {-1}^\mu a_0! a_1! \dotsb a_m! \pmod p$

## Proof 1

Proof by induction:

Let $\map P n$ be the proposition:

- $\dfrac {n!} {p^\mu} \equiv \paren {-1}^\mu a_0! a_1! \dotsm a_k! \pmod p$

where $p, a_0, \dots, a_k, \mu$ are as defined above.

### Basis for the Induction

For $n = 1$:

- $a_0 = 1, \mu = 0$

$\map P 1$ reduces to:

- $\dfrac {1!} {p^0} \equiv \paren {-1}^0 1! \pmod p$

which holds trivially.

This is the basis for the induction.

### Induction Hypothesis

This is our induction hypothesis:

- $\dfrac {r!} {p^\mu} \equiv \paren {-1}^\mu a_0! a_1! \dots a_k! \pmod p$

Now we need to show true for $n = r + 1$:

- $\dfrac {\paren {r + 1}!} {p^{\mu'}} \equiv \paren {-1}^{\mu'} b_0! b_1! \dots b_k! \pmod p$

where $\ds r + 1 = \sum_{j \mathop = 0}^k b_j p^j$ is the base $p$ presentation of $r + 1$, and:

- $p^{\mu'} \divides \paren {r + 1}!$
- $p^{\mu' + 1} \nmid \paren {r + 1}!$

### Induction Step

This is our induction step:

Let $p^m$ be the largest power of $p$ which divides $r + 1$, that is:

- $p^m \divides r + 1$
- $p^{m + 1} \nmid r + 1$

Then we must have:

- $b_m \ne 0$
- $b_j = 0$ for $0 \le j < m$
- $\mu' = \mu + m$

and consequently:

- $a_j = b_j$ for $j > m$
- $a_m + 1 = b_m$
- $a_j = p - 1$ for $0 \le j < m$

Thus:

\(\ds \frac {\paren {r + 1}!} {p^{\mu'} }\) | \(=\) | \(\ds \frac {r!} {p^\mu} \times \frac {r + 1} {p^m}\) | ||||||||||||

\(\ds \) | \(\equiv\) | \(\ds \paren {-1}^\mu a_0! \dots a_{m - 1}! a_m! \dots a_k! \times \frac {r + 1} {p^m}\) | \(\ds \pmod p\) | Induction Hypothesis | ||||||||||

\(\ds \) | \(\equiv\) | \(\ds \paren {-1}^\mu \paren {\paren {p - 1}!}^m \paren {b_m - 1}! b_{m + 1}! \dots b_k! \times \frac 1 {p^m} \sum_{j \mathop = m}^k b_j p^j\) | \(\ds \pmod p\) | from above | ||||||||||

\(\ds \) | \(\equiv\) | \(\ds \paren {-1}^\mu \paren {-1}^m \paren {b_m - 1}! b_{m + 1}! \dots b_k! \times \sum_{j \mathop = m}^k b_j p^{j - m}\) | \(\ds \pmod p\) | Wilson's Theorem | ||||||||||

\(\ds \) | \(\equiv\) | \(\ds \paren {-1}^{\mu'} \paren {b_m - 1}! b_{m + 1}! \dots b_k! b_m\) | \(\ds \pmod p\) | because $b_j p^{j - m} \equiv 0 \pmod p$ for $j - m > 0$ | ||||||||||

\(\ds \) | \(\equiv\) | \(\ds \paren {-1}^{\mu'} b_m! b_{m + 1}! \dots b_k!\) | \(\ds \pmod p\) | Definition of Factorial | ||||||||||

\(\ds \) | \(\equiv\) | \(\ds \paren {-1}^{\mu'} b_0! \dots b_k!\) | \(\ds \pmod p\) | Factorial of Zero: $b_j = 0$ for $0 \le j < m$ |

By the Principle of Mathematical Induction, $\map P n$ is true for all $n \in \Z_{>0}$.

$\blacksquare$

## Proof 2

Consider the numbers of $\set {1, 2, \ldots, n}$ which are not multiples of $p$.

There are $\floor {\dfrac n p}$ complete sets of $p - 1$ such consecutive elements of $\set {1, 2, \ldots, n}$.

Each one of these has a product which is congruent to $-1 \pmod p$ by Wilson's Theorem.

There are also $a_0$ left over which are congruent to $a_0! \pmod p$.

Thus:

- the contributions of the divisors which are not multiples of $p$ is $\paren {-1}^{\floor {n / p} } a_0!$

- the contributions of the divisors which are multiples of $p$ is the same as the contribution in $\floor {\dfrac n p}!$

Thus the argument can be repeated on $\floor {\dfrac n p}!$ until the formula is complete.

$\blacksquare$

## Historical Note

This corollary to Wilson's theorem was demonstrated, according to Donald E. Knuth: *The Art of Computer Programming: Volume 1: Fundamental Algorithms* (3rd ed.), by Ludwig Stickelberger in $1890$.

It is supposed that this appears in Stickelberger's $1890$ article *Ueber eine Verallgemeinerung der Kreistheilung* (*Math. Ann.* **Vol. 37**: pp. 321 – 367) during the course of his proof of Stickelberger's Theorem.

However, not only is the latter behind a paywall, it is also in a language the author of this page is not fluent in, and he has been disinclined to study it.