Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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?

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.