Let $q>2$ be a prime, and let $p(a,q)$ denote the least prime in arithmetic progression
$$a+nq,$$ where $n$ runs through the positive integers.
It is conjectured that $p(1,q)\le q(q+1)+1$.
Research suggests that the above statement is related to Linnik's theorem, albeit a special case.
How would one go about determining if this conjecture is valid/interesting or not and where would one start to prove this true or false and would proving something like this in any way help to decrease the bound of $L$ in Linnik's Theorem?
Background:
The Pocklington Criterion can be used to prove the primality of an integer $N$, given a partial factorization of $N-1$, specifically given that $N-1$ has a prime factor $q>\sqrt{N}-1$.
For a given odd prime $q$, the Pocklington Criterion can be used to test exactly $\frac{q+1}{2}$ integers for primality, $1+nq$, where $n=2, 4, …, q+1$. For the special case $q=2$, $n=1,2,3$ can be tested for primality, which is $3$, $5$ and $7$.
As an example, take $q=7$, the following $4$ integers can be tested:
- $1+2(7)=15$
- $1+4(7)=29$
- $1+6(7)=43$
- $1+8(7)=57$
From this list it is easy to see that $29$ and $43$ are primes and the Pocklington Criterion will confirm this fact. Odd $n$ terms are omitted as they are all divisible by $2$.
What we can now do is use these two primes and generate other primes.
What I am interested in, and where the question comes from, is whether this process continues ad infinitum or not. Can we generate an infinite number of primes given a starting prime $q$, or stated differently, can the Pocklington Criterion be used to generate at least one prime given a starting prime $q$. The other part of the question is whether this is in any way useful.
We already know, according to Dirichlet's Theorem on Arithmetic Progressions, that there are an infinite number of primes of the form $1+nq$.
Linnik's Theorem has to do with what the smallest prime in an Arithmetic Progression is.
Research Update:
There are a couple of theorems and conjectures about what the smallest prime in an Arithmetic Progression is, and these are mostly based on Linnik's Theorem.
It is conjectured that $p(a,d)<d^2$. Heath-Brown, Roger (1992). "Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression". This seems to be the smallest conjectured bound.
If the above conjecture is true, then the conjecture that $p(1,q)\le q(q+1)+1$ is also true, and not necessarily useful.
So, the conjecture in the question is not unique. What seems to be unique is the very specific bound $p(1,q)\le q(q+1)+1$. The other part that seems to be unique is the thinking that led to the conjecture.
Research Update:
Referencing the answer below, $q_1q_2+1=r$, where $r$ is the smallest value such that $r=1+tq_1=1+sq_2$, with $q_2>q_1$. This is only true if $gcd(q_1,q_2)=1$.
So $q_1(q_1+1)+1$ is just the largest value of the arithmetic progression $1+tq_1$ that is less than the smallest possible value of $r$, which we get when $q_2-q_1=2$. So the bound in the question does not necessarily have anything to do with the smallest prime in arithmetic progression, but it is an interesting boundary nonetheless.
Best Answer
As it happens, it is a standard conjecture in analytic number theory that for every $\varepsilon>0$, there exists a constant $C(\varepsilon)$ such that $p(a,d) < C(\varepsilon) d^{1+\varepsilon}$. (Probably there's some even more refined upper bound like $Cd(\log d)^2$.) The $d^2$ barrier is often emphasized because that's what follows from the generalized Riemann hypothesis, but that's not as strong as what we believe to be true.
On the other hand, the specific conjecture $p(1,d) < d^2$ does have a cool consequence: define a function $f$ from the set of primes to itself by setting $f(p)$ to be the least prime that is congruent to $1$ modulo $p$. Surprisingly, this function is probably injective! For if $f(q_1)=f(q_2)=r$ (say when $q_1<q_2$), then $r-1$ is divisible by both $q_1$ and $q_2$ by the definition of $f$, hence $r-1$ is divisible by $q_1q_2$ and thus $r>q_1q_2>q_1^2$, contradicting $p(1,q_1) < q_1^2$.