factorial modulo prime powers
For n∈ℕ and any prime number p, (n!)p is the product
of numbers 1≤m≤n, where p|̸.
For natural numbers and a given prime number , we have the congruence
where is the least non-negative residue of . Here denotes the number of digits in the representation of in base . More precisely, is unless .
Proof.
Let . Then the set of numbers between 1 and is
This is true for every integer with . So we have
(1) |
Multiplying all terms with , where is the largest power of
not greater than , 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 |