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

The answer is yes. Let $M$ be a positive integer exceeding and coprime with both $p$ and $|p-q|$. Here is a proof that a prime $N>M$ exists with the required two properties.

Let $k>M$ be a prime such that $k\equiv 1\pmod{\varphi(M)}$, this exists by (the easiest case of) Dirichlet's theorem on primes. Then $p^k-q\equiv p-q\pmod{kM}$, hence $p^k-q\not\equiv 1\pmod{k}$ and $(p^k-q,M)=(p-q,M)=1$. It follows that $p^k-q$ has a prime divisor $N\not\equiv 1\pmod{k}$ exceeding $M$. Note also that $(pq,N)=1$ by $(p,q)=1$. As $(k,N-1)=1$, there esxist a positive integer $l$ such that $kl\equiv 1\pmod{N-1}$. Hence $q^l\equiv p^{kl}\equiv p\pmod{N}$, and we are done.

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