Infinitely many $N$ such that $\langle p\rangle=\langle q\rangle$ mod $N$

Question

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

Answer 1

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.

Answer 2

@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^k-q$ 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 m-C(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 p-q\mod k$. If we are in trouble, we must have $N$ consisting of primes in $U$ only. Since $N\ge k+p-q$, 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(\ell-k)$ also satisfies $u^v\ge c(U)A^{\delta(U)}$ and thereby $\ell-k\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.