Divisibility problem with primes

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.

-

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$$
That comes from proving that if $r$ and $s$ are distinct primes, then $\gcd(2^r-1,2^s-1)=1$. –  Gerry Myerson Nov 12 '12 at 10:59
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$? –  Adam Nov 12 '12 at 11:43
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$. –  Gerry Myerson Nov 12 '12 at 12:13
Dear Gerry, could please explain why $gcd(2^r-1,2^s-1)=1$? –  Adam Nov 12 '12 at 21:22