Olimpiadas matemáticas II

A ver si resucito este blog ahora que vuelvo a tener algo de tiempo libre...

Un tal Harazi encontró una solución especialmente breve para el problema de la entrada anterior.

Como los enlaces dejan de funcionar con una facilidad pasmosa, repito aquí el argumento de Harazi. Empieza tomando un primo p tal que p-1 sea múltiplo de 4. Entonces p divide a algún número de la forma n²+1. La gracia está en ver que n puede ser pequeño; en concreto, podemos suponer que n<p/2, simplemente porque si p divide a n²+1 entonces también divide a (p-n)²+1. Sea k=p-2n>0; entonces p divide a 4(n²+1)=(p-k)²+4, de forma que también divide a k²+4 y por tanto k≥raiz(p-4). Por tanto, p=2n+k≥2n+raiz(p-4) y ya casi hemos acabado; para obtener la desigualdad final, p≥2n+raiz(p-4)≥2n+raiz(2n+raiz(p-4)-4), que es mayor que 2n+raiz(2n) si p es suficientemente grande.

Otras páginas relacionadas con este problema (encontradas por Roberto): solución 2 comentarios otro problema parecido.