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.
Divisibility problem with primes
2
$\begingroup$
elementary-number-theory
divisibility
prime-numbers
1 Answers
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$$
-
0Could 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
-
0That comes from proving that if $r$ and $s$ are distinct primes, then $\gcd(2^r-1,2^s-1)=1$. – 2012-11-12
-
0I 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
-
0If 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
-
0Dear Gerry, could please explain why $gcd(2^r-1,2^s-1)=1$? – 2012-11-12
-
0I have added a bit, but at some point, *you* have to do the work. – 2012-11-13