0
$\begingroup$

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.

3 Answers 3

9

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.

  • 0
    Yes, a nice reasonably straightforward elementary argument, always preferable.2011-08-04
1

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.

1

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, 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$.)