2
$\begingroup$

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.

  • 0
    $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)$2012-10-02

1 Answers 1

2

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?

  • 0
    Yes because I figured out this problem with my professor's key hint that I posted right below my question, but I also think your hint gave an great contribution to my solution on this problem, so I decided to accept your answer just to show that this problem has been solved.2012-10-04