|
|
|
|
factorial modulo prime powers
|
(Result)
|
|
|
For $n \in \mathbb{N}$ and any prime number $p$ , $\pfac{n}$ is the product of numbers $1 \le m \le n$ , where $p \not\vert m$ .
For natural numbers $n, s$ and a given prime number $p$ , we have the congruence
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 \ge 3$ .
Proof. Let $i \ge 0$ . Then the set of numbers between 1 and $\left\lfloor \frac{n}{p^i}\right\rfloor$ is $$\left\{kp, k \ge 1, k \le \left\lfloor\frac{n}{p^{i+1}}\right\rfloor\right\}$$ This is true for every integer $i$ with $p^{i+1} \le n$ . So we have \begin{equation} \label{F1} \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}} =\pfac{\left\lfloor\frac{n}{p^i}\right\rfloor}. \end{equation}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. 
|
"factorial modulo prime powers" is owned by Thomas Heye.
|
|
(view preamble | get metadata)
Cross-references: Anton's congruence, terms, integer, base, representation, digits, residue, congruence, natural numbers, numbers, product, prime number
This is version 4 of factorial modulo prime powers, born on 2003-01-23, modified 2004-04-01.
Object id is 3915, canonical name is FactorialModulePrimePowers.
Accessed 3061 times total.
Classification:
| AMS MSC: | 11A07 (Number theory :: Elementary number theory :: Congruences; primitive roots; residue systems) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|