# Do there exist any dormant primes?

Suppose that n is an integer > 1 such that:

1. The prime factorization of n is known

2. It is known that (n + 1) is a prime

Then: What can be concluded?

Among the possibilities are the following:

1. We can predict, at least with some non-trivial probability, the distance to the next prime after (n + 1).

2. We can bound away from 0 the ratio (w – t)/w, where w is the number of primes less than n and t is the number of those primes not appearing in the prime factorization of n (the idea being that if there are relatively many of them, then at least one of them would wind up being a divisor of (n + 1)).

Possibility #2 above suggests the following definition: A prime p is said to be dormant fif there exist infinitely many positive integers n such that p < n, p does not divide n, and (n + 1) is prime. Do there exist any dormant primes? This specific question sounds more interesting than the general question stated above, and so I have given this question as the title of this post.

-

The fact that all odd primes are dormant is much easier to prove than Dirichlet's theorem. Let $q$ be an odd prime and suppose by contradiction that there are only finitely many primes $p_1, ... p_n$ such that $p_i \not \equiv 1 \bmod q$. Then

$$q p_1 p_2 ... p_n - 1 \not \equiv 1 \bmod q$$

so at least one of its prime factors, which cannot be one of the $p_i$, is not congruent to $1 \bmod q$. This is a straightforward generalization of Euclid's proof of the infinitude of the primes, and more generally we can prove the following.

Proposition: Let $G$ be a proper subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$. There exist infinitely many primes $p$ such that $p \bmod n$ does not lie in $G$.

In particular, for $q$ an odd prime there exist infinitely many primes $p$ such that $p \bmod q$ is not a quadratic residue. On MO I asked a question about exactly how far this argument can be pushed.

-
Yes, a nice reasonably straightforward elementary argument, always preferable. –  Geoff Robinson Aug 4 '11 at 23:41
@Qiaochu Yuan: Thanks. I've up-voted, and accepted your excellent answer. –  Mike Jones Aug 5 '11 at 22:04

I think that all odd primes are dormant according to that definition. For any odd prime $p$, there are infinitely many primes of the form $kp+2$ ($k \in \mathbb{N}$), by a particular case of a theorem of Dirichlet.

-

An equivalent definition: a prime $p$ is dormant if there exist infinitely many primes $q$ such that $p$ doesn't divide $q-1$. In other words, infinitely many primes $q$ such that $q\not\equiv 1 \pmod p$. This is a trivial corollary of Dirichlet's theorem of primes in arithmetic progressions. Pick any number $1<r<p$, and it follows that the natural density of primes $q$ such that $q\equiv r \pmod p$ is $1/\phi(p)=1/(p-1)$. (EDIT: as Geoff says, this doesn't hold for $p=2$.)

-