Skip to main content
8 of 12
added 423 characters in body
GH from MO
  • 105.2k
  • 8
  • 292
  • 398

This is an updated version of my previous answer that was restricted to $q=p+1$ (and was itself a corrected version).

The answer is yes for all $p$ and $q$ (assumed to be coprime). It suffices to show that for any squarefree integer $M>1$ coprime with $pq$, there exists a prime $N\nmid M$ with the required two properties. Note that $N\nmid pq$ is automatic by the first property. We shall assume, without loss of generality, that $p<q$.

Let $k>M|p-q|$ be a prime such that $k\equiv 1\pmod{\varphi(M|p-q|)}$, this exists by (the easiest case of) Dirichlet's theorem on primes. Then $p^k-q\equiv p-q\pmod{kM|p-q|}$ upon noting that $p$ is coprime with both $M$ and $|p-q|$. It follows that $|p-q|$ divides $p^k-q$, and the quotient $$\frac{p^k-q}{|p-q|}\equiv -1\pmod{kM}. $$ As a result, the left hand side has a prime divisor $N\not\equiv 1\pmod{k}$ not dividing $M$. In particular, $p^k\equiv q\pmod{N}$, and so $(N,pq)=1$ by $(p,q)=1$. As $(k,N-1)=1$, there exist 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.

GH from MO
  • 105.2k
  • 8
  • 292
  • 398