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

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.

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

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

Hint:

$p,q > 3$

$pq|2^{p-1}+2^{q-1}-2$

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.

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.