# Divisibility explanation needed

I thought I proved the following two divisibility statements but later I found out I was wrong. Could someone explain them?

1) For primes $q\geq 2$, $2^q-1$ is divisible by some prime $p$ such that $p\equiv 3(mod\, 4)$

2) If $r$ and $s$ are distinct primes, then $gcd(2^s-1, 2^r-1)=1$

-

If $q\ge 2$, then $2^q-1\equiv -1\pmod{4}$.

Any product of primes (distinct or not) which are congruent to $1$ modulo $4$ is itself congruent to $1$ modulo $4$.

Since $2^q\equiv -1\pmod{4}$, it follows that not all the prime divisors of $2^q-1$ can be congruent to $1$ modulo $4$.

Similarly, any positive integer of the form $3k-1$ has a prime divisor of the form $3k-1$.

As to the $\gcd$ question, it has been asked and answered many times, and in many ways. In general, $$\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1.$$ And the $2$ is not important. A quick search gave this MSE link.

One way is to do it by induction on the maximum of $a$ and $b$. Say it is $b$, and that $a\lt b$. Note that $2^b-1=(2^a-1)2^{b-a}+(2^{b-a}-1)$. From this we can conclude that $\gcd(2^a-1,2^b-1)=\gcd(2^a-1,2^{b-a}-1)$. But $\gcd(a,b-a)=\gcd(a,b)$.

-

For 1), you can notice that $$2^q-1 = 2^q - 1^q = (2-1) \times \sum_{i=0}^{q-1} 2^i = 3 + \sum_{i=2}^{q-1} 2^i = 3 + 4 \times \sum_{i = 0}^{q-3} 2^i = 3 + 4 \times (2^{q-2} - 1).$$ So if $2^q-1$ is prime, then it is fine. Otherwise, it is a product of primes, and since $2$ does not divide $2^q-1$, if prime $p$ is such that $p | 2^q-1$ then $p = 1 \mod 4$ or $p = 3 \mod 4$. If all the divisors of $2^q-1$ are equal to $1 \mod 4$ you get a contradiction (because their product is equal to $1 \mod 4$).

-