11
$\begingroup$

This question is inspired by @Dan Brumleve's question on finding Pratt certificates efficiently. In a comment, I say that his problem is as hard as factoring, as long as the following problem is "easy" (i.e., can be solved in polynomial time):

Given $N > 2$, find a prime $p$ such that $p \equiv 1 \pmod{N} \tag{1}.$

(Of course, Dirichlet's theorem assures us that infinitely many such $p$ exist.)

Now, I do not know of a clever way to find such a $p$, so I suggested simply iterating through the arithmetic progression $1+kN$ for $k = 0, 1, 2, \ldots$, and terminating when we hit the first prime number. Clearly, this procedure is efficient if and only if the smallest prime $p$ satisfying $(1)$ is at most $N^{O(1)}$. (Edit: This claim is incorrect; see below.) I want to know if such a bound holds or not.

More generally,

Given an integer $N$, what upper bound do we know on the smallest prime satisfying $(1)$?

I did a quick check on Wikipedia and Mathworld, but cannot find any relevant results.

Edit: Turns out the claim in the question is false. The procedure will be efficient only if the smallest prime is $O(N \cdot\mathrm{poly}\log N)$, which seems very unlikely. In any case, I will just keep this question as it is, since it makes sense as a stand-alone question as well.

  • 0
    I apologize for the mistake (which is only tangentially related to this question anyway), and also not researching the topic properly. I overlooked the link to Linnik's theorem at the bottom of the wiki page.2011-09-05

2 Answers 2

12

The relevant results are found under the heading, Linnik's Theorem. Linnik proved that the least prime congruent to $a$ mod $d$ is at most $cd^L$ for some absolute constants $c$ and $L$. The current best bound is $L\le5.2$. On the Generalized Riemann Hypothesis, you can show there's a prime less than $(\phi(d)\log d)^2$, where that's Euler's phi-function. It is conjectured there's always a prime less than $d^2$.

  • 0
    @Peter, I don't know. I suppose one could chase through the literature on Linnik's Theorem to see. But since 5.2 is conjectured to be far from best possible for $L$, there may not be so much interest in pinning down a value for $c$.2015-10-14
6

Gerry Myerson has answered your main question, so I'll address the other part. I don't think that the claim is false, though certainly it's not proven. In any case I wouldn't say it's "very unlikely".

In fact it seems quite likely to me that the smallest k with $kn+1$ prime will be $O((\log n)^3)$ -- indeed, probably even $O((\log n)^2(\log\log n)^e)$ for some e.

Disregarding $n<20$, $e=0.18$ works up to 30 million with a constant of 1. A braver mathematician might conjecture that it holds for $e=0$ and a somewhat larger constant.

  • 0
    My apologies, it looks like the font makes it quite hard to distinguish between the $\varepsilon$ (epsilon) and the $e$ (e) in exponents. The only exponent with $e$ is the penultimate, $(\log\log n)^e.$2011-09-07