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}$?

Improve this question
$\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$ Commented 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$ Commented Nov 23, 2020 at 9:46
  • 1
    $\begingroup$ @katago Could you stil lprovide a detailed answer? $\endgroup$ Commented 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$ Commented 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$ Commented Nov 23, 2020 at 11:42

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.