Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
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

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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