Una conjetura: para todos los $n\in\mathbb{N}$, el mínimo de $k>1$ tal que $\phi(k)\geqslant n$ es un primer

Question

Me encontré con un problema en el libro que nos pidió para encontrar el primer número $n$ tal que $\phi(n)\geqslant 1,000$ resulta que la respuesta es de 1009, que es un número primo. Hubo varias preguntas de este tipo, y nuestro profesor conjeturó que siempre va a ser el próximo primer. Sin embargo, nadie ha sido capaz de llegar con una prueba de esta conjetura. Por lo tanto, más formalmente la conjetura es:

Para todos los $n\in\mathbb{N}$ el menor número positivo $k\in\mathbb{N}$, $k>1$ tal que $\phi(k)\geqslant n$ es un primo.

He trabajado con la función de Inversión de Möbius, y otro mínimo elemento contradictorio pruebas, pero nada ha funcionado hasta ahora. ¿Alguien tiene alguna idea buena?

Answer 1

Respuesta inicial: este debe seguir a partir de una muy leve conjetura en primer lagunas, que para un primer $p \geq 127,$ siempre hay un primer $q$ $p < q < p + \sqrt p.$ El último conocido malo es $113,$ $\sqrt {113} \approx 10.63,$ la suma es sobre $123.63,$, pero el primer presidente después de la $113$ $127.$ Las cosas que han sido probado de este tipo han exponentes ligeramente más grande, a continuación, $1/2,$ además de que suelen tener la condición de "grandes números suficientes," lo que significa que no puede invocar estos teoremas directamente por este problema. Edición, Komputer Kalkulation: para un primer $p \geq 2999,$ siempre hay un primer $q$ $p < q < p + \frac{1 }{2} \sqrt p \;;$ kalkulated para todos los $p \leq 1000000.$ Este ligeramente más fuerte conjetura (que es cierto para todos los $p \geq 2999$) implica la conjetura en la pregunta original muy directamente. Además, se puede ver en la Tabla de los primeros 75 que esta más fuerte conjetura tiene para todos los $ 4 \cdot 10^{18} \geq p \geq 9551,$ y a mi pequeño equipo de ejecución sólo se extiende a la 9551 abajo a 2999.

La razón de esto es relevante es la forma en que $\phi$ reduce los números. Mientras que $\phi(p) = p - 1, $ supongamos que tenemos un primer $r$ $r^2$ de un tamaño comparable al de $p.$ $\phi(r^2) = r^2 - r,$ que está más cerca de a $p - \sqrt p.$ Si $r^2 - r \geq N,$ pensamos que hay va a ser un $N < p < r^2.$ del mismo modo,para los números primos $r,s$ $rs \approx p,$ nos encontramos con que $\phi(rs)$ es aún más pequeña.

Así que, este es un muy razonable conjetura. Incluso podría haber una primaria de la prueba, difícil de decir.

EJERCICIO: si $M \geq 4$ es no prime, no se sigue que la $\phi(M) \leq M - \sqrt M?$ me voy a hacer un poco de equipo de ejecución.

Komputer Kalkulation: si $M \geq 4$ es no primo, entonces $\phi(M) \leq M - \sqrt M,$ y la igualdad sólo se aplica si $M = r^2$ primer $r.$

No debe ser difícil demostrar la Kalkulation. EDIT: sí, este es el significado de la primera muestra de la ecuación en la respuesta por mjqxxxx

Answer 2

Si $n$ no es primo, entonces se tiene un primer factor de $\le \sqrt{n}$, y así $$ \varphi(n) = n \prod_{p\;|\;n}\left(1-\frac{1}{p}\right)\le n\left(1-\frac{1}{\sqrt{n}}\right)=n-\sqrt{n}; $$ mientras que $\varphi(n)=n-1$ si $n$ es primo.

Así, fijará $M$. Deje $p$ ser el próximo primer número después de $M$, lo $\varphi(p)=p-1\ge M$; y deje $p'$ ser el más grande de los números primos $\le M$. (Es decir, $p$ $p'$ están al lado de los números primos.) Por último, supongamos que una composición $n < p$ también satisface $\varphi(n)\ge M$. Entonces $$ p-\sqrt{p}>n-\sqrt{n}\ge\varphi(n)\ge M \ge p', $$ o $$ p-p'\ge \sqrt{p}. $$ Si esto se sabe que nunca sucederá lo suficientemente grande para $p$ (es decir, si eventualmente $g_k < \sqrt{p_{k+1}}$ donde $p_k$ $k$- ésimo primo, y el primer gap $g_k\equiv p_{k+1}-p_{k}$), luego de su conjetura podría ser probada. Este es un fuerte conjetura (aunque casi cierto)... no creo que incluso se sabe a seguir a partir de la hipótesis de Riemann. Mirando la tabla de primer lagunas, sin embargo, hay muy pocos ejemplos en contra, y los únicos sustos para su conjetura son: $$ M=2 \qquad \varphi(3)=\varphi(4)=2; \\ M=6 \qquad \varphi(7)=\varphi(9)=6; \\ M=20 \qquad \varphi(23)=22; \varphi(25)=20; \\ M=110 \qquad \varphi(113)=112; \varphi(121)=110. $$

Answer 3

Un poco demasiado largo para un comentario.

Uno puede crear arbitrariamente larga serie de números enteros que no son primos. Deje $n \in \mathbb{N}$ y consideran que una serie de $n, n+1, \dots, n+r$ donde $n+r$ es el primer prime por encima de $n$. Supongamos que uno puede encontrar un número de $n+s$ $s < r$ $n+s = pq$ donde $p$ $q$ son números primos. Queremos elegir estos números, por lo que

$$\phi(n+s) = \phi(pq) = (p-1)(q-1) \geq n$$

Desde $pq = n+s$, esto significa $s+1 > p+q$ producirá un ejemplo contrario.

No está claro (para mí) de que esto es posible. Yo soy optimista porque la secuencia de $n, \dots, n+r$ puede hacerse arbitrariamente largas. Sin embargo, es claro que dicho contador de ejemplo construido de esta manera va a ser muy muy grande.