1
$\begingroup$

The problems

  1. 'Given $0<a<b$ and a prime $p<a$ is there an integer $\ell\in[a,b]$ such that $p|\ell$?'

  2. 'Given $0<a<b$ and an integer $q\not\in[a,b]$ is there an integer $\ell\in[a,b]$ such that $q$ is coprime to $\ell$?'

are in $\mathsf{NP}$.

Are these problems in $\mathsf{BPP}$ or at least in $\mathsf{P/poly}$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Both problems are provably in P. For the first one, this is immediate - using division with remainder (which is polynomial time), write $a=qp+r,b=q'p+r'$ with $0\leq r,r'<p$. Then there is $\ell$ divisible by $p$ in this interval iff $r=0$ or $q'>q$. For the record, this doesn't depend on $p$ being prime.

For the second problem is less trivial. We use the following fact due to Iwaniec (see the reference here combined with the fact $\omega(n)=O(\log n)$): there is a constant $C>0$ such that in any interval of length at least $C(\log q\log\log q)^2$ there is an element coprime to $q$. Once we prove that, the problem becomes easy - if $b-a>C(\log q\log\log q)^2$ the answer is yes, otherwise we can just check every $\ell\in[a,b]$ using the Euclidean algorithm.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Nice argument for 1. and thank you for algorithm for 2. $\endgroup$
    – Turbo
    Commented Jan 16, 2021 at 18:46
  • 1
    $\begingroup$ Actually, $\omega(n)=O(\log n/\log\log n)$, hence the bound can be simplified to $C(\log q)^2$. (In fact, the linked question says just that, quoting Iwaniec.) $\endgroup$
    – Emil Jeřábek
    Commented Jan 20, 2021 at 10:41

You must log in to answer this question.

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