Find all pairs of primes $p,q$ such that $pq \mid 2^p +2^q$

Solution 1:

A slight tune up to the argument presented in Prometheus' answer (currently deleted, but hopefully soon fixed and undeleted) proves that there are no solutions such that $p$ and $q$ are both odd primes.

Lemma. Assume that $p$ is a prime factor of $2^{2^ts}+1$ where $t,s$ are positive integers, $s$ odd. Then $$ p\equiv1\pmod{2^{t+1}}. $$

Proof. Let $m$ be the order of the residue class of $2$ in $\Bbb{Z}_p^*$. Because $p\mid 2^{2^ts}+1$, we have $2^{2^ts}\equiv-1\pmod p$, and consequently $2^{2^{t+1}s}\equiv1\pmod p$. This means that $m\mid 2^{t+1}s$ but $m\nmid 2^ts$. Therefore we can conclude that $2^{t+1}\mid m$. But by Lagrange's theorem $m\mid p-1$, so the claim follows.

The rest is easy. Without loss of generality we can assume that $2<p<q$ (the case $p=q$ is obviously impossible). Write $q-p=2^ts$, $s$ odd. The assumption is that $$ pq\mid 2^p+2^q=2^p(2^{q-p}+1). $$ This implies that both $p$ and $q$ should be factors of $2^{q-p}+1$. But the Lemma then implies that $$ p\equiv q\equiv 1\pmod{2^{t+1}}. $$ This means that $q-p$ is divisible by $2^{t+1}$ contradicting the fact that $s$ is an odd integer by design.