Presionando el sobre, presumiblemente el mejor escenario sería una simple demostración del Teorema de los Números Primos. Después de todo, el Teorema de Wilson da una condición necesaria y suficiente, en términos de la Función Gamma, para que un número sea primo, y la Fórmula de Stirling especifica el comportamiento asintótico de la Función Gamma.
Respuesta
¿Demasiados anuncios?
Utilizando la forma de Robbins [1] de la fórmula de Stirling,
$$\sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n+1))< n!< \sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n))$$
obtenemos
$$\left\lceil\sqrt{2\pi}(n-1)^{n-1/2}\exp(-n-1+1/(12n-11))\right\rceil$$ $$\le (n-1)!\le$$ $$\left\lfloor\sqrt{2\pi}(n-1)^{n-1/2}\exp(-n-1+1/(12n-12))\right\rfloor$$
que es lo suficientemente preciso como para distinguir entre primo y compuesto para $n\le8$ . Para números mayores, el límite de error es demasiado grande.
Esto puede ampliarse utilizando una modificación del teorema de Wilson: para n > 9, $$\lfloor n/2\rfloor!\equiv0\pmod n$$ si y sólo si n es compuesto. Esto permite probar del 10 al 15, más (con algo de ingenio) el 17.
Con límites explícitos más estrictos y una evaluación de alta precisión, podría ser posible probar hasta 100 con métodos relacionados: evaluación directa hasta 25 y la variante "dividir por 4" de la anterior para n > 25.
No se trata tanto de "usar un cañón para matar una mosca" (emplear métodos más potentes de lo necesario) como de "usar la estación espacial para matar una mosca": los métodos deben ser extremadamente potentes y precisos para hacer muy poco.
[1] H. Robbins, "A Remark on Stirling's Formula". The American Mathematical Monthly 62 (1955), pp. 26-29.
