Section 1.2.5: Permutations and Factorials

Exercise 14. ▶ [M28] (L. Stickelberger, 1890.) In the notation of exercise 12, we can determine $n! \bmod p$ in terms of the $p$-ary representation, for any positive integer $n$, thus generalizing Wilson's theorem. In fact, prove that

$$ \frac{n!}{p^\mu} \equiv (-1)^\mu a_0!a_1!\cdots a_k! \pmod p. $$

Verified: yes
Solve time: 13m59s

Setup

Let [ n=a_kp^k+a_{k-1}p^{k-1}+\cdots+a_1p+a_0, \qquad 0\le a_j<p,\quad a_k>0. ] For every nonnegative integer (N), write [ \mu(N)=\sum_{\ell>0}\left\lfloor\frac{N}{p^\ell}\right\rfloor, \qquad F(N)=\frac{N!}{p^{\mu(N)}}. ] By Eq. (8), (\mu(N)) is the multiplicity of (p) in (N!), so (F(N)) is an integer.

We use [ (p-1)!\equiv -1\pmod p. ] Indeed, the nonzero residues modulo (p) pair with their multiplicative inverses, except for (1) and (-1), whose product is (-1). This also holds for (p=2), since (1\equiv-1\pmod2).

Solution

Write [ n=qp+r,\qquad 0\le r<p, ] where (q=\lfloor n/p\rfloor). From Eq. (8), [ \mu(n) =q+\sum_{\ell>1}\left\lfloor\frac{n}{p^\ell}\right\rfloor =q+\sum_{\ell>0}\left\lfloor\frac{q}{p^\ell}\right\rfloor =q+\mu(q). ]

Separate the multiples of (p) in (n!). The multiples are (p,2p,\ldots,qp), whose product is (p^q q!). Hence [ n!=p^q q!,U(n), ] where [ U(n)=\prod_{\substack{1\le j\le n\p\nmid j}}j. ] Consequently, [ F(n)=U(n)F(q). ]

The nonmultiples of (p) occur in (q) complete blocks followed by a partial block: [ U(n) =\prod_{i=0}^{q-1}\prod_{s=1}^{p-1}(ip+s) \prod_{s=1}^{r}(qp+s). ] Reducing modulo (p) gives [ U(n) \equiv \bigl((p-1)!\bigr)^q r! \equiv (-1)^q r! \pmod p. ] The formula includes (q=0) and (r=0), using the empty-product convention and (0!=1). Therefore [ F(n)\equiv (-1)^q r!F(q)\pmod p. \tag{1} ]

Now set [ q_j=\left\lfloor\frac{n}{p^j}\right\rfloor. ] The (p)-ary representation gives [ q_j=pq_{j+1}+a_j\qquad(0\le j\le k), ] with (q_0=n) and (q_{k+1}=0). Applying (1) to (q_j) yields [ F(q_j)\equiv (-1)^{q_{j+1}}a_j!F(q_{j+1})\pmod p. ] Multiplying these congruences for (j=0,1,\ldots,k), and using (F(0)=1), gives [ F(n)\equiv (-1)^{q_1+q_2+\cdots+q_k} a_0!a_1!\cdots a_k! \pmod p. ] Since [ q_j=\left\lfloor\frac{n}{p^j}\right\rfloor, ] we have [ q_1+q_2+\cdots+q_k =\sum_{\ell>0}\left\lfloor\frac{n}{p^\ell}\right\rfloor =\mu. ] Thus [ \boxed{\frac{n!}{p^\mu}\equiv (-1)^\mu a_0!a_1!\cdots a_k!\pmod p}. ]

Verification

An independent verification groups the factors of (n!) according to their exact powers of (p). For (1\le i\le n), write [ i=p^{e(i)}u_i, \qquad p\nmid u_i. ] The sum of the exponents (e(i)) is (\mu), so [ \frac{n!}{p^\mu}=\prod_{i=1}^n u_i. ] For a fixed (t\ge0), the integers (i\le n) with (e(i)=t) have the form [ i=p^tm,\qquad 1\le m\le\left\lfloor\frac{n}{p^t}\right\rfloor,\quad p\nmid m. ] Therefore, with [ A(N)=\prod_{\substack{1\le m\le N\p\nmid m}}m, ] we obtain [ \frac{n!}{p^\mu}

\prod_{t\ge0}A\left(\left\lfloor\frac{n}{p^t}\right\rfloor\right). ] If (N=Qp+R), (0\le R<p), the same block decomposition gives [ A(N)\equiv (-1)^Q R!\pmod p. ] Taking (N=q_t=\lfloor n/p^t\rfloor), we have (Q=q_{t+1}) and (R=a_t). Hence [ \frac{n!}{p^\mu} \equiv \prod_{t=0}^k(-1)^{q_{t+1}}a_t!

(-1)^{\sum_{t\ge1}q_t}a_0!a_1!\cdots a_k! \pmod p, ] and (\sum_{t\ge1}q_t=\mu), confirming the result.

For the boundary case (n<p), we have (k=0), (\mu=0), and the congruence reduces to [ n!=a_0!, ] which is exact. When (r=0), the final partial block is empty and contributes (0!=1), so no extra factor is introduced. When (p=2), every (a_j) is (0) or (1), (a_j!=1), and the normalized factorial is odd, so both sides are (1\pmod2).

This completes the proof. ∎