Background: Several special classes of primes can be written as primes that satisfy some additional constraint $f(p)\equiv 0\pmod p$; for instance, Wilson primes are congruence primes with $f(p)=\dfrac{(p-1)!+1}{p}$ and Wieferich primes are congruence primes with $f(p) = \dfrac{2^{p-1}-1}{p}$. More recently, questions have come up on Math.SE and MathOverflow about primes satisfying similar congruence conditions with $\displaystyle f(p)=\sum_{i=1}^{p-1}i!$ and $\displaystyle f(p)=\sum_{i=1}^{p-1}i^i$, respectively. It makes sense (to me, at least) to generically call these congruence condition primes for the condition function $f()$. Assuming heuristically that $f(p)$ 'should be' equidistributed mod $p$ (and note that all of the above examples have $f(p)\gg p$ so that equidistribution is relatively plausible), then for some given condition $f()$ the number of congruence-condition primes less than $N$ should be approximately $\displaystyle\sum_{p\leq N}\frac1p\approx\log\log N$, and in particular their number should be infinite.

The other notable thing that all of the above examples have in common is that despite the heuristic arguments, none of them is known to be an infinite class of primes. What I'm wondering is whether there's any 'non-trivial' example of a congruence condition for which infinitely many primes are known to satisfy the condition; more specifically, an example where the heuristic arguments hold at least to the extent that $\#\{p\leq N: f(p)\equiv 0\}\in O(\log\log N)$ but where infinitude is specifically known. (The requirement here is meant to eliminate simple trivial-ish cases where e.g. all primes $\equiv 3\pmod 4$ satisfy the congruence or a member of a pair of twin primes satisfies the congruence; i.e., cases where the count is $\Theta(\dfrac N{\log^iN})$ for some $i$ rather than $O(\log \log N)$.)

  • 2
    $\begingroup$ Further (conjectural) examples include the Mirimanoff primes and Wolstenholme primes. While unrelated to congruence relations, I'd also like to point out the non-trivial existence of a certain class of primes that grows as $\log \log n$: the primes in the Mill's sequence. $\endgroup$ – awwalker May 29 '13 at 18:20
  • $\begingroup$ @AWalker thank you for the latter example; I'd been considering expanding the question to ask about any 'sparse' infinite sequences of primes but decided that might be going too far afield; the Mill's primes definitely answer that question, though. $\endgroup$ – Steven Stadnicki May 29 '13 at 18:25
  • 2
    $\begingroup$ In most of these situations, it is also not known if there are infinitely many primes not satisfying the congruence condition. $\endgroup$ – Julian Rosen Nov 16 '16 at 13:29

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.