Problem
Let $c \in \mathbb{N}$ $;$ $\exists$ a prime $p$ for which:
$$p^c \mid (p-1)!+1$$
Does $\exists$ $M$ $\in$ $\mathbb{N}$ $;$ $\forall$ $c \geqslant M$
$;$ $\nexists$ $p$ satisfying the above?
When $c$ = $1$
The statement is equivalent to Wilson's Theorem. For every prime $p$:
$$p \mid (p-1)!+1$$
Proof:
$\forall$ $x \in {1,2,…,p-1}$ $\exists!$ $ x' \in {1,2,…,p-1}$ ;
$x \cdot x'\equiv 1 \pmod{p}$
$x=x' \iff p \mid x^2-1 \iff x = 1, x=p-1$
$(p-1)! = 1 \cdot (p-1) \cdot \prod{(x \cdot x')} \equiv 1^n \cdot (p-1) \equiv p-1 \pmod{p}$
$\implies p \mid (p-1)!+1$
QED
When $c$ = $2$
We have the statement:
$$p^2 \mid (p-1)!+1$$
The only known primes that satisfy this are $5$, $13$ and $563$.
$(5-1)!+1 = 25 = 5^2$
$(13-1)!+1 = 479001601 = 13^2 \cdot 2834329$
$563^2 \mid (563-1)!+1 \approx 1.128 \cdot 10^{1303}$
Such primes $p$ are known as Wilson Primes. It is conjectured that there are infinitely many Wilson Primes. However, if there exists a fourth Wilson prime $p$, then $p>2 \cdot 10^{13}$.
When $c \geqslant 3$
There are no known primes for which $p^3 \mid (p-1)!+1$ as if there is, then $p$ also has to be a Wilson Prime.
$(5-1)!+1 = 25 \equiv 25 \pmod{5^3}$
$(13-1)!+1 = 479001601 \equiv 676 \pmod{13^3}$
$(563-1)!+1 \equiv 91921010 \pmod{563^3}$
It is most likely due to following evidence that there exists an upper bound $M$ for which:
$$c \geqslant M \implies p^c \nmid (p-1)!+1$$
where $M \geqslant 3$.
- We consider $(p-1)!+1 \pmod{p^c}$
- We assume that every remainder divisible by $p$ (Wilson's Theorem) is equally probable.
- Thus, the probability of required remainder $0$ is $\frac{1}{p^{c-1}}$
- Thus, probable number of primes for given constant $c$ is:
$$\sum{\frac{1}{p^{c-1}}} = P(c-1)$$
where $P(x)$ is the Prime Zeta Function
When $c=2$, the expected number of Wilson primes is $P(1)$.
$$P(1)=\sum{\frac{1}{p}}$$
This sum is divergent. Thus, it is probable that there exist infinitely many Wilson primes.
Proof:
Define $N(x)$ to be the number of positive integers $n \leqslant x$ for which $p_i \nmid n$, where $i > j$ for constant $j$ and $p_i$ is the $i$th smallest prime. Then, we write:
$$n=k^2m$$
where $m$ is square-free.
As $m$ is square-free, and the only primes that divide it are $p_i$ for $1 \leqslant i \leqslant j$, it has $2^j$ possibilities.
$n^2 \leqslant x \implies n \leqslant \sqrt{x}$, thus giving $n$ a maximum of $\sqrt{x}$ possibilities.
$$\implies N(x) \leqslant 2^j\sqrt{x}$$
Assume the contrary, then for some $j$:
$$\sum_{i=j+1}^\infty \frac{1}{p_i} < \frac{1}{2}$$
We also have $x-N(x)$ is the number of numbers less than or equal to $x$ divisible by one or more of $p_i$ for $i>j$.
$$x-N(x) \leqslant \sum_{i=j+1}^\infty \frac{x}{p_i} < \frac{x}{2}$$
$$\implies 2^j\sqrt{x} > \frac{x}{2}$$
which is untrue for $x \geqslant 2^{2j+2}$
Thus the sum diverges. The divergence is similar to $\log{\log{x}}$ (Which is very slow).
Probable Answer To Problem
When $c \geqslant 3$, the sum converges and is less than $1$.
When $c=3$, $P(c-1) \approx 0.45$
When $c=4$, $P(c-1) \approx 0.17$
When $c=5$, $P(c-1) \approx 0.07$
When $c=6$, $P(c-1) \approx 0.03$
When $c=7$, $P(c-1) \approx 0.002$
We now go on to show why there most probably exists a constant $M$ such as the one in the problem. Consider:
$$\sum_{i=3}^\infty P(i-1)$$
We have:
$$\sum_{i=3}^\infty P(i-1) < \sum{\frac{1}{n(n+1)}} = \sum{\biggl(\frac{1}{n}-\frac{1}{n+1}\biggl)} = 1$$
Thus, the probable sum of the number of primes that satisfy the statement for $c \geqslant 3$, including a prime $p$, $n-2$ times, if the maximum $c$ satisfied is $n$, is less than $1$. However, if the answer to the problem is false, then, the sum would be infinite.
Thus, it is highly unlikely for there to be a solution for $c \geqslant 3$ as the probable answer is less than $1$ but the actual answer would be a positive integer. However, it is almost impossible for the answer to the problem to be false, as the probable answer is less than $1$ but the actual answer would be infinite!
Any of the following:
- Any progress or insight
- Answers conditional on conjectures
- Polynomial or logarithmic non-trivial bounds on $M$
will be accepted and appreciated.
P.S. This question has been posted and answered in Math Overflow for the interested reader. Link:
https://mathoverflow.net/questions/311675/stronger-versions-of-wilsons-theorem
Best Answer
Posted as an answer as it is too long for a comment
Let it be some prime number $p$. It is known that the set of numbers $G=(Z/pZ)^x=\{1,2,\dots,p-1\}$ forms a group under multiplication; therefore, for each element $a$ of $G$, there is a unique multiplicative inverse $b$ in $G$ such that $ab\equiv 1\pmod p$. It is important to note that $1$ and $p-1$ are each one their own multiplicative inverse.
This implies that, if we take all the elements of $G$ in pairs $(a,b)$, each pair $(a_k,b_k)$ can be expressed as $c_{k}p+1$, where $c$ is some positive integer. And if we multiply them all, we get that $$(p-1)!=1(p-1)(c_1p+1)(c_2p+1)\dots(c_\left({\frac{p-1}{2}-1}\right)p+1)\equiv -1\pmod p$$
With this expression, it can be proved the conditional part of Wilson's theorem: if $p$ is some prime number, then $(p-1)!\equiv -1\pmod p$.
The existence of some $c_k=1$ is guaranteed for every odd prime number $p$ by the fact that $2b\equiv 1 \pmod p$ has the unique solution $b=\frac{p+1}{2}$ for every odd prime number $p$. As $2\left(\frac{p+1}{2}\right)=c_kp+1$, it follows that $c_k=1$ for the pair $(2,\frac{p+1}{2})$.
As a result, if we consider wlog the pair $(2,\frac{p+1}{2})$=$(a_1,b_1)$=$(c_{1}p+1)$, we have that
$$(p-1)!=1(p-1)(p+1)(c_2p+1)\dots(c_\left({\frac{p-1}{2}-1}\right)p+1)$$
$$(p-1)!=\left(p^2-1\right)\left((c_2p+1)(c_3p+1)\dots(c_\left({\frac{p-1}{2}-1}\right)p+1)\right)$$
If we consider the term $\left((c_2p+1)(c_3p+1)\dots(c_\left({\frac{p-1}{2}-1}\right)p+1)\right)$, it can be seen that it is of the form $p^{k}m+1$, where $k\geq 1$. Therefore, $$(p-1)!=\left(p^2-1\right)\left(p^{k}m+1\right)$$
Expanding the product, we get that $$(p-1)!=p^{k+2}m+p^2-p^{k}m-1=$$ $$(p-1)!=p^2\left(p^{k}m-p^{k-2}m+1\right)-1$$
Therefore, $$(p-1)!+1=p^2\left(p^{k}m-p^{k-2}m+1\right)$$
It follows that the term between brackets of the RHS is coprime to $p$, and thus $p^2$ is the maximum power possible dividing $(p-1)!+1$, unless $k=2$ and $p\mid m+1$.
Expanding the term $\left((c_2p+1)(c_3p+1)\dots(c_\left({\frac{p-1}{2}-1}\right)p+1)\right)$ it can be seen that $k=2$ only if $p\mid \sum_{i=2}^{\frac{p-1}{2}-1}c_i$, which constitutes a necessary condition for Wilson primes. However, proving that $p\nmid m+1$ for every prime number $p$ might be hard.