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
    Will the last condition be $q\mid (2^{p-1}-1)?$2012-10-02
  • 0
    oh yes sorry that was typo2012-10-02
  • 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
    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?2012-10-03
  • 0
    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.2012-10-03
  • 0
    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$2012-10-03
  • 0
    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$?2012-10-03
  • 0
    Where do you get $(2^l-1)\mid(2^{p-1}-1)$?2012-10-03
  • 0
    Yeah I cheated a bit... I know both $2^{p-1} \equiv 1 \pmod p$ and $2^l \equiv 1 \pmod p$ but that may not be enough to have $(2^l-1)\mid(2^{p-1}-1)$ Any other hints?2012-10-03
  • 0
    I am a bit not sure when you claim that there are obvious candidates for $p$ and $q$ because so far I still haven't found out what they should be like.2012-10-03
  • 0
    Sorry, I'm going to have to put some more thought into this. In the case where $2^l-1=pq$, you get $$0\equiv2^l-1=(2^p)^q-1\equiv2^q-1\pmod p$$ and similarly $q\mid2^p-1$. I thought there was a simple way to generalize this this to $2^l-1=pqr$ for arbitrary $r$ but what I originally had in mind didn't pan out when I tried to write it down.2012-10-04
  • 0
    How do we get $2^l-1=(2^p)^q-1$ I thought $l$ is a prime so it shouldn't be the product of $p$ and $q$?2012-10-04
  • 0
    I have really butchered this one, haven't I? I'm glad you persevered and got through to an answer. You should post it, and then later you can accept it.2012-10-04
  • 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