Return to Answer

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\ne 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.

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.

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

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\ne 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.

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\ne 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.

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>Mq$ 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 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.

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

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\ne 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.