Se necesita una explicación de la divisibilidad

Question

Pensé que había demostrado las siguientes dos afirmaciones de divisibilidad, pero más tarde descubrí que estaba equivocado. ¿Podría alguien explicarlos?

1) Para los primos $q\geq 2$ , $2^q-1$ es divisible por algún primo $p$ tal que $p\equiv 3(mod\, 4)$

2) Si $r$ y $s$ son primos distintos, entonces $gcd(2^s-1, 2^r-1)=1$

Answer 1

Si $q\ge 2$ entonces $2^q-1\equiv -1\pmod{4}$ .

Cualquier producto de primos (distintos o no) que sea congruente con $1$ modulo $4$ es a su vez congruente con $1$ modulo $4$ .

Desde $2^q\equiv -1\pmod{4}$ se deduce que no todos los divisores primos de $2^q-1$ puede ser congruente con $1$ modulo $4$ .

Del mismo modo, cualquier número entero positivo de la forma $3k-1$ tiene un divisor primo de la forma $3k-1$ .

En cuanto a la $\gcd$ pregunta, ha sido formulada y respondida muchas veces, y de muchas maneras. En general, $$\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1.$$ Y el $2$ no es importante. Una búsqueda rápida dio este enlace de MSE.

Una forma es hacerlo por inducción sobre el máximo de $a$ y $b$ . Digamos que es $b$ y que $a\lt b$ . Tenga en cuenta que $2^b-1=(2^a-1)2^{b-a}+(2^{b-a}-1)$ . De esto podemos concluir que $\gcd(2^a-1,2^b-1)=\gcd(2^a-1,2^{b-a}-1)$ . Pero $\gcd(a,b-a)=\gcd(a,b)$ .

Answer 2

Para 1), puede observar que $$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).$$ Así que si $2^q-1$ es primo, entonces está bien. Si no, es un producto de primos, y como $2$ no divide $2^q-1$ , si es primo $p$ es tal que $p | 2^q-1$ entonces $ p = 1 \mod 4$ o $p = 3 \mod 4$ . Si todos los divisores de $2^q-1$ son iguales a $1 \mod 4$ se obtiene una contradicción (porque su producto es igual a $1 \mod 4$ ).