Demostrar que $n^2+n+41$ es primordial para $n<40$

Question

Aquí hay un problema que apareció en un examen que hice, me interesa ver si hay otras formas de enfocarlo.

Dejemos que $n\in\{0,1,...,39\}$ . Demostrar que $n^2+n+41$ es primo.

Voy a dar mi propia solución, aunque tengo curiosidad por saber si alguien sabe cómo hacerlo sin usar PIDs.

Answer 1

Desde $4(n^2+n+41)=(2n+1)^2+163$ Una forma sería demostrar metódicamente que $-163$ es un cuadrático no -residuo mod todos (impar) primos menos que $41$ .

Añadido más tarde : El operador ha pedido más detalles, así que aquí va.

Si $p\mid n^2+n+41$ entonces $(2n+1)^2+163\equiv0$ mod $p$ lo que significa que $-163$ es un cuadrado mod $p$ . Ahora los valores de $n^2+n+41$ para $n\lt40$ son todos menores que $40^2+40+41=1681$ por lo que si alguno de ellos fuera compuesto, tendría que tener un factor primo menor que $\sqrt{1681}=41$ . Ese factor principal tendría que ser impar, ya que está claro que $n^2+n+41$ es siempre impar. Esto requeriría $-163$ sea un residuo cuadrático para algún primo impar menor que $41$ . Por tanto, basta con calcular el símbolo de Legendre $({-163\over p})$ para $p=3,5,7,11,13,17,19,23,29,31$ y $37$ y demostrar que es $-1$ en cada caso.

Esto es un poco tedioso, pero menos que comprobar directamente la primalidad del $39$ números $(1^1+1+41), (2^2+2+41),\ldots,(39^2+39+41)$ . Por ejemplo,

$$\left({-163\over17}\right)=\left({7\over17}\right)=\left({17\over7}\right)=\left({3\over7}\right)=-\left({7\over3}\right)=-\left({1\over3}\right)=-1$$

donde la cadena de igualdades hace uso (dos veces) de la Ley de reciprocidad cuadrática .

Answer 2

Lo demostraremos utilizando el PID $R:=\mathbb{Z}[\omega]$ , donde $\omega=\frac{1+i\sqrt{163}}{2}$ con la norma $N(a+b\omega)=|a+b\omega|^2=a^2+ab+41b^2$ .

Lema 1: Si $p$ es primo en $\mathbb{Z}$ tal que $\exists n\in\mathbb{Z}$ tal que $p|n^2+n+41$ entonces $p$ es reducible en $R$ .

Prueba: Dejemos que $p|n^2+n+41$ y asumir $p$ es irreducible. Entonces $p$ también es primo, ya que $R$ se sabe que es un PID. Así, $p|(n+\omega)(n+\overline{\omega})\Rightarrow p|n+\omega$ ou $p|n+\overline{\omega}$ . La primera no tiene sentido ya que los múltiplos de $p$ son de la forma $ap+bp\omega$ por lo que esto obligaría a $p$ para ser una unidad en $\mathbb{Z}$ . Pero lo segundo también es imposible ya que $n+\overline{\omega}=n+1-\omega$ .

Lema 2: Si $p$ es primo en $\mathbb{Z}$ entonces $p$ es reducible en $R$ si $\exists a,b\in\mathbb{Z}$ tal que $p=a^2+ab+41b^2$

Prueba: Dejemos que $p$ sea reducible. Entonces $p=\alpha\beta\Rightarrow p^2=N(p)=N(\alpha\beta)=N(\alpha) N(\beta)\Rightarrow p=N\alpha=N\beta$ . Para la otra dirección, dejemos $p=a^2+ab+41b^2$ y asumir que es irreducible, por lo que $p=(a+b\omega)(a+b\overline{\omega})$ . Desde $p$ es irreducible, una de ellas tiene norma $1$ . Pero estos tienen claramente la misma norma, entonces $N(p)=1$ que es imposible.

Prueba del teorema: Dejemos que $m=n^2+n+41$ y asumir $m$ no es primo. Entonces existen primos $p,q\in\mathbb{N}$ tal que $\frac{m}{pq}\in\mathbb{N}$ . Por lo tanto, según el lema 1, $p,q$ son reducibles en $\mathbb{Z}[\omega]$ y por lo tanto por el Lemma 2 son de la forma $p=a^2+ab+41b^2$ y $q=c^2+cd+41d^2$ . Observe que $b^2d^2>0$ ya que si $b=0$ entonces $p=a^2\Rightarrow p$ no es primo. De la misma manera, para $d$ . WLOG $a>0$ . Entonces, o bien $a^2+ab>0$ en cuyo caso tenemos $$pq\leq m<41^2\leq (a^2+ab+41b^2)(c^2+cd+41d^2)=pq$$ ou $a<-b$ en cuyo caso tenemos $$41\leq a^2+40b^2\leq a^2+ab+41b^2=p$$ como ninguno $a$ ni $b$ puede ser cero.

Answer 3

Teorema $ $ El polinomio $\rm\, f(x) = (x\!-\!\alpha)\,(x\!-\!\alpha') = x^2 + x + k\, $ asume sólo valores primos para $\rm\ 0 \le x \le k-2 \iff \mathbb Z[\alpha]\ $ es un PID.

Sugerencia $\ (\Rightarrow)\ $ Mostrar todos los primos $\rm\ p \le \sqrt{n},\; n = 1\!-\!4k\,$ tienen $\rm\, (n/p) = -1\, $ así que no hay primos divididos/ramificados.

Para las pruebas, véase, por ejemplo, Cohn, Teoría avanzada de los números , pp. 155-156, o Ribenboim, Mis números, mis amigos , 5.7 p.108. Nota: ambas pruebas emplean el límite $\rm\ p < \sqrt{n}\ $ sin mencionar explícitamente que se trata de una consecuencia del límite de Minkowski -suponiendo, presumiblemente, que es obvio para el lector basándose en los resultados anteriores. Por lo tanto, tendrá que leer las secciones anteriores sobre el límite de Minkowski. Compara Stewart y Tall, Teoría algebraica de los números y FLT , 3ed, Teorema 10.4 p.176 donde se menciona explícitamente el uso del límite de Minkowski.

Como alternativa, consulte la página web autónoma papel [1] que procede de forma un poco más sencilla, empleando la aproximación Dirichlet para obtener una generalización del algoritmo euclidiano (el criterio Dedekind-Rabinowitsch-Hasse para un PID). Si la memoria no me falla, esto se aproxima al enfoque empleado originalmente por Rabinowitsch cuando publicó por primera vez este teorema en 1913.

[1] Daniel Fendel, Polinomios productores de primos y dominios ideales principales,
Revista de Matemáticas, Vol. 58, 4, 1985, 204-210

Answer 4

A continuación, el problema $\rm 6\ (B3)$ de la OMI $1987$ y su solución (de AoPS o Scholes )

Teorema . Si $k^2+k+n$ es primo para todos los enteros $k$ tal que $0\le k\le \sqrt\frac{n}{3}$ entonces $k^2+k+n$ es primo para todos los enteros $0\le k\le n-2$ .

Prueba . Primero observe que si $m$ es relativamente primo de $b+1$ , $b+2$ , $\cdots$ , $2b$ entonces $m$ es relativamente primo de cualquier número menor que $2b$ . En efecto, si $c\leq b$ , entonces podemos elegir algún $i$ para hacer $2^ic$ se encuentra en el rango $b+1,b+2,\cdots,2b$ Así que $2^ic$ es relativamente primo de $m$ . Por lo tanto, $c$ también es un primo. Si también tenemos $(2b+1)^2>m$ entonces podemos concluir que $m$ es un primo, de lo contrario debe haber un factor de $m$ menos de $\sqrt{m}$ .

Dejemos que $n=3r^2+h$ donde $0\leq h<6r+3$ Así que $r$ es el mayor número entero menor o igual que $\sqrt{n/3}$ . (para ver esto, basta con dejar $r=\lfloor\sqrt{n/3}\rfloor$ entonces podemos escribir $n=3(r+\epsilon)^2(0\leq\epsilon< 1)$ Así que $h=6r\epsilon+3\epsilon^2\leq 6r+3$ ).

Supongamos que $n+k(k+1)$ es primordial para $k=1,2,3\cdots,r$ . Demostramos que $N=n+(r+s)(r+s+1)$ es primordial para $s=0,1,2,\cdots,n-r-2$ . Por nuestra observación anterior, basta con demostrar que $(2s+2r+t)^2>N$ y $N$ es relativamente primo a todos los $r+s+1,r+s+2,\cdots,2r+2s$ . Tenemos $(2r+2s+1)^2=4r^2+4s^2+8rs+4r+4s+1$ . Desde $s,r\ge1$ tenemos $4s+1>s+2$ , $4s^2>s^2$ y $6rs>3r$ . Por lo tanto, $$(2s+2r+1)^2>4r^2+2rs+s^2+7r+s+2=3r^2+6r+2+(r+s)(r+s+1)\ge N.$$ Ahora bien, si $N$ tiene un factor que divide $2r-i$ en el rango $-2s$ a $r-s-1$ entonces también lo hace $N-(i+2s+1)(2r-i)=n+(r-i-s-1)(r-i-s)$ que tienen la forma $n+s'(s'+1)$ con $s'$ en el rango $0$ a $r$ .