Un trivial pero el método no-trivial, sin embargo, tal vez de inferir primalidad

Question

El topologist J. H. C. Whitehead (que no debe confundirse con su famoso tío) dijo: es ingenuo pensar que un teorema es trivial, simplemente porque su prueba es trivial. Por lo tanto me pregunto si un determinado trivial proposición aparece en la literatura en algún lugar. Tal vez la mejor forma de estado es este: Si $p$ es el menor factor primo de $n$$p^3>n$, $n/p$ es primo.

Supongamos que yo estoy tratando de factor de $5497$ a mano. He descartado la divisibilidad entre todos los primos a través de $19$, y puedo hacer una división larga por $23$ y consigue $239$ como el cociente. Dado que todos los factores primos de a $5497$ debe ser de al menos $23$, e $23^3$ es claramente demasiado grande para ser $5497$, hay espacio para uno más en el primer factor, por lo que tengo a la conclusión de que el cociente, $239$, es primo.

Un estándar de paso en algoritmos estándar que aparecen en todos los libros de texto? O en algún otro lugar en fuentes publicadas?

Supongo que se podría decir que me he tácitamente descartó la divisibilidad de la $239$ por todos los números primos menos de $\sqrt{239}$, y por supuesto todo (?) libro menciona que, pero yo no estaba pensando en $239$ en el momento, y yo no podría haber llegado a mi conclusión, sin ir más allá de la raíz cuadrada de $239$ incluyendo $17$ $19$ en mi búsqueda.

Answer 1

Debe haber muchos ejemplos en la literatura de esta idea como un límite en el número de números primos en la factorización de $n$, dado el menor primo, o un límite inferior en el primer factores, pero probablemente hay muy pocos ejemplos en los que se presenta como una condición de primalidad, debido a la falta de naturales, casos de uso, donde uno desea comparar $p$ a un cubo de la raíz y no una raíz cuadrada.

En el ejemplo de la pregunta, el cociente $n/p$ es conocido antes de la comparación de $p^3$$n$. Cuando el cociente es conocido, las pruebas de $p^3 > n$ no es más fácil que $p^2 > (n/p)$ debido a que el error relativo es el mismo en las dos desigualdades, que sólo difieren por un factor de $p$. La calidad que se requiere de aproximación, o el costo de la computación, sería mayor para la multiplicación de tres veces en comparación con el doble.

Situaciones en las que el cociente no es conocido, pero $p > \sqrt[3]{n}$ es conocido por ser el más pequeño del primer factor, no son aparentes de inmediato. Por supuesto, se puede suponer, como en el ejercicio de Esmonde y Murty del libro, pero hay ejemplos en la naturaleza son más difíciles de encontrar.