# factorial modulo prime powers

For $n\in\mathbb{N}$ and any prime number $p$, $\left(n!\right)_{p}$ is the product of numbers $1\leq m\leq n$, where $p\not|m$.

For natural numbers $n,s$ and a given prime number $p$, we have the congruence

 $\frac{n!}{p^{\sum\limits_{i=0}^{d}\left\lfloor\frac{n}{p^{i}}\right\rfloor}}% \equiv\prod\limits_{i=0}^{d}\left((\pm 1)^{\left\lfloor\frac{n}{p^{s}+i}\right% \rfloor}\left(N_{i}!\right)_{p}\right)\pmod{p^{s}},$

where $N_{i}$ is the least non-negative residue of $\left\lfloor\frac{n}{p^{i}}\right\rfloor\pmod{p^{s}}$. Here $d+1$ denotes the number of digits in the representation of $n$ in base $p$. More precisely, $\pm 1$ is $-1$ unless $p=2,s\geq 3$.

###### Proof.

Let $i\geq 0$. Then the set of numbers between 1 and $\left\lfloor\frac{n}{p^{i}}\right\rfloor$ is

 $\left\{kp,k\geq 1,k\leq\left\lfloor\frac{n}{p^{i+1}}\right\rfloor\right\}.$

This is true for every integer $i$ with $p^{i+1}\leq n$. So we have

 $\frac{\left\lfloor\frac{n}{p^{i}}\right\rfloor!}{\left\lfloor\frac{n}{p^{i+1}}% \right\rfloor p^{\left\lfloor\frac{n}{p^{i+1}}\right\rfloor}}=\left(\left% \lfloor\frac{n}{p^{i}}\right\rfloor!\right)_{p}.$ (1)

Multiplying all terms with $0\leq i\leq d$, where $d$ is the largest power of $p$ not greater than $n$, the statement follows from the generalization of Anton’s congruence. ∎

Title factorial modulo prime powers FactorialModuloPrimePowers 2013-03-22 13:22:52 2013-03-22 13:22:52 Thomas Heye (1234) Thomas Heye (1234) 7 Thomas Heye (1234) Result msc 11A07