Demostrar que el conjunto de enteros de la forma $2^k3$ contiene un subconjunto infinito de números relativamente primos

Question

Demostrar que el conjunto de enteros de la forma $2^k 3(k = 2, 3, ...) $ contiene un subconjunto infinito en el que cada dos miembros son relativamente primos.

---

Tratando de resolver este problema, me topé con esta conjetura:

Hay una infinidad de números primos $p$ tal que $p=2^n - 1, n\in \mathbb{N}$

Me interesa resolver tanto el problema como la conjetura.

Answer 1

Un primo de la forma $2^n-1$ se llama El primo de Mersenne . Es un problema abierto si hay un número infinito de ellos, pero no hay indicios concretos de que la oferta se agote; los mayores primos conocidos actualmente son todos primos de Mersenne.

---

Sugerencia para el problema original: Demuestre que es una condición suficiente para $2^k-3$ y $2^j-3$ para ser coprima que $(k-2)\mid(j-2)$ pero $k\ne j$ . A continuación, considere los exponentes de la forma, por ejemplo, $n!+2$ .

No tengo ni idea de por qué pensé que eso funcionaría. No es el caso que el $2^{2+2}-3$ y $2^{14+2}-3$ son coprimos, por ejemplo, a pesar de que $2\mid 14$ . Pero no puedo borrar la respuesta porque está acptada ...

Answer 2

Aquí hay un intento de prueba incompleta que implica el teorema de Ramsey infinito:

Dejemos que $G$ denota el grafo completo infinito con vértices $2^k-3$ , $k\in\mathbb{N}\backslash\{1\}$ . Colorea un borde de $G$ rojo si sus extremos son relativamente primos y azul si no lo son. Aplicando el infinito Ramsey obtenemos un infinito subgrafo rojo de $G$ en cuyo caso hemos terminado, o un subgrafo azul infinito.

Afirmo que esto último no puede ocurrir: Supongamos que hay infinitas $k$ de manera que la correspondiente $2^k-3$ son pares no relativamente primos. Entonces debe existir un primo $p$ dividiendo $2^{k_n}-3$ para un número infinito de $k_1<k_2< k_3\ldots$ y claramente $p\neq 2$ .

Tenga en cuenta que $p$ divide cada diferencia $2^{k_{n+1}}-2^{k_n}=2^{k_n}(2^{k_{n+1}-k_n}-1)$ y por lo tanto divide $2^{k_{n+1}-k_n}-1$ . Dejemos que $m$ ser más pequeño con la propiedad de que $p$ divide $2^m-1$ . Si para algunos $n$ tenemos $k_{n+1}-k_n>m$ entonces aplicando el mismo argumento de divisibilidad a la diferencia $2^{k_{n+1}-k_n}-2^m$ obtenemos una contradicción con la definición de $m$ . Por lo tanto, el $k_n$ están en progresión aritmética $k_n=a+nm$ lo cual es (probablemente) absurdo.

Answer 3

Hay una solución disponible aquí.

Para reproducirlo, no vaya a ser que el enlace se pierda:

Es evidente que podemos encontrar un subconjunto de tamaño 1. Mostramos cómo ampliar un conjunto de $r$ tales enteros a un conjunto de $r+1$ de modo que el resultado se deduce por inducción.

Supongamos que $2^{n_1} - 3, ... , 2^{n_r} - 3$ son todos relativamente primos. La idea es encontrar $n$ tal que $2^n - 1$ es divisible por $m = (2^{n_1} - 3) \cdots (2^{n_r} - 3)$ porque entonces $2^n - 3$ debe ser relativamente primo de todos los factores de $m$ .

Al menos dos de $2^0, 2^1, ... , 2^m$ debe ser congruente mod $m$ . Así que supongamos $m_1 > m_2$ y $2^{m_1} \equiv 2^{m_2} \mod m$ . Entonces debemos tener $2^{m_1 - m_2} - 1 \equiv 0 \mod m$ ya que $m$ es impar. Así que podemos tomar $n_{r+1}$ para ser $m_1 - m_2$ .

Answer 4

Dejemos que $p_i$ sea el $i^\text{th}$ impar prime. Sea $(k_r)_{r=1}^\infty$ sea cualquier secuencia de enteros tal que $k_1 \geqslant 3$ , $k_{r+1} > k_r$ y $k_{r+1}$ es divisible por $\prod_{i=1}^{m_r} (p_i - 1)$ , donde $p_{m_r}$ es el mayor factor primo de $a_r = 2^{k_r} - 3$ . Entonces $$ a_{r+1} = \left(2^{k_{r+1}/(p_i - 1)}\right)^{p_i - 1}\!\!\! - 3 \equiv -2 \pmod{p_i} \quad (i = 1, \ldots, m_r), $$ por el pequeño teorema de Fermat. Por lo tanto, $a_{r+1}$ no tiene ningún factor primo en común con $a_r$ y $m_{r+1} > m_r$ . Las secuencias $(k_r)$ , $(m_r)$ , $(a_r)$ son estrictamente crecientes. Si $r, s$ son números enteros con $1 \leqslant r < s$ entonces $a_s$ no es divisible por ninguno de los primos $p_1, \ldots, p_{m_{s-1}}$ En particular $p_1, \ldots, p_{m_r}$ Por lo tanto $a_s$ es primordial para $a_r$ .