2
$\begingroup$

I got stuck with another divisibility problem. Prove that there exist infinitely many primes p that can be represented in the form $p=4k-1$, where k is a natural number, such that $2^q-1 \equiv 0 \pmod p$ for some prime q.

1 Answers 1

2

First prove that for $q\ge2$, $2^q-1$ is divisible by some prime $p$, $p\equiv3\pmod4$. Then prove that if $r$ and $s$ are distinct primes, then $\gcd(2^r-1,2^s-1)=1$.

EDIT: to expand on this --- anything that divides both $2^r-1$ and $2^s-1$ must divide their difference and thus, being odd, must divide $2^{r-s}-1$ (assuming $r\gt s$). Now repeat the argument with $2^s-1$ and $2^{r-s}-1$. By induction, show that $$\gcd(2^r-1,2^s-1)=2^{\gcd(r,s)}-1$$

  • 0
    Could you please provide some more details? I proved the first part but I don't see how I get the "infinitely many" primes p?2012-11-12
  • 0
    That comes from proving that if $r$ and $s$ are distinct primes, then $\gcd(2^r-1,2^s-1)=1$.2012-11-12
  • 0
    I think I proved the second part but still I don't get the idea. If $gcd(2^r-1,2^s-1)=1$, then does it follow that there exist primes $p_1=4k_1-1$ and $p_2=4k_2-1$ such that $p_1$ and $p_2$ divide $2^r-1$ and $2^s-1$?2012-11-12
  • 0
    If two numbers are relatively prime, they must be divisible by different primes, right? and you wrote that you have proved the first part, the part about $2^q-1$ being divisible by some prime $p$, $p\equiv3\pmod 4$.2012-11-12
  • 0
    Dear Gerry, could please explain why $gcd(2^r-1,2^s-1)=1$?2012-11-12
  • 0
    I have added a bit, but at some point, *you* have to do the work.2012-11-13