← All problems

Erdős Problem #478 — Factorial residues modulo primes

46 years old · traced to

For each prime pp, let Fp\mathbb F_p be the field with pp elements and define the set of factorial residues

Ap={k! mod p:1≤k<p}⊆Fp×.A_p=\{k!\bmod p:1\leq k<p\}\subseteq\mathbb F_p^\times.

Is it true, as pp tends to infinity through the primes, that

lim⁡p→∞∣Ap∣p=1−1e,\lim_{p\to\infty}\frac{|A_p|}{p}=1-\frac1e,

equivalently, that ∣Ap∣∼(1−e−1)p|A_p|\sim(1-e^{-1})p? Erdős Problem #478 Factorial Residues Modulo a Prime: Beyond the Square-Root Bound

Background

Erdős and Graham posed the question in their 1980 book. The constant 1−e−11-e^{-1} is suggested by an occupancy heuristic: if the p−1p-1 factorials behaved like independent uniform choices from pp residues, the expected number of residues hit would be p(1−(1−1/p)p−1)∼(1−e−1)pp\bigl(1-(1-1/p)^{p-1}\bigr)\sim(1-e^{-1})p. This models the proposed density but does not account for the dependencies among factorial residues. Erdős Problem #478 Factorial Residues Modulo a Prime: Beyond the Square-Root Bound

A basic source of information is the ratio of consecutive factorials: (k+1)!/k!=k+1(k+1)!/k!=k+1 in Fp×\mathbb F_p^\times. Together with 1∈Ap1\in A_p, this gives Ap/Ap=Fp×A_p/A_p=\mathbb F_p^\times, and hence ∣Ap∣≥p−1|A_p|\geq\sqrt{p-1}. Wilson's theorem also gives (p−2)!≡1(modp)(p-2)!\equiv1\pmod p. For p≥5p\geq5, this repeats the value 1!=11!=1 at a distinct index, so ∣Ap∣≤p−2|A_p|\leq p-2; this bound does not hold for p=3p=3, where ∣A3∣=2|A_3|=2. Erdős Problem #478 Factorial Residues Modulo a Prime: Beyond the Square-Root Bound

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.