15
$\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 is also in Mathematics Stack Exchange. Link: https://math.stackexchange.com/questions/2651733/stronger-versions-of-wilsons-theorem

$\endgroup$
  • 2
    $\begingroup$ I don't know what you mean by "moved from Mathematics Stack Exchange". The question is still there, math.stackexchange.com/questions/2651733/… and indeed it has an active 100-point bounty. $\endgroup$ – Gerry Myerson Sep 29 '18 at 12:58
  • $\begingroup$ Yeah, moved as in not literally, it is still there too $\endgroup$ – Haran Sep 29 '18 at 12:59
  • 1
    $\begingroup$ I will be placing a bounty for this question in 2 days here too $\endgroup$ – Haran Sep 29 '18 at 13:00
  • 6
    $\begingroup$ Thank you for showing your work. For MathOverflow, a different style is preferred, preferably a brief summary of what you want and what you know. Much of what you prove is known to number theory students in this community. What might be of interest are computational statistics bearing (or refuting) a key assumption. Can you speak to the following: How is (p-1)! actually distributed mod p^2 as p ranges over primes? Can you find a paper which approaches this question? Gerhard "Try Breaking The Problem Down" Paseman, 2018.09.29. $\endgroup$ – Gerhard Paseman Sep 29 '18 at 15:29
  • 5
    $\begingroup$ A naive application of the abc conjecture gives $v_p((p-1)!+1)=o(p)$. $\endgroup$ – Dror Speiser Sep 30 '18 at 15:57
9
$\begingroup$

The question is not trivial, and to my knowledge the answer is not known: there is no known uniform upper bound for the $p$-adic valuation of $(p-1)!+1$ (although such a bound most probably exists, as you indicate).

The only result I know in this direction is that $(p-1)!+1$ is not a power of $p$ for any $p>5$, see e.g. this link. EDIT. I have in my notes that this result is due to Liouville, but I cannot find the precise reference.

This does provide an upper bound for the $p$-adic valuation, although a very weak one. A natural problem would be to improve this bound, but a uniform upper bound may be out of reach given current technology.

$\endgroup$
  • $\begingroup$ I am aware that this question is not trivial. However, is it possible for you to show that it is out of reach for now, by linking it with any unsolved problem or conjecture? Also, could you show your $p$-adic valuation. It is alright even if it is a weak bound. Do edit your post to add these two replies. $\endgroup$ – Haran Sep 30 '18 at 18:19
  • $\begingroup$ @Haran I'm not aware of any result of the type "this would imply some well-known conjecture" and I doubt there is any. The links are rather in the opposite direction, see Prof. Silverman's theorem on non-Wieferich primes assuming the ABC conjecture, or Dror Speiser's comment for Wilson primes. The bound on $\alpha=v_p(N)$ with $N=(p-1)!+1$ is simply $p^\alpha \leq N/(p+2)$ since $N$ must have a prime factor $>p$. Nothing more, but still better than the trivial bound $p^\alpha \leq N$. $\endgroup$ – François Brunault Sep 30 '18 at 19:44
  • $\begingroup$ Oh, you mean that. True, that is a very weak bound. However, you can make it a little stronger. If $p^{\alpha}(p+k) = (p-1)!+1$, then $p^{\alpha +1}-1=(p-1)!-p^{\alpha}k$. Thus, $p-1$ divides LHS and will have to divide $p^{\alpha}k$, which implies that $p-1 \mid k$ and thus, $k \geqslant p-1$. Also, for $p > 5, (p+2)^2 > (p+p-1) = 2p-1$. Thus, $p^{\alpha} \leqslant \frac{N}{2p-1} \implies \alpha \leqslant \log_ {p}{\frac{N}{2p-1}}$, where $N = (p-1)!+1$. $\endgroup$ – Haran Oct 1 '18 at 5:59
  • $\begingroup$ With the same kind of techniques, one can show for example that if $(p-1)!+1 = p \cdot q^\alpha$ with $p,q$ primes and $q>p \geq 7$, then in fact $q \geq 6p-1$. But this is still very far from what is expected. $\endgroup$ – François Brunault Oct 1 '18 at 10:29
  • $\begingroup$ Do you mean $p \cdot q^{\alpha}$ or $p^{\alpha} \cdot q$ ? $\endgroup$ – Haran Oct 1 '18 at 15:59
9
+50
$\begingroup$

Short expansion of my comment on what's immediately achievable when assuming the $abc$-conjecture.

Proporistion. Assuming the $abc$-conjecture, we have $$v_p((p-1)!+1)=o(p).$$

Proof. One formulation of the $abc$-conjecture goes as follows (straight from Wikipedia):

ABC conjecture. For every positive real number $\varepsilon$, there is a constant $K_\varepsilon$ such that for all triples $(a, b, c)$ of coprime positive integers, with $a+b=c$: $$c < K_\varepsilon\cdot \text{rad}(abc)^{1+\varepsilon}.$$

Set $a=(p-1)!$, $b=1$, and $c=a+b=p^{v_p((p-1)!+1)}c'$, where $p\not|c'$. Fix a positive real number $\varepsilon$. Then, assuming the $abc$-conjecture, there exists a constant $K_\varepsilon$ such that

\begin{align} p^{v_p((p-1)!+1)}c'<&\ K_\varepsilon\cdot\text{rad}((p-1)!p^{v_p((p-1)!+1)}c')^{1+\varepsilon}\\ =&\ K_\varepsilon\cdot(p\cdot\text{rad}(c')\prod_{q\lt p}q)^{1+\varepsilon}\\ <&\ K_\varepsilon\cdot(c'\prod_{q\le p}q)^{1+\varepsilon}\\ \Rightarrow p^{v_p((p-1)!+1)}<&\ K_\varepsilon\cdot c'^\varepsilon(\prod_{q\le p} q)^{1+\varepsilon}\\ =&\ K_\varepsilon \cdot \big(\frac{(p-1)!+1}{p^{v_p((p-1)!+1)}}\big)^\varepsilon(\prod_{q\le p}q)^{1+\varepsilon}\\ \Rightarrow p^{(1+\varepsilon)v_p((p-1)!+1)}<&\ K_\varepsilon \cdot ((p-1)! + 1)^\varepsilon(\prod_{q\le p}q)^{1+\varepsilon}. \end{align}

We now take logs on both sides, and apply Stirling's Formula and the Prime Number Theorem:

\begin{align} (1+\varepsilon)v_p((p-1)!+1)\log{p}<&\ \varepsilon p\log{p} + O(p) + (1+\varepsilon)(p+o(p))\\ \Rightarrow v_p((p-1)!+1) <&\ \varepsilon p + o(p). \end{align}

Since this is true for all positive real numbers $\varepsilon$, we get the proposition.

$\endgroup$
5
$\begingroup$

For the $c=2$ case, if the expected number of Wilson primes less than $x$ is estimated as $\sum_{p \lt x}\frac1p$, then one would conjecture infinitely many such primes. However that series diverges quite slowly so one might not expect the simplest search idea to yield many (if any) new ones in our lifetime. At any rate, one would want to know when that series exceeds passes each integer. That sequence starts $$5, 277, 5195977, 1801241230056600523.$$

$\endgroup$
  • 1
    $\begingroup$ Thank you for the input. This actually gives a visual presentation of the huge gaps between Wilson Primes. $\endgroup$ – Haran Sep 30 '18 at 18:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.