22
$\begingroup$

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 in Math Overflow. Link: https://mathoverflow.net/questions/311675/stronger-versions-of-wilsons-theorem

$\endgroup$
  • 3
    $\begingroup$ Please, use MathJax (i.e. LaTeX commands) for mathematical notations. $\endgroup$ – Taroccoesbrocco Feb 15 '18 at 14:13
  • 6
    $\begingroup$ related : "Double Wilson primes" - do they exist? $\endgroup$ – mathlove Sep 19 '18 at 15:04
  • 3
    $\begingroup$ Why are you adding over all $c \ge 3$??? Can't you just deduce the finiteness of the sum for $c=3$ and be done? $\endgroup$ – mathworker21 Sep 19 '18 at 17:49
  • 4
    $\begingroup$ @DietrichBurde it is definitely an open problem since it is open for $c=2$ $\endgroup$ – mathworker21 Sep 19 '18 at 17:54
  • 3
    $\begingroup$ Please read the actual problem. It is about whether there exists an upper bound $M$. Even if $M=10^{10^{10}}$, the problem is solved. One just needs to show its existence, if not even its value, however big. This is hence a weaker problem, which is especially portrayed in the last part by probability using prime zeta function. $\endgroup$ – Haran Sep 19 '18 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.