# How does the probability of a number being prime increase, if its factors have the form $km+1$?

The "probability" that a number $n$ is prime, is roughly $\frac{1}{\ln(n)}$.

How does this probability increase, if it is known, that the prime factors must have the form $km+1$ for some given $m\in \mathbb N$ ?

Motivation : I wonder, how likely the generalized fermat numbers $b^{2^l}+1\ ,\ b\ even\$ are prime. It is known that the factors of such a number must have the form $2^{l+1}k+1$. This should increase the probability of being prime, but I have no idea of the magnitude of the increase.

• i've checked numbers smaller than $N = 1000000$ and the "probability" of being prime gets multiplied by $6.2$ when you restrict to numbers whose prime factors are congruent to $1$mod $3$. This factor tends to increase slowly as $N$ gets larger. – mercio Sep 30 '15 at 12:44
• Why did you ask this question without at least linking to this one? I would have thought that my answer there goes a long way towards answering this question, and at least is relevant enough that it should be linked to avoid unnecessary duplication of efforts. – joriki Sep 30 '15 at 13:56

Let $S_m$ be the set of integers whose prime factors are all congruent to $1$ mod $m$. We know from the Prime Number Theorem for Arithmetic Progressions, as described in Julián's answer, that

$$\# \{ p \le x : p \in S_m, p \text{ prime} \} = c_m \frac{x}{\log x} + O_m\big(\frac{x}{\log^2 x}\big),$$

where $c_m = 1/\phi(m)$. To answer the question, we only need an asymptotic for the counting function of $S_m$. Since $S_m$ excludes a fraction of $(1-c_m)$ of all primes, one expects heuristically that $$\# \{ n \le x : n \in S_m \} \asymp \frac{x}{(\log x)^{1-c_m}},$$ and in fact it can be obtained rigorously by a theorem of Odoni that the following precise asymptotic holds: $$\# \{ n \le x : n \in S_m \} = D_m x(\log x)^{c_m-1} + O_m(x(\log x)^{c_m-2+\epsilon}),$$ where $D_m > 0$ is given by a certain convergent Euler product. Specifically, if $\chi_m(p)$ is the indicator function of $\{ p : p \equiv 1 \pmod m\}$, then $$D_m = \frac{1}{\Gamma(c_m)} \prod_{p} \big(1 - \frac1p\big)^{c_m-\chi_m(p)}.$$ The "probability" you're seeking is just the ratio of primes to all numbers in $S_m$ up to $x$, namely $$\frac{c_m}{D_m (\log x)^{c_m}}.$$

I think in this case, the $\epsilon$ in the error term can be removed by applying the Selberg-Delange method, but I haven't checked the details (see, for instance, this paper).

However, as pointed out in Aravind's answer, even though this is provable, it still only amounts to a heuristic when you try to apply it to much thinner sets such as $\{n^2+1\}$ or $\{2^{2^n}+1\}$ that are not defined purely in terms of the prime composition.

I believe this question is impossible to answer in general and very hard for even simple instances.

Firstly, we are looking at a set $S$ of numbers such that all prime factors of numbers in $S$ are of the form $km+1$. The question is about the fraction of primes in $S$ among the first $n$ numbers in $S$.

It is not clear why this function should be greater than $\frac{1}{\log n}$ or indeed how we can say anything about it for arbitrary $S$. If we choose $S$ as a subset of the composites, then the probability is zero, while we could make it 1 by choosing $S$ to be a subset of the primes.

Also consider the example $S=\{n^2+1: n \in \mathbb{N}, \text{ n even}\}$. We know that all prime factors must be of the form $4k+1$, but clearly this is not sufficient information; we don't even know if the probability is positive!

The same is true for any set $S$ for which whether it has infinitely many primes is itself open, such as the set of Fermat numbers.

• Not sure the example is particularly relevant. We don't know the number of primes in $\{n^2+1\}$, but we certainly know the number of primes in $\{n : p \mid n \implies p \equiv 1 \pmod 4\}$, and we also know the counting function of the latter set. – Erick Wong Sep 30 '15 at 14:00

The probability that a number smaller than $n$ of the form $k\,m+1$ is prime is of the order of $$\frac{m}{\phi(m)}\,\frac{1}{\log N}\ .$$ This is an upper bound on the probability you are looking for. To get a better estimate you would need to know the number of integers less than $n$ all whose factors are $\equiv1\mod m$.