MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?
share|cite|improve this question
It seems that I answered this interesting question in the affirmative. Thanks to Emil Jeřábek, Will Sawin, Michael Zieve for the criticism and encouragement. Thanks to fedja for simplifying the proof substantially (see his comment below). – GH from MO Oct 31 '13 at 12:24
up vote 13 down vote accepted

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.

share|cite|improve this answer
How does this produce infinitely many $N$? What if they all divide $p-q$? – Will Sawin Oct 30 '13 at 16:32
Lovely. So, all we need is $k$, and a large $N|p^k-q$ with $k$ relatively prime to $\varphi(N)$. That $N$ or $k$ is prime is of no importance really. Let's do it avoiding Dirichlet. The primality of $k$ and the condition $p<q$ are ingenious, so we keep them. Take a huge prime $k>q-p$. Then $p^k-q\equiv p-q\mod k$. Now take the prime factorization of $p^k-q$ and remove all prime factors that are $1$ modulo $k$. Let $N$ be what is left. Then $k\not\mid\varphi(N)$ ($k$ is neither a prime in $N$, nor a divisor of a prime in $N$ minus $1$) and we still have $N\equiv p-q\mod k$, so $N\ge k+p-q$. – fedja Oct 31 '13 at 10:54
@fedja: I love your version, it is great! Can you also give infinitely many pairwise coprime $N$'s without Dirichlet? – GH from MO Oct 31 '13 at 12:33
@GH:Thanks.Nice proof. One more comment: the procedure to produce infinitely many $N$ seems to go as follows: suppose we have $N_1,\,...\,N_i$ as required, then let $M=N_1\timesN_2...\timesN_i$, then we get $N_{i+1}$ satisfying with the required properties but distinct from $N_1,...,N_i$. – Huichi Huang Oct 31 '13 at 13:30

@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.

share|cite|improve this answer
I admire your skills. So you prove that there is $N$ whose support is not in $U$, then reduction to a prime divisor of $N$ not in $U$ produces the final $N$, right? I would add this remark for clarity. – GH from MO Nov 1 '13 at 13:35
Correct.$\phantom{uuu}$ – fedja Nov 1 '13 at 20:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.