El problema Internacional

Enunciado

Este es el problema internacional del mes. Tengamos en cuenta que se trata de un problema muy difícil. Vamos a poner muchos ejemplos de esta situación en una tabla, de forma que comprobemos que no se cumple en todos los casos, y tratar de buscar un patrón.

Número	Cota	Mayor primo	S/N
3	8	5	N
4	10	17	S
5	13	13	N
6	15	37	S
7	17	5	N
8	20	13	N
9	22	41	S
10	24	101	S
11	26	61	S
12	28	29	S
13	31	17	N
14	33	197	S
15	35	113	S
16	37	257	S
17	39	29	N
18	42	13	N
19	44	181	S
20	46	401	S
21	48	17	N
22	50	97	S
23	52	53	S
24	54	577	S
25	57	313	S
26	59	677	S
27	61	73	S
28	63	157	S
29	65	421	S
30	67	53	N
31	69	37	N

Pruebas para el problema

Está conjeturado que hay infinitos primos de la forma n² + 1, pero no está probado, de forma que es evidente que no se puede utilizar este resultado. Sin embargo, es evidente que si el número n cumple esta condición, el primo es más grande que la cifra pedida, siempre que n sea mayor que 2.

Hay un resultado que puede o no ser conocido, que es que todo primo que pertenece a la descomposición de n² + 1 o es 2, o es de la forma 4k + 1. Además, todo primo de la forma 4k + 1 pertenece a la descomposición de n² + 1 para algún n. Estos resultados, si bien dan lugar a distintas vías de solución del problema, no son imprescindibles para su solución, como veremos.

También es conocido, aunque no fácil de probar, que hay infinitos primos de la forma 4k + 1 (en general, hay infinida de primos en toda sucesión de la forma ak + b, para a y b primos entre sí). De nuevo, esto da lugar a interesantes vías de solución, aunque ninguna de ellas es imprescindible.

Ahora bien, si miramos con atención la tabla, hay algo que llama la atención. Aunque siguiéramos calculando para números mayores, no hay, aparentemente, una sucesión de valores para los que se cumpla, pero cuando no se cumple, siempre hay un valor anterior en el que ese primo salía y sí se cumplía, excepto para los primos 13 y 5. Esta circunstancia es muy difícil de apreciar con pocas muestras, de forma que tal vez sea conveniente disponer de una amplia selección.

Una vez que hemos dado con una intuición que nos permita trabajar, vamos a probar la existencia de infinitos números n como los que nos piden.

Vamos a dar un primer paso: supongamos que tomamos un p cualquiera, primo mayor que 20 (para que luego podamos aplicar una desigualdad con comodidad), y que divide a un cierto número k = m² + 1 para un número natural m. Veamos que existe un valor n que cumple que n es menor que p/2 y p también es un divisor de n² + 1.

Bueno, está claro que si m > p y p divide a m² + 1, también divide a (m - p)² + 1 = m² + 1 + 2p + p², de forma que podemos encontrar, bajando poco a poco, un valor m₁ que cumpla las condiciones de que m₁ < p y que p divide a m₁² + 1.

Ahora bien, si m₁ < p/2, tomamos n = m₁, y en caso contrario, p/2 < m₁ < p, tomamos n = p - m₁. Está claro que 0 < n < p/2, y p divide a n² + 1 = (p - m₁)² + 1 = p² - 2p + m₁² + 1. En cualquier caso, tenemos ese valor n.

Ahora, vamos con el segundo paso: para todo p, dado el n encontrado antes con esas dos condiciones, tenemos que p > 2n + √2n.

Llamemos ahora k al número p - 2n (nuestro objetivo es ver que es mayor que √2n). Tenemos que n = (p - k)/2 y que p divide a (p - k)²/4 + 1 = ((p - k)² + 4)/4. Luego p divide al denominador, a (p - k)² + 4 = p² - 2p + k² + 4. Por tanto, p divide a k² + 4. Eso quiere decir que k² + 4 es mayor que p, por lo que k es mayor que √(p - 4). Claro, que p - 4 = 2n + k - 4 > 2n + √(p - 4) - 4. Observamos que √(p - 4) es mayor que 4 siempre que p sea mayor que 20, de forma que (p - 4) > 2n, y resulta que p = 2n + k > 2n + √2n, como se quería ver.

Parece que ya estamos cerca, pero falta un paso más. ¿Hay infinitos n con esta condición? Veamos que así es.

Supongamos que no hay infinitos n que cumplan esta condición. Por ello, el conjunto de primos que dividen a los números de la forma n² + 1 también es finito (ya que si fuese infinito, habría una cantidad infinita de p, y por tanto de n, que cumplen esta condición, ya que recordemos que p divide siempre a un n² + 1 que cumple esta condición de cota). Ahora bien, tomemos m el producto finito de los primos p que dividen a los números de la forma n² + 1. El número m² + 1 es primo con m, ya que su número anterior es múltiplo de m, y por tanto sus factores primos no pertenecen al conjunto de todos los factores primos de los números de la forma n² + 1, siendo de la forma m² + 1. Lo cual es absurdo.

Por tanto concluimos que el enunciado es cierto.