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



What are the complexity classes of these problems about divisibility and coprimality?
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](https://math.stackexchange.com/a/1163946/127263) 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.


