Suppose that $p,q>1$ are two relatively prime integers. Are there infinitely many positive integers $N$ such that
 $N$ is relatively prime to $p$ and $q$;
 there exists positive integers $k,l$ such that $p^k\equiv q\mod N$ and $q^l\equiv p \mod N$?
Suppose that $p,q>1$ are two relatively prime integers. Are there infinitely many positive integers $N$ such that



The answer is yes for all $p$ and $q$. We shall assume, without loss of generality, that $p<q$. It suffices to show that for any positive integer $M$ which is coprime with $p$, there exists a prime $N\nmid M$ with the required two properties (since the first property implies $N\nmid p$). Let $k>Mq$ be a prime such that $k\equiv 1\pmod{\varphi(Mpq)}$, which exists by (the easiest case of) Dirichlet's theorem on primes in arithmetic progressions. Then $p^kq\equiv pq\pmod{kMpq}$, since $(p,M)=1$ by hypothesis and $(p,pq)=(p,q)=1$. It follows that $pq$ divides $p^kq$, and thus that $$\frac{p^kq}{pq}\equiv 1\pmod{kM}. $$ Since $k>q$ and $p\ge 2$, the left side is positive, so it has a prime divisor $N\not\equiv 1\pmod{k}$, which in addition must satisfy $N\nmid M$. In particular, $p^k\equiv q\pmod{N}$, so the condition $(p,q)=1$ implies that $(N,pq)=1$. Since $(k,N1)=1$, there exists a positive integer $l$ such that $kl\equiv 1\pmod{N1}$. Therefore $q^l\equiv p^{kl}\equiv p\pmod{N}$, and we are done. 


@GH from MO. Yes, we can find infinitely many primes $N$ without Dirichlet as well though the argument is a bit too long to be posted as a comment. Let $A$ be a large number. Let $U$ be a finite set of primes that can divide $p^kq$ in principle. Note that if we want to have $p^k\equiv p^\ell\mod u^m$ with $u\in U$, then, by the lifting the exponent lemma, we need to ensure that $v_u(k\ell)\ge mC(u,p)$. Let $S$ be the set of primes between $A$ and $2A$. Now take $k\in S$ and construct $N$ as above. Recall that $N\equiv pq\mod k$. If we are in trouble, we must have $N$ consisting of primes in $U$ only. Since $N\ge k+pq$, we must have $u^{v_u(N)}\ge A^{\delta(U)}$ for some $u\in U$. Let $\ell$ be the next prime in $S$ corresponding to the same $u\in U$ with this property. Then $v=v_u(\ellk)$ also satisfies $u^v\ge c(U)A^{\delta(U)}$ and thereby $\ellk\ge c(U)A^{\delta(U)}$. This results in $S\le C(U)A^{1\delta(U)}$, which (if true for all sufficiently large $A=2^k$) is bad enough to contradict something as simple as Euler's theorem on the divergence of inverse primes. 

