factorial modulo prime powers

For n and any prime numberMathworldPlanetmath p, (n!)p is the productMathworldPlanetmathPlanetmath of numbers 1mn, where pm.

For natural numbersMathworldPlanetmath n,s and a given prime number p, we have the congruenceMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath


where Ni is the least non-negative residue of npi(modps). Here d+1 denotes the number of digits in the representation of n in base p. More precisely, ±1 is -1 unless p=2,s3.


Let i0. Then the set of numbers between 1 and npi is


This is true for every integer i with pi+1n. So we have

npi!npi+1pnpi+1=(npi!)p. (1)

Multiplying all terms with 0id, where d is the largest power of p not greater than n, the statement follows from the generalizationPlanetmathPlanetmath 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