Given two primes $p,q\in[T,2T]$, how many integers $m$ of size $O(T^{3/2+\epsilon})$ are there such that the residues $m\bmod p$ and $m\bmod q$ are both $O(polylog(T))$? **Looking for an answer**


Is it possible to construct any such in $polylog(T)$ time without integer programming? *Answered below*



Constructing an integer with small residues for two distinct primes in polynomial time
If such $m$ exists, then $m=up+a=vq+b$ for some $u,v\in O(T^{1/2+\epsilon})$ and $a,b\in O(\mathrm{polylog}(T))$. Then $up-vq=b-a$ and thus $\frac{p}q - \frac{v}u=\frac{b-a}{uq}$, implying that $\frac{v}u$ represents a rational approximation to $\frac{p}q$, which so good that it must be a convergent. So, it enough to compute a continuous fraction for $\frac{p}q$ and search for $\frac{v}u$ among its convergents.


