# Primes in modular arithmetic progression

Fix a prime $$p$$.

I want to get $$k primes $$p_1<\dots such that at every $$i\in\{1,\dots,k\}$$ we have $$p_i\equiv (2i+1+c)\bmod p$$ where $$c$$ is fixed and $$2k+1+c holds.

1. For a given $$p$$ what is the maximum $$k$$ I can get?

2. For a given $$p$$ and given $$k$$ what is the minimum $$p_1$$ and $$p_k$$ that can achieve this?

3. How small can $$\prod_{i=1}^kp_i$$ be?

4. What are the smallest ratios $$\frac{p_1}{p}$$ and $$\frac{p_k}{p}$$?

• Siefel-Walfisz estimate give a partial answer to 2 and 3. $\forall \epsilon>0$, $p_1,p_k$ can choose moroally $O((\log p)^{1+\epsilon})$, and $\Pi_{i=1}^k p_i$ can choose moroally $O((\log p)^{(p-c-1)(1+\epsilon)})$ Nov 23, 2020 at 9:26
• Sorry this is not true, use Siefel-Walfisz we can only get a estimate $\forall \epsilon>0$, $p_1,p_k$ can choosed $O(e^{p^{\epsilon}})$, and $\Pi_{i=1}^kp_i$ can be choosed $O(e^{p^{\epsilon}(p-c-1)})$. and the best thing we can expect for 2 and 3 maybe is the unprove(and without tool to attack it now) bound in the previous comment. Nov 23, 2020 at 9:46
• @katago Could you stil lprovide a detailed answer? Nov 23, 2020 at 10:26
• @katago I made the remainders all odd. I think this will shrink the size of $p_k$ or else we have to alternate between odd and even multiples of $p$ for $p_i$ as $i$ increases. Nov 23, 2020 at 10:51
• a remark is, the constant $C_{N}$ is not effectively computable because Siegel's theorem is ineffective. From the theorem we can deduce the following bound regarding the prime number theorem for arithmetic progressions: If, for $(a, q)=1,$ by $\pi(x ; q, a)$ we denote the number of primes less than or equal to $x$ which are congruent to $a \bmod q$, then $$\pi(x ; q, a)=\frac{\operatorname{Li}(x)}{\varphi(q)}+O\left(x \exp \left(-\frac{C_{N}}{2}(\log x)^{\frac{1}{2}}\right)\right)$$ where $N, a, q, C_{N}$ and $\varphi$ are as in the theorem, and Li denotes the logarithmic integral. Nov 23, 2020 at 11:42

Assuming that $$c\geq 0$$, the answer to 1 is that there is no bound for $$k$$ besides the one stated in the question: $$2k+1+c. That is, the maximum $$k$$ is given by $$\lfloor \frac{p-c}{2}\rfloor$$.
Indeed, since $$0<2+1+c and thus $$\gcd(2+1+c,p)=1$$, by Dirichlet theorem, there exists prime $$p_1$$ satisfying $$p_1\equiv 2+1+c\pmod{p}.$$ Then, again by Dirichlet theorem, there exists $$p_2>p_1$$ such that $$p_2\equiv 4+1+c\pmod{p}.$$ And so on.