# Assume there exists infinitely many prime numbers $l$ such that $2^l -1$ is NOT a prime, show the following

Assume there exists infinitely many prime numbers $l$ such that $2^l-1$ is NOT a prime, prove that ther exists infinitely many pairs $(p,q)$ of DISTINCT prime numbers $p \neq q$ s.t.

$p\mid (2^{q-1}-1)$ and $q\mid (2^{p-1}-1)?$

*So I walked into my professor's office hour and he suggest me to use the following fact $\gcd(2^a-1,2^b-1) = 2^{\gcd(a,b)} -1$, and since here $\gcd(2^{p-1}-1,2^l-1) \ge p \gt 1$, we eventually will have $l \mid p-1$; simialrly for $q$ case, and I finally figure out this problem. Thank you to everyone for helping.

-
Will the last condition be $q\mid (2^{p-1}-1)?$ – lab bhattacharjee Oct 2 '12 at 6:15
oh yes sorry that was typo – fmat Oct 2 '12 at 6:27
$p\mid (2^{q-1}-1)$, but $q\mid (2^{q-1}-1),$ so, $2^{q-1}-1$ is divisible by $lcm(p,q)$ which is $pq\implies ord_{pq}2\mid (q-1)$. Similarly, $ord_{pq}2\mid (p-1)\implies ord_{pq}2\mid (q-1,p-1),\implies ord_{pq}2\mid (q-1,p-q)$ – lab bhattacharjee Oct 2 '12 at 7:49

Suppose $2^l-1$ is not prime. Then either it's a power of a prime, or it has 2 (or more) distinct prime divisors. In the second case, there are obvious candidates for $p$ and $q$. In the first case, well, can you see your way through that one?
So I realized that the first case will lead to a contradiction that $2^l - 1$ is a prime; so all I am going to do is to prove that for every $l$ there exist such prime $p$ and $q$ satisfying the above divisiblity, so I can prove that $p$ and $q$ are infinitely many. Am I on the right track? – fmat Oct 3 '12 at 4:17
I think so, though I'm not sure I understand you. You want to prove that if $2^l-1$ is not prime then there are primes $p$ and $q$ satisfying the division conditions, and I claim it's clear what $p$ and $q$ you should try. – Gerry Myerson Oct 3 '12 at 5:50
so i thought about Fermat's Little Theorem which states that if $p$ is prime and $\gcd(a,p) = 1$ then $a^{p-1} \equiv 1 \pmod p$ – fmat Oct 3 '12 at 6:15
Here since $a = 2$ and $p$ is prime, so we get $p \mid (2^{p-1}-1)$, im thinking since $(2^{l}-1) \mid (2^{p-1}-1)$ and $(2^{l}-1) = qm$ for some $q,m \in \Bbb N$, $q$ prime so $q\mid (2^{p-1}-1)$ Is this the one that you suggest? Is there more obvious $p$ and $q$? – fmat Oct 3 '12 at 6:29
Where do you get $(2^l-1)\mid(2^{p-1}-1)$? – Gerry Myerson Oct 3 '12 at 6:29