# factorial modulo prime powers

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

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

$$\frac{n!}{{p}^{\sum _{i=0}^{d}\lfloor \frac{n}{{p}^{i}}\rfloor}}\equiv \prod _{i=0}^{d}\left({(\pm 1)}^{\lfloor \frac{n}{{p}^{s}+i}\rfloor}{\left({N}_{i}!\right)}_{p}\right)\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}^{s}),$$ |

where ${N}_{i}$ is the least non-negative residue of $\lfloor \frac{n}{{p}^{i}}\rfloor \phantom{\rule{veryverythickmathspace}{0ex}}(mod{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\ge 3$.

###### Proof.

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

$$\left\{kp,k\ge 1,k\le \lfloor \frac{n}{{p}^{i+1}}\rfloor \right\}.$$ |

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

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

Multiplying all terms with $0\le i\le 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 |
---|---|

Canonical name | FactorialModuloPrimePowers |

Date of creation | 2013-03-22 13:22:52 |

Last modified on | 2013-03-22 13:22:52 |

Owner | Thomas Heye (1234) |

Last modified by | Thomas Heye (1234) |

Numerical id | 7 |

Author | Thomas Heye (1234) |

Entry type | Result |

Classification | msc 11A07 |