2
$\begingroup$

Fix a prime $p$.

I want to get $k<p$ primes $p_1<\dots<p_k$ 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<p$ 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}$?

$\endgroup$
7
  • 2
    $\begingroup$ 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)})$ $\endgroup$
    – katago
    Nov 23, 2020 at 9:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – katago
    Nov 23, 2020 at 9:46
  • 1
    $\begingroup$ @katago Could you stil lprovide a detailed answer? $\endgroup$
    – Turbo
    Nov 23, 2020 at 10:26
  • $\begingroup$ @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. $\endgroup$
    – Turbo
    Nov 23, 2020 at 10:51
  • 2
    $\begingroup$ 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. $\endgroup$
    – katago
    Nov 23, 2020 at 11:42

1 Answer 1

1
$\begingroup$

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<p$. That is, the maximum $k$ is given by $\lfloor \frac{p-c}{2}\rfloor$.

Indeed, since $0<2+1+c<p$ 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .