This can be proven with CRS easily, take a number $b$ such that it is $\equiv i \pmod{q_i}$ and $\equiv -i \pmod{p_i}$ for $i \in [1,k].$ Then take $a=\prod p_i \times \prod q_i.$ here the $2k$ numbers $P_i,Q_i$ are primes bigger than $k.$ Hence $gcd(a,b)=1$ and there exist an other prime $P=ax+b$ for some $x$ by Dirichlet. Now this $P$ satisfy the question.

See the Theorem 4.1 in this paper : http://mathdl.maa.org/images/upload_library/22/Chauvenet/GethnerWagonWick.pdf