A mathematician friend gave me this question (partly as a joke) a few months ago and it has puzzled me for a long time:-

Do there exist infinitely many pairs of primes $(p,q)$ such that $pq|2^{p-1}+2^{q-1}-2$?

The equation seems so random I have been unable to make any significant progress on it (I can just derive equally horrible conditions).

I would appreciate it enormously if anyone could set me on the right track regarding this this.

  • 2
    $\begingroup$ Equivalently, $p|2^{q-1}-1$ and $q|2^{p-1}-1$ simultaneously. (I have no time but I barely remember that it was in one of my math olympiad contest which I solved quite some time ago when I was so young!) $\endgroup$ May 7, 2013 at 7:01
  • 6
    $\begingroup$ It looks to me like $(p,q) = (4k+1,8k+1)$ satisfy the requirements for any positive integer $k$ for which they are both primes. The first few are $$[37, 73], [97, 193], [157, 313], [229, 457], [337, 673], [577, 1153], [601, 1201], [661, 1321], [829, 1657], [877, 1753], [937, 1873], [997, 1993]$$ and there are almost certainly infinitely many, but this is still open. $\endgroup$ May 7, 2013 at 7:11
  • $\begingroup$ @RobertIsrael: Does my answer generalize your comment? $\endgroup$
    – Inceptio
    May 7, 2013 at 7:45

4 Answers 4


Edit: The main result proven in this post (stated at the end of the post) is actually known as Zsigmondy's theorem, where I left out the case $n=2$, which is easy to analyse. A neater proof along similar lines can be found here. It somehow slipped my mind that this result was actually a named theorem, until I relooked at this question again today.

The following result kills the problem:

Result: Let $n \geq 49$ be a positive integer and let $a$ be an even positive integer. Then there exists a prime $q$ s.t. $q \nmid a$ and $ord_q(a)=n$.

Note: I have edited in an improved version of this at the end.

To see why this is sufficient, let us assume for a moment that we have proven this result (Proof provided at the end). Take any prime $p \geq 99, p \equiv 3 \pmod{8}$, and take $n=\frac{p-1}{2}, a=2$ in the statement above. Then there exists a prime $q \not =2$ s.t. $ord_q(2)=\frac{p-1}{2}$. Since $p \equiv 3 \pmod{8}$, $(\frac{2}{p})=-1$, so this implies that $p \not =q$. (since $ord_p(2) \not =\frac{p-1}{2}$ by Euler's criterion).

Now by Fermat's little theorem and the definition of order, we have $\frac{p-1}{2}=ord_q(2) \mid q-1$. Also $2 \mid q-1$. Since $\frac{p-1}{2}$ is odd, we get $p-1 \mid q-1$. Fermat's little theorem gives $ord_p(2) \mid p-1$, so $ord_p(2) \mid q-1$. Thus $p \mid 2^{q-1}-1, q \mid 2^{p-1}-1, p \not =q$, so $pq \mid (2^{p-1}-1)+(2^{q-1}-1)$. Since there are infinitely many choices for $p$, we have infinitely many pairs of primes $(p, q)$ satisfying the condition.

Now for the hard part. The following is the proof for the result I stated above.

Proof of result: We have $\prod_{d \mid n}{\Phi_d(x)}=x^n-1$, where $\Phi_n(x)$ is the $n$th cyclotomic polynomial (which is always a polynomial with integer coefficients). Thus $a^n-1=\prod_{d \mid n, d \not =n}{\Phi_d(a)}\Phi_n(a)=k\Phi_n(a)$, where $k=\prod_{d \mid n, d \not =n}{\Phi_d(a)}$ is clearly an integer which is divisible by $a^{\frac{n}{r}}-1$ for each prime $r$ dividing $n$.

It clearly suffices to show that there exists a prime $q$ s.t. $q \mid \Phi_n(a), q \nmid k$. This is because we then have $q \mid k\Phi_n(a)=a^n-1$, and $q \nmid a^{\frac{n}{r}}-1$ for each prime $r$ dividing $n$ (since $k$ is a multiple of $a^{\frac{n}{r}}-1$). Therefore $ord_q(a)=n$. It is clear that $q \nmid a$.

Consider a prime $p$ dividing both $\Phi_n(a)$ and $k=\prod_{d \mid n, d \not =n}{\Phi_d(a)}$. Then $p \mid \Phi_d(a)$ for some $d \mid n, d \not =n$, so $p \mid a^d-1$ so $p \mid a^{\frac{n}{r}}-1$ for some prime $r$ dividing $n$. Let $b=a^{\frac{n}{r}}$, so $p \mid b-1$ . Note that $b-1 \mid k$, so $\Phi(n)(a) \mid \frac{k}{b-1}\Phi_n(a)=\frac{a^n-1}{b-1}=\frac{b^r-1}{b-1}=1+b+b^2+ \ldots +b^{r-1}$. Since $b \equiv 1 \pmod{p}$, we get $0 \equiv 1+b+b^2+ \ldots +b^{r-1} \equiv r \pmod{p}$, so $p=r \mid n$. Therefore any prime dividing both $\Phi_n(a)$ and $k$ must necessarily divide $n$. Let us now suppose that $r^i \|a^{\frac{n}{r}}-1$. Since $p=r$ and $p \mid a^{\frac{n}{r}}-1$, we have $i \geq 1$. Since $a$ is even, we have $r \not =2$. Therefore by Lifting the Exponent Lemma, we have $r^{i+1} \|a^n-1=k\Phi_n(a)$. Since $a^{\frac{n}{r}}-1 \mid k$ we have $r^i \mid k$, so $r^2 \nmid \Phi_n(a)$. Thus $p=r \|\Phi_n(a)$.

As such, we can write $\Phi_n(a)=st$ where $s$ contains all the primes $p$ dividing $\Phi_n(a), k$ and $n$ simultaneously, and any prime dividing $t$ does not divide $k$. It thus suffices to show that $t>1$, so that $t$ has a prime factor $q$, which would then naturally divide $\Phi_n(a)$ but not $k$. By above, $s$ is squarefree, with all prime factors dividing $n$, so $s \mid n$. Thus $s \leq n$. It thus suffices to show that $\Phi_n(a)>n$ (as it would imply $t>1$).

We now finish off the proof by showing that $\Phi_n(a)>n$. Recall that we have $n \geq 49$. To do this, we use Möbius inversion formula to get $\Phi_n(a)=\prod_{d \mid n}{(a^d-1)^{\mu(\frac{n}{d})}}$. Thus

$$\Phi_n(a)=\frac{\prod_{d \mid n, \mu(\frac{n}{d})=1}{(a^d-1)}}{\prod_{d \mid n, \mu(\frac{n}{d})=-1}{(a^d-1)}}>\frac{\prod_{d \mid n, \mu(\frac{n}{d})=1}{a^{d-1}}}{\prod_{d \mid n, \mu(\frac{n}{d})=-1}{a^d}}=a^{\sum_{d \mid n}{d\mu(\frac{n}{d})}-\sum_{d \mid n, \mu(\frac{n}{d})=1}{1}}$$

where we have used the crude bounds $a^d-1 \geq a^{d-1}$ and $\frac{1}{a^d-1}>\frac{1}{a^d}$.

It is easy to see that $\phi(n)=\sum_{d \mid n}{d\mu(\frac{n}{d})}$. If we suppose that $n=\prod_{i=1}^{m}{p_i^{a_i}}>1, m \geq 1$, where $a_i \geq 1$ and $p_1<p_2< \ldots$, then $\sum_{d \mid n, \mu(\frac{n}{d})=1}{1}=\sum_{d \mid n, \mu(d)=1}{1}=\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=1}{1}$. Note that $0=\sum_{d \mid \prod_{i=1}^{m}{p_i}}{\mu(d)}=\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=1}{1}-\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=-1}{1}$ and $\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=1}{1}+\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=-1}{1}=\sum_{d \mid \prod_{i=1}^{m}{p_i}}{1}=2^m$. Thus $\sum_{d \mid \prod_{i=1}^{m}{p_i}, \mu(d)=1}{1}=2^{m-1}$.

Therefore $$\Phi_n(a)>a^{\phi(n)-2^{m-1}} \geq 2^{\phi(n)-2^{m-1}}$$

If $m=1$, then $n$ is a prime, so clearly $2^{\phi(n)-2^{m-1}}=2^{n-2} \geq n$ since $n \geq 49$ (In fact it is true for $n \geq 4$). Therefore we just need to consider the case where $m \geq 2$. Now note that $\phi(n)=n\prod_{i=1}^{m}{\frac{p_i-1}{p_i}} \geq n\prod_{i=1}^{m}{\frac{i}{i+1}}=\frac{n}{m+1}$ since $p_i \geq i+1$. Thus $\Phi_n(a)>2^{\frac{n}{m+1}-2^{m-1}}$. It thus suffices to show that $2^{\frac{n}{m+1}-2^{m-1}} \geq n$. This looks simple.

Note the trivial bound $n=\prod_{i=1}^{m}{p_i^{a_i}} \geq \prod_{i=1}^{m}{p_i} \geq 2\prod_{i=2}^{m}{2(i-1)}=2^m(m-1)!$. We also have the inequality $2^z \geq z^2$ for $z \geq 4$.

If $m \geq 5$. Then $2^{2m-2}=2^m(2^{m-2}) \leq 2^m(m-1)! \leq n$ so $2^{m-1} \leq \sqrt{n}$. Also $n \geq 2^m(m-1)! \geq m^2(m-1)! \geq 24m^2>4(m+1)^2$, so $m+1 \leq \frac{\sqrt{n}}{2}$. Thus $\frac{n}{m+1}-2^{m-1} \geq 2\sqrt{n}-\sqrt{n}=\sqrt{n}$. Thus $2^{\frac{n}{m+1}-2^{m-1}} \geq 2^{\sqrt{n}} \geq (\sqrt{n})^2=n$ since $n \geq 49>16$.

It thus suffices to consider $m=2, 3, 4$.

If $m=4$, then $n \geq \prod_{i=1}^{m}{p_i} \geq 2(3)(5)(7) \geq 210$, so $\sqrt{n} \geq 10$. Thus $n \geq 10\sqrt{n} \geq 5\sqrt{n}+50$, so $\frac{n}{m+1}-2^{m-1}=\frac{n}{5}-8 \geq \sqrt{n}+10-8>\sqrt{n}$, so since $\sqrt{n} \geq 4$, $2^{\frac{n}{m+1}-2^{m-1}} \geq 2^{\sqrt{n}} \geq n$.

If $m=3$, then since $n \geq 49$, we have $\sqrt{n} \geq 7$, so $n \geq 7\sqrt{n} \geq 4\sqrt{n}+21>4\sqrt{n}+16$ so $\frac{n}{m+1}-2^{m-1}=\frac{n}{4}-4 \geq \sqrt{n}$, so since $\sqrt{n} \geq 4$, $2^{\frac{n}{m+1}-2^{m-1}} \geq 2^{\sqrt{n}} \geq n$.

If $m=2$, then since $n \geq 49$, we have $\sqrt{n} \geq 7$, so $n \geq 7\sqrt{n} \geq 3\sqrt{n}+28>3\sqrt{n}+6$ so $\frac{n}{m+1}-2^{m-1}=\frac{n}{3}-2\geq \sqrt{n}$, so since $\sqrt{n} \geq 4$, $2^{\frac{n}{m+1}-2^{m-1}} \geq 2^{\sqrt{n}} \geq n$.

Therefore we have proven that $\Phi_n(a)>n$, and we are done.

For those who read all the way to the end, I feel like I just did the equivalent of nuking a mosquito... Surely there is a simpler way to solve the problem, without proving a stronger result?

Edit: Here I have incorporated the comments below into my answer, to get an improved version of the result stated above.

We shall consider the general case, where $a>1$ and $n>2$ are positive integers. When $a$ is even, we have already proven the result for $n \geq 49$. Consider odd $a>1$ and $n>2$. The proof above still works up to the point where I used Lifting the Exponent Lemma, as now since $a$ is odd, we could possibly have $r=2$.

If $n$ is odd, then $p=r \mid n$ so $r \not =2$, and the rest of the proof follows. If $4 \mid n$, then for $r \not =2$, the proof still works. Consider $r=2$. Since $\frac{n}{r}$ is even, we have $4 \mid a^{\frac{n}{r}}-1$, so we can still use Lifting the Exponent Lemma to get $r^{i+1} \|a^n-1$, and the rest of the proof follows. Finally, if $n \equiv 2 \pmod{4}$, since $n>2$, $n$ has an odd prime factor $u$, so since $4 \mid a^{\frac{n}{u}}-1$ and $2 \nmid u$, we have $v_2(a^{\frac{n}{u}}-1)=v_2(a^n-1)$ by Lifting the Exponent Lemma. Since $a^{\frac{n}{u}}-1 \mid k$ and $a^n-1=k\Phi_n(a)$, this implies that $\Phi_n(a)$ is odd, so $r \not =2$, and the rest of the proof follows.

As such, it suffices to check that $\Phi_n(a)>n$. This has already been shown to be true above for $n \geq 49$, so we only need to worry about $n \leq 48$. We now consider odd and even $a>1$ together. (Note that we only used $n \geq 49$ to prove that $\Phi_n(a)>n$ above, so the proof up to this point still works for small $n$)

(Thanks to @DavidSpeyer for this simplification) Consider $\zeta$, a primitive $n$th root of unity. Then $(a-\zeta)(a-\zeta^{-1}) \geq (a-1)^2$, so $\Phi_n(a)=\prod_{1 \leq k \leq n \atop \gcd(k, n=1)}{a-e^{2i \pi \frac{k}{n}}} \geq (a-1)^{\phi(n)}$. We have $\phi(n) \geq \sqrt{n}$ for $n \not =2, 6$. If $a \geq 4$, then for $n \not =6$ we have $\Phi_n(a) \geq (a-1)^{\phi(n)} \geq 3^{\sqrt{n}}>n$. For $n=6$ we have $\Phi_6(a) \geq 3^{\phi(6)}=9>6$. Therefore, we are done when $a \geq 4$.

When $a=3$, the same approach gives for $n \geq 17$ that $\Phi_n(3) \geq 2^{\sqrt{n}}>n$. We are thus left to consider $a=2, 3 \leq n \leq 49$ and $a=3, 3 \leq n \leq 16$, which can be easily checked with a computer to see that the only exception is $(a, n)=(2, 6)$.

We thus have:

Theorem: Let $a>1, n>2$ be positive integers and suppose $(a, n) \not =(2, 6)$. Then there exists a prime $q$ s.t. $q \nmid a$ and $ord_q(a)=n$.

  • $\begingroup$ A quick computer check of $n \leq 49$ shows that $2^n-1$ always has a prime factor not dividing $2^d-1$ for $d<n$, with the single exception $n=6$. $\endgroup$ May 8, 2013 at 15:45
  • $\begingroup$ @DavidSpeyer (And $n=1$) Indeed, we have $\Phi_6(2)=3 \leq 6$. I think $a=2, n=1, 6$ are the only exceptions. I believe an analogous result holds for odd $a>1$ (with sufficiently large $n$), though $p=2$ would be troublesome when trying to apply Lifting the Exponent Lemma. $\endgroup$
    – Ivan Loh
    May 8, 2013 at 15:56
  • $\begingroup$ $(a,n) = (2^k-1, 2)$ is a counter-example for any $k \geq 2$. I suspect that for $n>2$, the only example is $(a,n) = (2,6)$. Nice answer! I did not know this lemma. $\endgroup$ May 8, 2013 at 16:01
  • $\begingroup$ @DavidSpeyer I think my approach will still work except maybe when $a \equiv 3 \pmod{4}$ and $n \equiv 2 \pmod{4}$, or when $n$ is small. I'll think about what happens in that case. $\endgroup$
    – Ivan Loh
    May 8, 2013 at 16:31
  • $\begingroup$ @DavidSpeyer Got it. If $n$ is odd, then $p=r \mid n$, so $r \not =2$, and the rest of the proof follows. If $4 \mid n$, then if $r \not =2$, the rest of the proof follows. If $r=2$, then $\frac{n}{r}$ is even, so $4 \mid a^{\frac{n}{r}}-1$, so we can still use Lifting the Exponent Lemma to get $r^{i+1} \|a^n-1$, and the rest of the proof follows. If $n \equiv 2 \pmod{4}, n>2$, then $n$ has an odd prime factor $u$, then $v_2(a^{\frac{n}{u}}-1)=v_2(a^n-1)$. Since $a^{\frac{n}{u}}-1 \mid k$, we have $v_2(k)=v_2(a^n-1)$ so $\Phi_n(a)$ is odd, so $r \not =2$, and the rest of the proof follows. $\endgroup$
    – Ivan Loh
    May 8, 2013 at 17:06

No one has explicitly said this yet: Robert Israel's formula always works. Let $(p,q) = (4k+1, 8k+1)$. In one direction, $2^{q-1} -1 = (2^{p-1})^2-1$ and we know $2^{p-1} \equiv 1 \mod p$ so $p | 2^{q-1}-1$. In the other direction, since $q \equiv 1 \mod 8$, we have $\left( \frac{2}{q} \right) = 1$ so $2^{(q-1)/2} \equiv 1 \mod q$ and $q | 2^{(q-1)/2}-1=2^{p-1}-1$.

  • $\begingroup$ Actually, I took the hint from Robert Israel's comment. Just that it was written in another form. $\endgroup$
    – Inceptio
    May 7, 2013 at 14:38


$p,q > 3$


Reframe to $pq|(2^{q-1}-1)+(2^{p-1}-1)$, now you know $2^{q-1}-1 \equiv 0(\mod q)$ and similarily $2^{p-1}-1 \equiv 0(\mod p)$.

$\dfrac{pk+qt}{pq}=s$, For some $k,t,s \in \mathbb{N}$

If we consider the case, $p$ and $q=2p-1$ (Yeah, taking the hint from Robert Israel's comment, $p \equiv 1(\mod 4)$)

$2^{p-1}-1 \equiv 0(\mod p)$ and $2^{2p-2}-1 \equiv (\mod q) \implies (2^{\frac{2p-2}{2}}-1)(2^{\frac{2p-2}{2}}+1) \equiv 0(\mod q)$

It is still not known that $(p,2p-1)$ pairs of primes are infinite.

  • $\begingroup$ Inceptio, does $p|a$ and $q|b\implies p\cdot q|(a+b)?$ $\endgroup$ May 7, 2013 at 5:28
  • $\begingroup$ No. You need to use Chinese remainder theorem for further movement. $\endgroup$
    – Inceptio
    May 7, 2013 at 5:29
  • $\begingroup$ we need $ord_p2|(q-1)$ and $ord_q2|(p-1)$. Could you please elaborate your point a bit? $\endgroup$ May 7, 2013 at 5:32
  • 3
    $\begingroup$ Consider $(p, q)=(7, 13)$, then $ 13 \nmid 2^{7-1}-1$. $\endgroup$
    – Ivan Loh
    May 7, 2013 at 14:40
  • 3
    $\begingroup$ Have you read David Speyer's answer and understood it? Since $q \equiv 1 \pmod{8}$, $2$ is a quadratic residue $\pmod{q}$ so by Euler's criterion $2^{p-1} \equiv 2^{\frac{q-1}{2}} \equiv 1 \pmod{q}$. $\endgroup$
    – Ivan Loh
    May 7, 2013 at 14:58

See also http://www.mathsolympiad.org.nz/wp-content/uploads/2010/04/2010squad-nt-soln.pdf (last page) for an elementary solution which does not rely on Zsigmondy's theorem.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .