¿Hay alguna $k$ para lo cual podemos demostrar que $n^n+k$ ¿nunca es primo?

Question

¿Existe algún número entero positivo $k$ , de tal manera que podemos demostrar que $n^n+k$ no es primo para ningún entero positivo $n$ ?

$$n^n+1805$$ tiene un factor primo no superior a $43$ hasta $n=1805$ . Sin embargo, para los múltiplos de $1806$ en general, esto ya no es así.

Creo que para no $k$ , $n^n+k$ debe tener un factor "pequeño" para todos $n$ .

¿Es esto cierto, y si es así, destruye esto cualquier esperanza de una prueba?

Answer 1

La secuencia formada por el más pequeño $n$ en función de $k$ está en OEIS como A087037 . Como se indica en la página, para $k=(6m-1)^3$ no existe tal $n$ . Para completar la prueba, la repito aquí.

Dejemos que $k=(6m-1)^3$ y considerar $N=n^n+k$ . Para $n$ impar, $N$ es par, por lo tanto compuesto. Si $3\mid n$ entonces $N$ es una suma de cubos, por lo tanto compuesta, ya que $a^3+b^3$ factores como $(a+b)(a^2-ab+b^2)$ . Por último, si $n$ es par pero no divisible por $3$ , $$n^n+k\equiv(\pm 1)^n+(-1)^3\equiv 1-1\equiv 0\pmod 3$$ y por lo tanto es compuesto.

Este método proporciona $k=125$ como el menor número para el que conocemos $n$ no existe, pero como señala la entrada de la OEIS, la existencia de $n$ es desconocido para muchos pequeños $k$ , siendo el menor de ellos $k=8$ .

Answer 2

No es una respuesta, sino un método de cómo encontrar algo "bueno" $k$ (y tal vez así es como encontró $k=1805$ ).

Supongamos que para algunos $m$ ya sabemos que $$\tag1n^n+k\text{ is prime}\implies m\mid n.$$ Dejemos que $q$ sea un divisor primo de $k+1$ y supongamos que $q-1\mid m$ y $q\nmid m$ . Entonces $n^n+k$ sólo puede ser primo si $q\mid n$ . En efecto, en todos los demás casos tenemos (como podemos suponer $q-1\mid m\mid n$ ) $$n^n=\left(n^{q-1}\right)^{\frac n{q-1}}\equiv 1\pmod q$$ y así $q\mid n^n+k$ . Así, salvo en el caso trivial $k=q-1$ , $n=1$ vemos que $n^n+k$ no es primo. Se deduce que en $(1)$ podemos sustituir $m$ con $qm$ .

Inicialmente, $(1)$ se mantiene para $m=1$ No importa lo que suceda. $k$ que utilizamos. Por lo tanto, si $k+1$ es par, podemos usar lo anterior para mejorar esto a $m=2$ . Entonces con $q=3$ podemos mejorar esto a $m=6$ siempre y cuando $k\equiv -1\pmod 6$ . A continuación podemos utilizar $q=7$ para mejorar esto a $m=42$ proporcionó $k\equiv -1\pmod{42}$ . A continuación, utilizando $q=43$ a $m=1806$ proporcionó $k\equiv -1\pmod {1806}$ . Desgraciadamente, $1807=13\cdot 139$ no es primo y de hecho no hay ningún primo adicional $q$ con $q-1\mid 1806$ . Curiosamente, hemos reconstruido la secuencia finita OEIS A014117 a lo largo del camino. Pero parece que $k=1805$ es el mayor $k$ para lo cual podemos fácilmente demostrar que $(1)$ se mantiene con $m=k+1$ .