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$
-
0I have added a bit, but at some point, *you* have to do the work. – 2012-11-13