P4 OMM 2000. Número de primos hasta el primer compuesto

Versión para impresión
Su voto: Ninguno Media: 5 (1 voto)

Para $a$ y $b$ enteros positivos, no divisibles entre $5$, se construye una lista de números como sigue:

  • El primer número es 5 y,
  • a partir del segundo, cada número se obtiene multiplicando el número que le precede (en la lista) por $a$, y sumándole $b$.

(Por ejemplo, si $a = 2$ y $b = 4$, entonces los primeros tres números de la
lista serán: 5, 14, 32 (pues $14 = 5\cdot2 + 4$ y $32 = 14\cdot2 + 4$.)

¿Cuál es la cantidad máxima de primos que se pueden obtener en la lista antes de obtener el primer número no primo?




Imagen de German Puga

La respuesta son cinco primos

La respuesta son cinco primos antes del primer compuesto.

El $n - ésimo $ termino de la lista esta dado por:

$$ 5a^{n-1} + a^{n-2}b + a^{n-3} + \cdots + a^2b + ab + b$$

Llamemos esta expresion $S$ y encontremos el mayor $n$ para el cual $5$ divide a $S$ que ocurre si y solo si $5$ divide a $ a^{n-2}b + a^{n-3} + \cdots + ab + b$ factorizando con el termino comun $b$ se tiene que ocurre si y solo si $5$ divide a $ b ( a^{n-2} + \cdots + a^2 + a + 1)$ si y solo si $5$ divide a $b$ o a la expresion entre parentesis, pero por dato 5 no divide a b por lo que se tendra que 5 tendra que dividir a $ a^{n-2} + \cdots + a + 1$. Trabajemos $\pmod{5}$

Si $a \equiv 1$ la expresion entre parentesis es divisible entre 5 cuando $n = 6$.

Si $a \equiv 2$ se logra cuando $n = 5$, 

Si $a \equiv 3$ se logra cuando $n= 5$

Finalmente si $a \equiv 4 $ se logra cuando $n = 3$ 

Por lo tanto maximo se pueden producir 5 elementos de la lista antes de que aparezca uno divisible entre 5, ahora hay que asegurarnos que sean primos, haciendo $a=1$ y $b=6$ se tiene la siguiente lista:

$ 5, 11 , 17 , 23 , 29 , 35$ en la que aparecen cinco primos antes del primer compuesto.

Saludos

Germán.

Imagen de jmd

Gracias Germán, lo voy a

Gracias Germán, lo voy a pasar a la solución (con algunas ediciones). 

Te saluda