factorial modulo prime powers
For and any prime number , is the product
of numbers , where .
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 representationof 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 ofAnton’s congruence.∎