# The amount of $n$ so that $n!+1$ is divisible by $p$

Consider any prime number $$p$$ and sequence $$(n!+1)_{n=1}^{\infty}$$

How many elements from this sequence are divisible by p? Let's denote this number as $$f(p)$$

I know that $$f(p)$$ is finite since for all $$n\ge p$$ ; $$n!+1$$ is not divisible by $$p$$.

I also know that from Wilson theorem we have $$p|(p-1)!+1$$ so $$f(p)\ge1$$.

What is upper bound for $$f(p)$$?

Regards

• as you indicated, $f(p)\lt p$, but I suppose you'd like a tighter bound Feb 10, 2020 at 15:00
• Trying some examples: $f(2)=1$ ($n=1$); $f(3)=1$ ($n=2$); $f(5)=1$ ($n=4$); $f(7)=2$ ($n=3,6$); $f(11)=2$ ($n=5,10$); $f(13)=1$ ($n=12$); $f(17)=1$ ($n=16$); $f(19)=2$ ($n=9,18$);
– Paul
Feb 10, 2020 at 15:10

The residue classes modulo $$p$$ form a field and so, for $$p$$ odd, all the non-zero elements are in pairs of multiplicative inverses except for $$\pm1$$.
If we placed the numbers $$1,2, ... ,p-1$$ in the order :- $$1,p-1,a,a^{-1},b,b^{-1},c,c^{-1}, ...$$ then every other successive product of numbers from the left is $$-1$$.
No other ordering of the elements can do better than this and so an upper bound for $$f(p)$$ is given by $$\frac{p-1}{2}.$$
This bound is only achieved when $$p-1=2$$ i.e. $$p=3$$. For larger primes it takes several elements before $$1\times2\times3\times ...$$ reaches $$p-1$$ and then various pairs $$a,a^{-1}$$ have been 'lost' by one or other of the pair having been used. In practice therefore, the bound is typically much less than $$\frac{p-1}{2}.$$
An upper bound is $$f(p) \leq p - \sqrt{p-1}$$. The number of nonzero residue classes attained by $$n!$$ is at least $$\sqrt{p-1}$$; see among $1!,2!,...,p!$ there are at least $\sqrt{p}$ different residues in modulo $p$
So at least $$\sqrt{p-1} - 1$$ of the first $$p-1$$ residues of $$n!$$ are not $$-1$$.