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|̸m$.

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)(mod{p}^s),$$

where $N_i$ is the least non-negative residue of $\lfloor \frac{n}{p^i}\rfloor (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