Question on existence of infinite pairs of primes I have the following problem with me:
Show that there are infinitely many prime numbers $p, q$ such that $p \mid 2^{q - 1} - 1,  q \mid 2^{p - 1} - 1$.
Obviously $p$ and $q$ both are not equal to 2. When I have $p = q$, The result is again obvious by Fermat's Little theorem. Now comes the case where I found the difficulty, whenever $p$ is not equal to $q$ and both are not equal to 2. In such a case, I need two primes $p$ and $q$ in such a way that the product $pq$ divides $2^{p - 1} - 1$. Now how do I prove that there exist an infinite number of them.
A silly doubt: When I took the case $p = q$ and showed it is true by Fermat, and since there exist infinite number of primes, can I say that I have proved the given statement? Either ways I am interested in the case where $p$ is not equal to $q$.
 A: Judging directly by the wording of the problem, yes, you have proven the claim - all pairs $(p,p)$ for any prime $p>2$ work. This is really unsatisfying.
I present a proof that there are infinitely many pairs $(p,q)$ of distinct primes that satisfy this. It is a strange proof and I believe it can be made better, but it is a proof nonetheless. 
Lemma. If $r$ is a prime number for which $2^r-1$ is not prime, there exist two distinct primes $p,q>r$ so that the condition holds for $(p,q)$. 
Proof. We first claim that $2^r-1$ is not a prime power. Indeed, if $2^r=p^k+1$ for some prime $p$ and exponent $k>1$, if $k$ is even we have that the RHS is $\equiv 2\bmod 8$, a contradiction, and it $k$ is odd we may write
$$2^r=(p+1)\left(p^{k-1}-p^{k-2}+\cdots-p+1\right)$$
where the second factor is odd and greater than $1$, a contradiction. So, there exist at least two distinct prime factors of $2^r-1$.
Claim. Let $r$ be a prime number. If a prime $p$ divides $2^r-1$, then $r|p-1$. 
Proof. We have that the order $\mathrm{ord}_p(2)|r$, so it is either $1$ or $r$. It is clearly not $1$ as $p\nmid 1$, so $\mathrm{ord}_p(2)=r$. As $\mathrm{ord}_p(x)|p-1$ for any prime $p$ and integer $x$, we see that $r|p-1$. $\blacksquare$ 
From here, let $p,q$ be two distinct primes that divide $2^r-1$. We have $r|p-1,q-1$, so 
$$p|2^r-1|2^{q-1}-1,$$
and similarly $q|2^{p-1}-1$. Finally, $r|p-1,q-1\implies r\leq p-1,q-1 \implies p,q>r$, so we are done. $\blacksquare$

If there are infinitely many primes for which $2^r-1$ is composite (I believe this is open), we then have that we can find pairs $(p,q)$ satisfying the problem condition with arbitrarily large values of $\min(p,q)$, so we have infinitely many.
Otherwise, let $r_0$ be the largest prime for which $2^{r_0}-1$ is composite (such a prime exists - take $2^{11}-1=23\cdot 89$ for example), and let $p_0,q_0$ be distinct primes dividing $2^{r_0}-1$. 
Define $p_{n+1}=2^{p_n}-1,q_{n+1}=2^{q_n}-1$ for all $n\geq 0$. We claim that the pair $(p_{n+1},q_{n+1})$ satisfies the condition. First we see that $(p_n,q_n)$ is actually a pair of distinct primes, which is immediate by the fact that $p_0,q_0>r_0$ and $f(x)=2^x-1$ is monotone increasing (and in fact injective over $\mathbb{N}$). We show the remaining claim by induction. 
By our lemma, the pair $(p_0,q_0)$ satisfies the problem condition, so our base case is true. For any pair $(p,q)$ satisfying the problem condition, we have that
$$p|2^{q-1}-1\implies p|2^q-2 \implies 2^p-1|2^{(2^q-1)-1}-1,$$
and similarly $2^q-1|2^{(2^p-1)-1}-1,$ so the condition holds for $(2^p-1,2^q-1)$. So, if $(p_n,q_n)$ satisfies the condition, then $(p_{n+1},q_{n+1})$ does too. So, we have constructed an infinitely increasing sequence of pairs of distinct primes satisfying the problem condition, and thus we have infinitely many such pairs. $\blacksquare$
