Suppose that $p,q>1$ are two relatively prime integers. Are there infinitely many positive integers $N$ such that


1. $N$ is relatively prime to $p$ and $q$;
2. there exists positive integers $k,l$ such that $p^k\equiv q\mod N$ and $q^l\equiv p \mod N$?



Infinitely many $N$ such that $\langle p\rangle=\langle q\rangle$ mod $N$
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(M|p-q|)}$, which exists by (the easiest case of) Dirichlet's theorem on primes in arithmetic progressions. Then $p^k-q\equiv p-q\pmod{kM|p-q|}$, since $(p,M)=1$ by hypothesis and $(p,|p-q|)=(p,q)=1$. It follows that $|p-q|$ divides $p^k-q$, and thus that
$$\frac{p^k-q}{|p-q|}\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,N-1)=1$, there exists a positive integer $l$ such that $kl\equiv 1\pmod{N-1}$. Therefore $q^l\equiv p^{kl}\equiv p\pmod{N}$, and we are done.


