PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Low Entry average rating: No information on entry rating
[parent] 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

$\displaystyle \frac{n!}{p^{\sum\limits_{i=0}^d \left\lfloor \frac{n}{p^i}\right... ...eft\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 \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. $ \qedsymbol$




"factorial modulo prime powers" is owned by Thomas Heye.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

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 MSC11A07 (Number theory :: Elementary number theory :: Congruences; primitive roots; residue systems)

Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)