Refutación de la afirmación de que los números 1+2+4, 1+2+4+8, 1+2+4+8+16... alternan entre primos y compuestos

Question

Estoy trabajando con un libro de teoría numérica elemental y me he encontrado con el siguiente problema.

Demuestre que las siguientes afirmaciones son erróneas:

Afirmación 1: La secuencia 1+2+4, 1+2+4+8, 1+2+4+8+16, ... es alternativamente prima y compuesta.

Afirmación 2: Uno o ambos números 6n-1 y 6n+1 son primos.

De hecho, he encontrado contraejemplos a ambas afirmaciones, pero sólo a través de la fría y dura comprobación de los números. Quiero creer que este problema no estaría aquí a no ser que hubiera alguna forma elegante de refutar estas afirmaciones. ¿Hay alguna otra forma de refutar las afirmaciones que no sea simplemente encontrar un contraejemplo?

Nota: las dos reclamaciones no tienen ninguna relación.

Answer 1

Para la afirmación 2: Los números $m!+2, m!+3,\dots,m!+m$ serán todos compuestos. Si $m$ es lo suficientemente grande, esta secuencia contendrá algunos $6n-1$ y $6n+1$ .

Para la afirmación 1: Obsérvese que $2^{ab}-1$ es siempre divisible por $2^a-1$ (ya que $x-1$ divide $x^b-1$ en $\Bbb{Z}[x]$ Ahora bien, dejemos que $x=2^a$ ); por lo tanto $2^8-1, 2^9-1, 2^{10}-1$ son todos compuestos.

Answer 2

El cálculo de números es una técnica consagrada; muchas conjeturas son mucho más fáciles de resolver probándolas (ya sea por fuerza bruta o mediante búsquedas más inteligentes) en lugar de pensar en ellas.

Pero a veces estas conjeturas -así como los métodos para refutarlas- sugieren afirmaciones más generales. Los números de su primera conjetura son

$$ \sum_{i=0}^{n-1} 2^i = 2^n - 1$$

se llaman números de Mersenne. Como has observado, es bastante fácil demostrar que no son primos/compuestos, y hay una serie de teoremas sobre cuándo un número de Mersenne puede ser primo o compuesto (por ejemplo, para $2^n - 1$ para ser primo, $n$ también debe ser primo)

También hay cuestiones abiertas: por ejemplo, nadie sabe si hay o no infinitos números de Mersenne que sean primos.

Answer 3

Una bonita y sencilla para la reclamación 2:

Obsérvese que ambos términos del par $(x^3+1, x^3-1)$ factorizar (teniendo factores más simples de $x+1$ y $x-1$ respectivamente), y que $(6n+1,6n-1)$ será de esa forma si $n=6^2$ .

(Que es simplemente $(217,215)$ y efectivamente el par es divisible por 7 y 5 respectivamente).

Este argumento se extiende a los pares de la forma $(kn+1, kn-1)$ para $k>2$ (aunque el caso de $k$ De todos modos, impar es obvio, ya que ambos miembros estarán igualados).

Answer 4

Para divertirme, he construido a mano (bueno, en realidad en mi cabeza) los más pequeños contraejemplos de ambas afirmaciones. Aquí están los resultados, así como la forma en que los encontré.

Reclamo 1: El séptimo miembro de la serie, $1+2+4+8+16+32+64+128+256=511$ es compuesto, no primo como se especifica. $511 = 7*73$ .

Esta afirmación es más fácil de refutar una vez que reconocemos que los elementos

$7, 15, 31, 63, 127, 255, 511, ...$

son los números de Mersenne, $2^n-1$ a partir de $n = 3$ . Un hecho útil sobre los números de Mersenne es que un número de Mersenne sólo puede ser primo si su exponente, $n$ es primordial. Esto implica inmediatamente que los elementos $2, 4, 6, 7$ de la serie dada son compuestos. Así, vemos que el elemento $7$ , $511$ debe ser un contraejemplo, porque es un elemento compuesto impar. Para comprobar que es el contraejemplo más pequeño, basta con verificar que los elementos $1,3,5$ , a saber $7, 31, 127$ son primos. De hecho lo son, así que $511$ es el contraejemplo más pequeño.

Reclamación 2: $n = 20, (119,121)$ . $119 = 7*17, 121 = 11*11$

Para ello, he clasificado las posibles soluciones según el factor primo inferior de $6n-1$ y $6n+1$ . Evidentemente, ninguno de los dos valores será $2$ o $3$ . Primero, probé el par $(5,7)$ .

He calculado que $x \equiv 0 \mod 5$ y $x \equiv -1 \text{ or } 1 \mod 6$ implica $x \equiv 5\text{ or }25 \mod 30$ respectivamente, por lo que el otro miembro del par debe ser igual a $7\text{ or }23 \mod 30$ . Los múltiplos más pequeños de 7 que satisfacen esas congruencias, aparte del propio 7, son $217$ y $203$ respectivamente.

Como no estaba seguro de que esta solución $(203, 205)$ fuera lo más pequeño posible, repetí el proceso para el par de factores $(5, 11)$ . Reutilización de la congruencia $7\text{ or }23 \mod 30$ para el múltiplo de $11$ , he encontrado los múltiplos más pequeños $187$ y $143$ .

En este punto, mi menor contraejemplo fue $(143, 145)$ . Sólo quedaba un caso por comprobar: $(119,121)$ porque $121$ es el único número con $11$ como su factor más pequeño bajo $143$ y ya había comprobado que el par $(5,7)$ no tenía soluciones bajo $(143, 145)$ . Resulta que, $(119,121)$ es una solución, por lo que debe ser la más pequeña.

Answer 5

1. Para $ n=6k+2 $ los números $ 2^n-1 $ y $ 2^{n+1}-1 $ son ambos compuestos.
2. Para $ n= 6^{2k} $ los números $ 6n+1, 6n-1 $ son ambos compuestos.