# Wilson's Theorem/Corollary 2/Proof 2

Jump to navigation
Jump to search

## 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

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$

## Sources

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.5$: Permutations and Factorials: Exercise $14$