Mostrar Mensajes

Esta sección te permite ver todos los posts escritos por este usuario. Ten en cuenta que sólo puedes ver los posts escritos en zonas a las que tienes acceso en este momento.

Temas - sqrmatrix

Páginas: [1]
1
Saludos a todos.

Hace tiempo abrí un hilo con el mismo título que éste, y pretendía mostrar una serie de propiedades y características del método de factorización de Hugo Scolnik que me parecían interesantes. A medida que lo iba desarrollando, me iban surgiendo nuevas ideas, hasta que llegó un punto en el que las nuevas ideas eran demasiadas, y algunas un poco largas de desarrollar, y yo no tenía tiempo y/o ganas de desarrollarlas en ese momento. Así que poco a poco fui dejando de publicar nuevas entradas, hasta que al final interrumpí la publicación de ese hilo. Este hilo se encuentra en:

http://rinconmatematico.com/foros/index.php?topic=97062.0

En todo este tiempo, de vez en cuando, he ido escribiendo todas las ideas que me iban surgiendo sobre este tema en un documento escrito en \( \LaTeX \). Al final, el documento se ha hecho bastante grande, y no he terminado de desarrollar todas las ideas que tengo pendientes. Pero creo que es lo suficientemente interesante para publicarlo ya.

El documento es bastante extenso, y seguro que aburrirá a más de uno :). Seguramente también tendrá numerosos errores. Agradecería que todos los comentarios, sugerencias, discusiones, aclaraciones, avisos de errores, etc, se hicieran en el otro hilo (en la URL dada arriba) para dejar este hilo limpio, para que las correcciones que publique y los nuevos desarrollos que añada queden a la vista a cualquiera que quiera consultarlo, sin tener que andar explorando todo el hilo en busca de las últimas actualizaciones de los documentos.

No publico el documento como entradas en el hilo por ser demasiado extenso. Todavía me faltan ideas que desarrollar, pero las iré desarrollando poco a poco, cuando tenga tiempo y ganas, y cuando tenga suficiente material para publicar, añadiré una nueva entrada con el documento con el nuevo material. Igualmente, las correcciones las iré publicando en nuevos documentos.

2
Esto que voy a explicar ya lo publiqué en otro foro, hace años, pero ese otro foro ya cerró. Lo he modificado un poco para que se entienda mejor, y he añadido algunas cosas nuevas. Tenía pensado publicarlo en un solo post, pero he ido añadiendo cosas nuevas que han ido surgiendo a medida que iba repasando lo que ya tenía, y se ha alargado demasiado. Así que lo publicaré en varios posts, ya que me parece más fácil de leer. Además, todavía tengo cosas pendientes que añadir, que iré publicando en post sucesivos.

Para entender lo que voy a explicar, conviene leer los documentos de Hugo Scolnik, que se pueden encontrar en los siguientes enlaces:

Un trabajo del 2007: http://www.criptored.upm.es/descarga/Avances_en_la_factorizacion_entera.pdf

Un trabajo del 2008: http://campus.usal.es/~xrecsi/Imagenes/conferenciantes/Scolnik.pdf

Un trabajo del 2011: http://www.40jaiio.sadio.org.ar/sites/default/files/T2011/WSegI/834.pdf

Estos documentos son bastante breves y fáciles de entender (el último es un poco más extenso). Basta con leer el primero para entender lo que voy a exponer.

También hay un vídeo en el que da una conferencia explicando su método:

https://www.youtube.com/watch?v=Zrd8tM_1Pnk

En estos documentos se habla de un algoritmo de factorización en tiempo polinómico que estaba desarrollando Hugo Scolnik.

Lo primero que hay que indicar, antes de empezar a explicar, es que de momento el método de factorización de Hugo Scolnik no permite factorizar grandes enteros de forma rápida. El método fue presentado en el año 2007 (o quizá antes), y desde entonces no se han visto avances, ni se encuentra casi información del mismo en Internet, lo que lleva a pensar que no se ha podido desarrollar para permitir factorizaciones rápidas de grandes enteros (o a lo mejor sí, y lo mantienen en secreto :)).

Y dicho esto, empiezo con el resumen de lo que voy a explicar.

Resumen

Como todavía tengo cosas pendientes que revisar, seguramente añada más adelante cosas que no se reflejen en este resumen. De momento, resumo lo que ya tengo listo para añadir.

Primero explicaré el fundamento del resto de lo que voy a exponer. Es un poco lo que Hugo Scolnik explicó en sus trabajos, para entender lo que voy a exponer.

Definiré lo que denomino como target válido, target no válido, target correspondiente a una diferencia de cuadrados, y target trivial.

Explicaré unos algoritmos para determinar si un entero tiene target único módulo \( \displaystyle c \), a pesar de no ser necesario debido a la limitación del valor de \( \displaystyle c \) a \( \displaystyle 1440 \), como indica Hugo Scolnik en sus trabajos, para que puedan existir targets únicos, ya que podría comprobarse de forma exhaustiva rápidamente.

Explicaré la composición de targets, y cómo afectan a la composición los targets únicos, los targets válidos, y los targets no válidos.

Mostraré un caso especial de target, que es aquel target válido cuyo módulo es mayor que el menor de los cuadrados de la expresión de un entero como diferencia de cuadrados. Explicaré el fundamento de un algoritmo de factorización basado en esta idea, y mostraré el algoritmo en pseudocódigo, con un ejemplo de factorización (el algoritmo no permite factorizar grandes enteros por las limitaciones de los targets únicos :(). Por último, mostraré una optimización de este algoritmo.

Explicaré un poco el límite de \( \displaystyle 1440 \) en los módulos que pueden tener target único.

Hablaré del problema que suponen los targets múltiples a la hora de factorizar un entero con el algoritmo presentado antes.

Definiré lo que denomino como target trivial solapado, mostraré cómo calcular los módulos máximos (que sean máximos es una conjetura) para los que existen estos targets conociendo la factorización del entero, y presentaré una serie de conjeturas sobre estos targets, conjeturas que parecen ciertas por las pruebas que he realizado (todavía tengo que revisar estas conjeturas, para ver si se me ocurre cómo demostrarlas, o ver si encuentro algún contraejemplo, aunque las he comprobado con millones de enteros y todavía no he encontrado contraejemplos).

Hablaré de cómo determinar algunos divisores de la suma y la diferencia de los divisores de un entero con los targets únicos, cálculo extensible a cualquier target válido.

Finalmente, hablaré de los enteros cuyos targets son todos válidos módulo algún \( \displaystyle c \). Esto todavía lo estoy estudiando, pues me lo encontré casi de casualidad (pensaba que si un entero no tenía targets únicos módulo \( \displaystyle c \), tendría algún target no válido, pero resulta que no siempre ocurre esto).

Cualquier otra cosa que me encuentre la añadiré en sucesivos posts.

Notas preliminares

En lo que sigue, todas las variables, si no se dice otra cosa, cumplirán las siguientes condiciones:

- Los valores de las variables serán enteros mayores o iguales a \( \displaystyle 0 \).
- La variable \( \displaystyle n \) hace referencia al entero que se quiere factorizar, que será impar y, por tanto, expresable como diferencia de cuadrados, y puede ser primo o compuesto.
- La variable \( \displaystyle c\ge 2 \) hace referencia al módulo de las congruencias de los targets.
- Las variables \( \displaystyle p \) y \( \displaystyle q \) hacen referencia a valores primos.
- Las variables \( \displaystyle a \), \( \displaystyle b \), \( \displaystyle r \), \( \displaystyle s \), y cualquier otra, hacen referencia a cualquier valor, que puede ser primo o compuesto.
- Todo lo anterior también aplica si las variables tienen subíndices, o primas.

A menudo se verá expresado \( \displaystyle n \) como producto de dos enteros, o como diferencia de dos cuadrados. Para simplificar, y no estar continuamente diciendo que un entero es menor que otro, en estas expresiones el orden alfabético de los pares de variables indica también el orden de sus valores. Así, en las expresiones \( \displaystyle n=r\cdot s \), \( \displaystyle n=p\cdot q \), \( \displaystyle n=b^2-a^2 \), se considerará que \( \displaystyle r\le s \) \( \displaystyle p\le q \), \( \displaystyle a\le b \). En otras expresiones, sobre todo en congruencias, no habrá necesariamente tal orden, y si lo hay, se indicará explícitamente.

A la hora de escribir targets, se podrán expresar con cuadrados explícitos (esto es, de la forma \( \displaystyle n+a^2\equiv b^2\pmod{c} \)), o con cuadrados implícitos (esto es, de la forma \( \displaystyle n+a\equiv b\pmod{c} \), donde se entenderá que \( \displaystyle a \) y \( \displaystyle b \) son cuadrados módulo \( \displaystyle c \)). En este último caso, se mencionará que la expresión es un target para evitar confusiones.

Las formas \( \displaystyle n=b^2-a^2 \) y \( \displaystyle n+a^2=b^2 \), que son equivalentes, las llamaré indistintamente como 'diferencia de cuadrados de \( \displaystyle n \)', a pesar de que la segunda expresión no muestra directamente una diferencia de cuadrados.

3
Lo que voy a escribir aquí surgió como idea de otro hilo:

http://rinconmatematico.com/foros/index.php?topic=93551.0

A su vez, seguiré un razonamiento muy parecido al que seguí para los primos equidistantes, que está en este otro hilo:

http://rinconmatematico.com/foros/index.php?topic=92097.0

Lo primero que tenemos que hacer es definir qué entendemos por polinomio generador de primos. Diremos que el polinomio \( \displaystyle a+b\cdot x+c\cdot x^2+d\cdot x^3+... \) es un polinomio generador de primos si existe un valor de \( \displaystyle x \), que denotaremos como \( \displaystyle x_0 \), tal que el valor del polinomio cuando \( \displaystyle x=x_0 \) da como resultado un número primo, y también da como resultado un número primo para \( \displaystyle x=x_0+1,x_0+2,x_0+3,... \). Al menos, debe dar como resultado un número primo para \( \displaystyle x=x_0+1 \). Es decir, debe dar al menos dos primos para dos valores consecutivos de \( \displaystyle x \). Los primos generados podrán, o no, repetirse.

Al conjunto de primos generado por este polinomio lo llamaremos cadena de primos generada por el polinomio (o, para este contexto, simplemente cadena de primos).

Hay que tener en cuenta que, normalmente, las cadenas de primos generadas por el polinomio no serán primos consecutivos dado que normalmente el polinomio crecerá rápidamente, más que los números primos en los enteros. Es decir, que si \( \displaystyle x_0 \) y \( \displaystyle x_0+1 \) generan los primos \( \displaystyle p \) y \( \displaystyle q \), puede que entre \( \displaystyle p \) y \( \displaystyle q \) haya otros primos, o no.

Dado un polinomio \( \displaystyle a+b\cdot x+c\cdot x^2+d\cdot x^3+... \), nos preguntamos por la máxima longitud de la cadena de primos que podrá generar.

Sea \( \displaystyle x_0 \) el valor con el que comienza la generación de la cadena de primos. Queremos determinar el máximo valor de \( \displaystyle i \) para el que los enteros \( \displaystyle x_0, x_0+1, x_0+2, ..., x_0+i \) pueden generar primos, y además, \( \displaystyle x_0+i+1 \) genera un compuesto.

Para que el polinomio genere primos para los valores comprendidos entre \( \displaystyle x_0 \) y \( \displaystyle x_0+i \), tiene que ocurrir que todos esos valores no sean divisibles por ningún primo menor que los valores generados. En particular, no deben ser divisibles por los primos \( \displaystyle 2,3,5,7,11,... \), salvo que esos propios primos sean los que genera el polinomio. Esto significa que tiene que cumplirse \( \displaystyle a+b\cdot (x_0+t)+c\cdot (x_0+t)^2+d\cdot (x_0+t)^3+...\not\equiv 0\pmod{\{2,3,5,7,11,...\}} \).

Consideremos uno de los primos \( \displaystyle q \) para los que tiene que cumplirse \( \displaystyle a+b\cdot (x_0+t)+c\cdot (x_0+t)^2+d\cdot (x_0+t)^3+...\not\equiv 0\pmod{q} \). ¿Qué ocurre cuando \( \displaystyle x_0+t\equiv 0\pmod{q} \)?. En este caso, tenemos que se cumplirá que \( \displaystyle r\cdot (x_0+t)^s\equiv 0\pmod{q} \) para todo \( \displaystyle r \) y para todo \( \displaystyle s \). Es decir, que en esas condiciones, tenemos que se cumple \( \displaystyle a+b\cdot (x_0+t)+c\cdot (x_0+t)^2+d\cdot (x_0+t)^3+...\equiv a\pmod{q} \) al ser todos los términos del polinomio, salvo el término independiente, congruentes con \( \displaystyle 0 \) módulo \( \displaystyle q \).

Si resulta que \( \displaystyle a \) no es primo, cuando \( \displaystyle x_0+t\equiv 0\pmod{q} \), el polinomio generará un múltiplo de \( \displaystyle q \) y, por tanto, no será primo, lo que marca el límite máximo para la cadena de primos generada por el polinomio empezando por el valor \( \displaystyle x_0 \). Esto significa que la máxima longitud posible de la cadena será el número de valores que hay entre \( \displaystyle x_0 \) y el valor anterior al siguiente múltiplo de \( \displaystyle q \). Esto no nos garantiza que exista tal cadena de primos. Sólo nos garantiza que la cadena no tendrá una longitud mayor.

Ahora nos preguntamos por el menor primo \( \displaystyle q \) que cumple lo anterior. Se puede determinar fácilmente. Siendo \( \displaystyle a \) compuesto, podemos expresarlo como \( \displaystyle a=q\cdot a' \), donde \( \displaystyle q \) es el menor primo que divide a \( \displaystyle a \). Este \( \displaystyle q \) es precisamente el valor que buscamos. En el mejor de los casos, la cadena de primos más larga la podemos obtener partiendo de \( \displaystyle 1\pmod{q} \), hasta \( \displaystyle q-1\pmod{q} \). La longitud de la cadena sería de \( \displaystyle q-1 \) primos. Como antes, esto no nos garantiza que exista tal cadena. Simplemente nos dice que si \( \displaystyle a \) es compuesto, la máxima longitud posible de la cadena de primos será una unidad menor que el valor del primo más pequeño que divida a \( \displaystyle a \).

Visto esto, veamos ahora qué ocurre cuando \( \displaystyle a \) es primo. Sea \( \displaystyle q \) este primo. Siguiendo el mismo razonamiento que antes, vemos que, cuando \( \displaystyle x_0+t\equiv 0\pmod{q} \), el valor del polinomio es divisible por \( \displaystyle q \). Pero puesto que \( \displaystyle q \) es primo, puede ocurrir que el valor generado por el polinomio sea precisamente ese valor \( \displaystyle q \), con lo cual, seguiría generando un primo. Esto ocurre en particular cuando \( \displaystyle x_0+t=0 \), ya que en este caso, tendríamos \( \displaystyle q+b\cdot (0)+c\cdot (0)^2+d\cdot (0)^3+...=q \). Observemos que no estamos diciendo que \( \displaystyle x_0+t\equiv 0\pmod{q} \), sino que estamos diciendo que \( \displaystyle x_0+t=0 \).

Este no es necesariamente el único caso en el que el polinomio da como resultado el valor \( \displaystyle q \). Este valor lo dará cuando \( \displaystyle b\cdot x+c\cdot x^2+d\cdot x^3+...=0 \). El número de veces que puede ocurrir esto es el número de soluciones de la igualdad, y sabemos que este número de soluciones es, como máximo, el mismo que el grado del polinomio. Además, estas soluciones deben ser enteras para ser aplicables a este problema. Una de esas soluciones sabemos que es \( \displaystyle 0 \). Más adelante veremos las condiciones que tienen que cumplir estas soluciones para poder generar una cadena de primos más larga.

Veamos ahora la longitud máxima de la cadena de primos que se puede generar con el polinomio. Si \( \displaystyle x_0=0 \), el polinomio dará como resultado el primo \( \displaystyle q \), por lo visto antes. Y también, por lo visto antes, para \( \displaystyle x_0+t \), con \( \displaystyle t \) comprendido entre \( \displaystyle 1 \) y \( \displaystyle q-1 \), es posible (pero no es seguro) que los valores generados por el polinomio sean primos. Pero cuando \( \displaystyle t=q \), tenemos la seguridad de que el valor generado por el polinomio será divisible por \( \displaystyle q \). ¿Es posible que el polinomio genere el propio valor \( \displaystyle q \)?. La respuesta es que sí es posible. Como vimos antes, si \( \displaystyle b\cdot x+c\cdot x^2+d\cdot x^3+...=0 \), entonces el polinomio genera el valor \( \displaystyle q \), que es primo. Y para que esto ocurra, tiene que cumplirse que \( \displaystyle x_0+q \) sea solución de la igualdad. Si se cumple esto, entonces, como antes, existe la posibilidad (pero no la seguridad) de que para los valores comprendidos entre \( \displaystyle x_0+q+1 \) y \( \displaystyle x_0+q+q-1=x_0+2\cdot q-1 \) el polinomio genere valores primos. Y para \( \displaystyle x_0+2\cdot q \), estamos en la misma situación que antes. Para que el valor generado por el polinomio sea primo, debe dar como resultado el propio valor \( \displaystyle q \), y esto sólo es posible si la igualdad \( \displaystyle b\cdot x+c\cdot x^2+d\cdot x^3+...=0 \) tiene como solución el valor \( \displaystyle x_0+2\cdot q \). Repitiendo este razonamiento, llegamos al último caso posible. Como la igualdad tiene tantas soluciones como grado tiene el polinomio, si \( \displaystyle g \) es el grado del polinomio, tenemos que, en el mejor de los casos, la igualdad \( \displaystyle b\cdot x+c\cdot x^2+d\cdot x^3+...=0 \) tiene como soluciones los enteros \( \displaystyle \{0,q,2\cdot q,3\cdot q,...,(g-1)\cdot q\} \), y además, para todos los valores distintos entre \( \displaystyle 0 \) y \( \displaystyle g\cdot q-1 \), el polinomio genera primos (para \( \displaystyle g\cdot q \) no generará un valor primo, pues no es solución de la igualdad \( \displaystyle b\cdot x+c\cdot x^2+d\cdot x^3+...=0 \), con lo que no generará el valor \( \displaystyle q \), sino un múltiplo del mismo, a raíz del hecho de que se cumple \( \displaystyle q+b\cdot (g\cdot q)+c\cdot (g\cdot q)^2+d\cdot (g\cdot q)^3+...\equiv 0\pmod{q} \), es decir, el polinomio genera un múltiplo del primo \( \displaystyle q \), pero no es el mismo primo \( \displaystyle q \), con lo cual, debe ser un compuesto).

Pero se nos ha olvidado un tramo en la anterior cadena. Este tramo parte del valor \( \displaystyle x_0=-q+1 \), ya que en este tramo puede no haber divisores de \( \displaystyle q \) y, por tanto, pueden ser primos. Con esto, es fácil ver que si las soluciones de la igualdad \( \displaystyle b\cdot x+c\cdot x^2+d\cdot x^3+...=0 \) van desde valores negativos a valores positivos (o incluso si la mayor solución es \( \displaystyle 0 \)), esto no afecta a la longitud de la cadena de primos generada.

Como nota sobre lo anterior, no es necesario que \( \displaystyle x_0=0 \) forme parte del conjunto de soluciones a distancia \( \displaystyle q \) de la anterior o de la siguiente para generar la cadena de primos. Podemos partir de cualquier valor. Sin embargo, la máxima longitud posible de la cadena se reducirá en \( \displaystyle q \) términos, ya que \( \displaystyle x_0=0 \) es una solución de la igualdad \( \displaystyle b\cdot x+c\cdot x^2+d\cdot x^3+...=0 \), y que hemos descartado, así como el tramo anterior. El mejor de los casos para esta condición es cuando el resto de soluciones de la igualdad son \( \displaystyle \{r\cdot q,(r+1)\cdot q,(r+2)\cdot q,...,(r+g-1)\cdot q\} \). En este caso, la máxima longitud de la cadena de primos se dará cuando el polinomio genere primos desde el valor \( \displaystyle r\cdot q-q+1=(r-1)\cdot q+1 \), hasta el valor \( \displaystyle (r+g-1)\cdot q \), que en total son tantos valores como antes, menos el correspondiente a la solución \( \displaystyle 0 \) y el tramo anterior a la misma, es decir, menos \( \displaystyle q \).

Aquí llegamos a la conclusión de que el número máximo posible para una cadena de primos generada por un polinomio de grado \( \displaystyle g \) con término independiente un primo \( \displaystyle q \) será de, como mucho, \( \displaystyle g\cdot q+q-1=(g+1)\cdot q-1 \) (hemos añadido el tramo que hay antes de la primera solución, y se lo hemos sumado al número de tramos de cada solución). Como antes, esto no nos garantiza que existan cadenas de esta longitud, sólo nos garantiza que no existen cadenas de longitud mayor. Además, esta longitud sólo es posible si todas las soluciones de la igualdad \( \displaystyle b\cdot x+c\cdot x^2+d\cdot x^3+...=0 \) son equidistantes a distancia \( \displaystyle q \) (una de esas soluciones siempre será \( \displaystyle 0 \) para que el número de soluciones sea máximo). Si no, la longitud de la cadena de primos será menor. En particular, si \( \displaystyle r \) es el máximo número de soluciones equidistantes a distancia \( \displaystyle q \), la máxima longitud posible de la cadena de primos será de \( \displaystyle (r+1)\cdot q-1 \).

El problema de estas cadenas que hemos encontrado es que, si son de longitud mayor que \( \displaystyle q \), siempre hay primos que se repiten (que su longitud sea menor no garantiza que no haya primos repetidos). En particular, el primo \( \displaystyle q \) se repetirá. Es fácil ver que, si queremos una cadena de primos sin que se repitan, la máxima longitud posible será de \( \displaystyle q \).

Ahora que ya sabemos la longitud máxima que podrán tener las cadenas de primos generadas por un polinomio, nos preguntamos cómo encontrar un polinomio que genere cadenas de esta longitud. Sabemos, por lo visto aquí, que cualquier polinomio con término independiente un primo \( \displaystyle q \) puede generar cadenas de primos de, como máximo, \( \displaystyle q \) primos sin repetición, o \( \displaystyle (g+1)\cdot q-1 \) primos con repetición, siendo \( \displaystyle g \) el grado del polinomio. Pero no tenemos garantías de que las cadenas generadas tengan dicha longitud.

Más allá de esto, no se me ocurre una forma directa de hallar polinomios que generen primos de una determinada longitud. Sin embargo, se pueden realizar ciertas comprobaciones para descartar polinomios que no generarán cadenas de la longitud deseada.

Para ello, primero decidimos la máxima longitud que queremos de la cadena de primos que deberá generar nuestro polinomio. Sea \( \displaystyle l \) esta longitud. Elegimos un número primo \( \displaystyle q>l \), que será el término independiente de nuestro polinomio. Ahora elegimos el grado que tendrá nuestro polinomio. Sea \( \displaystyle g \) este grado. Escribimos nuestro polinomio como \( \displaystyle q+b\cdot x+c\cdot x^2+d\cdot x^3+...+k\cdot x^g=0 \), donde \( \displaystyle b,c,...,k \) son incógnitas que desconocemos, y que debemos calcular.

Nuestro polinomio ya genera un primo, y es cuando \( \displaystyle x=0 \), y genera el primo \( \displaystyle q \). Pero queremos que genere más primos cuando \( \displaystyle x=1,2,3,...,l-1 \), para tener al final la cadena de primos que buscamos. Como forma alternativa, podemos buscar cadenas de primos para valores de \( \displaystyle x=t\cdot q+1+\alpha,t\cdot q+2+\alpha,t\cdot q+3+\alpha,...,t\cdot q+l+\alpha \), para algún \( \displaystyle t>1 \), y algún \( \displaystyle \alpha \) comprendido entre \( \displaystyle 0 \) y el máximo valor para el que \( \displaystyle t\cdot q+l+\alpha \) no es múltiplo de \( \displaystyle q \). Como veremos, el procedimiento que vamos a seguir sirve igual, sólo que al comprobar si el polinomio genera la cadena de primos de la longitud que deseamos, tendremos que hacer comprobaciones más largas.

Para que el polinomio genere primos, tenemos que seleccionar valores para las incógnitas \( \displaystyle b,c,...,k \) de forma que para los valores de \( \displaystyle x \) que queremos que generen la cadena de primos, los valores generados por el polinomio sean primos. Esto significa que los valores generados por el polinomio no serán divisibles por ningún primo \( \displaystyle p \), salvo los propios primos generados. En particular, los valores del polinomio no serán divisibles por \( \displaystyle 2 \), salvo que queramos que genere el primo \( \displaystyle 2 \). En este caso, se tiene que cumplir:

\( \displaystyle q+b\cdot x+c\cdot x^2+d\cdot x^3+...+k\cdot x^g\not\equiv 0\pmod{2} \)

A primera vista parece que no hemos conseguido nada. Pero basta darse cuenta de que todos los términos del polinomio siguen una aritmética módulo 2, por lo que sus valores son, o bien \( \displaystyle 0\pmod{2} \), o bien \( \displaystyle 1\pmod{2} \). Esto incluye también la variable \( \displaystyle x \). Ahora, podemos asignar todas las posibles combinaciones de valores \( \displaystyle 0 \) o \( \displaystyle 1 \) a cada incógnita \( \displaystyle b,c,...,k \), y después, comprobar si el polinomio cumple:

\( \displaystyle q+b\cdot x+c\cdot x^2+d\cdot x^3+...+k\cdot x^g\not\equiv 0\pmod{2} \)

para todos los posibles valores de \( \displaystyle x \), que también serán \( \displaystyle 0 \) o \( \displaystyle 1 \). Por ejemplo, supongamos el polinomio \( \displaystyle 41+b\cdot x+c\cdot x^2 \). Se tiene que cumplir \( \displaystyle 41+b\cdot x+c\cdot x^2\not\equiv 0\pmod{2} \), que es equivalente a \( \displaystyle 1+b\cdot x+c\cdot x^2\not\equiv 0\pmod{2} \). Las incógnitas son \( \displaystyle b \) y \( \displaystyle c \), y les daremos los valores \( \displaystyle 0 \) y \( \displaystyle 1 \), y comprobaremos en cada caso si con dichos valores, se cumple \( \displaystyle 1+b\cdot x+c\cdot x^2\not\equiv 0\pmod{2} \) con cada valor posible de \( \displaystyle x \). Tenemos:

\( \displaystyle
b=0,c=0 \\
1+0\cdot 0+0\cdot 0^2\equiv 1\not\equiv 0\pmod{2} \\
1+0\cdot 1+0\cdot 1^2\equiv 1\not\equiv 0\pmod{2} \\ \ \\

b=1,c=0 \\
1+1\cdot 0+0\cdot 0^2\equiv 1\not\equiv 0\pmod{2} \\
1+1\cdot 1+0\cdot 1^2\equiv 0\equiv 0\pmod{2} \\ \ \\

b=0,c=1 \\
1+0\cdot 0+1\cdot 0^2\equiv 1\not\equiv 0\pmod{2} \\
1+0\cdot 1+1\cdot 1^2\equiv 0\equiv 0\pmod{2} \\ \ \\

b=1,c=1 \\
1+1\cdot 0+1\cdot 0^2\equiv 1\not\equiv 0\pmod{2} \\
1+1\cdot 1+1\cdot 1^2\equiv 1\not\equiv 0\pmod{2}
 \)

Tenemos dos posibilidades, a saber, que \( \displaystyle b\equiv 0\pmod{2} \) y \( \displaystyle c\equiv 0\pmod{2} \), o bien que \( \displaystyle b\equiv 1\pmod{2} \) y \( \displaystyle c\equiv 1\pmod{2} \) (es decir, que la paridad de \( \displaystyle b \) y de \( \displaystyle c \) coinciden).

Esto sólo nos garantiza que los valores generados por el polinomio no son divisibles por \( \displaystyle 2 \). Podríamos buscar valores de \( \displaystyle b \) y \( \displaystyle c \) que cumplan estas condiciones, y ver si el polinomio genera la cadena de primos que estamos buscando (en este ejemplo, la encontraríamos enseguida, pues basta dar los valores \( \displaystyle b=1,c=1 \) para obtener el famoso polinomio \( \displaystyle 41+x+x^2 \), que ya genera la cadena de primos).

Podemos hacer lo mismo para \( \displaystyle 3 \). En este caso, tenemos que darle a las incógnitas \( \displaystyle b,c,...,k \), todos los valores comprendidos entre \( \displaystyle 0 \) y \( \displaystyle 2 \), y ver para cuáles de ellos se cumple, para todos los valores de \( \displaystyle x \) comprendidos entre \( \displaystyle 0 \) y \( \displaystyle 2 \):

\( \displaystyle q+b\cdot x+c\cdot x^2+d\cdot x^3+...+k\cdot x^g\not\equiv 0\pmod{3} \)

Esto supone más combinaciones que antes. En nuestro ejemplo, tiene que cumplirse \( \displaystyle 41+b\cdot x+c\cdot x^2\not\equiv 0\pmod{3} \), que es equivalente a \( \displaystyle 2+b\cdot x+c\cdot x^2\not\equiv 0\pmod{3} \). No voy a escribir todos los casos. Simplemente escribo los valores permitidos para \( \displaystyle b \) y \( \displaystyle c \):

\( \displaystyle
b\equiv 0\pmod{3}, c\equiv 0\pmod{3} \\
b\equiv 0\pmod{3}, c\equiv 2\pmod{3} \\
b\equiv 1\pmod{3}, c\equiv 1\pmod{3} \\
b\equiv 2\pmod{3}, c\equiv 1\pmod{3}
 \)

Estos valores para \( \displaystyle b \) y \( \displaystyle c \) nos garantizan que el polinomio no generará múltiplos de \( \displaystyle 3 \). Podemos seguir haciendo esto para diferentes primos \( \displaystyle p \), obteniendo qué valores de las incógnitas \( \displaystyle b,c,...,k \) nos garantizan que el polinomio no va a generar múltiplos de \( \displaystyle p \). Por ejemplo, para \( \displaystyle 5 \), en el ejemplo, tenemos:

\( \displaystyle
b\equiv 0\pmod{5}, c\equiv 0\pmod{5} \\
b\equiv 0\pmod{5}, c\equiv 2\pmod{5} \\
b\equiv 0\pmod{5}, c\equiv 3\pmod{5} \\
b\equiv 1\pmod{5}, c\equiv 1\pmod{5} \\
b\equiv 1\pmod{5}, c\equiv 2\pmod{5} \\
b\equiv 2\pmod{5}, c\equiv 3\pmod{5} \\
b\equiv 2\pmod{5}, c\equiv 4\pmod{5} \\
b\equiv 3\pmod{5}, c\equiv 3\pmod{5} \\
b\equiv 3\pmod{5}, c\equiv 4\pmod{5} \\
b\equiv 4\pmod{5}, c\equiv 1\pmod{5} \\
b\equiv 4\pmod{5}, c\equiv 2\pmod{5}
 \)

Cada uno de estos resultados nos garantiza que los valores generados por el polinomio no van a ser divisibles por el correspondiente primo, pero en cada caso, no tenemos garantías de que el valor no sea divisible por los otros primos de los otros casos (es decir, en este último ejemplo, tenemos garantizado que con esos valores, el polinomio no va a generar valores divisibles por \( \displaystyle 5 \), pero podrían generarse valores divisibles por \( \displaystyle 2 \), por \( \displaystyle 3 \), o por cualquier otro primo).

Para obtener los correspondientes valores de \( \displaystyle b,c,...,k \) que garanticen que el polinomio no genere valores divisibles por ninguno de los primos con los que hemos trabajado, basta coger un caso de cada primo, plantear un sistema de conguencias con cada uno de los términos y cada uno de los primos, y aplicar el Teorema Chino de los Restos.

En nuestro ejemplo, queremos ver para qué valores de \( \displaystyle b \) y \( \displaystyle c \) el polinomio no genera valores divisibles por \( \displaystyle 2 \) ni por \( \displaystyle 3 \) ni por \( \displaystyle 5 \). Tomamos un caso de cada primo. Por ejemplo, tomamos para el primo \( \displaystyle 2 \), el caso \( \displaystyle b\equiv 1\pmod{2}, c\equiv 1\pmod{2} \). Para el primo \( \displaystyle 3 \), el caso \( \displaystyle b\equiv 0\pmod{3}, c\equiv 2\pmod{3} \), y para el primo \( \displaystyle 5 \), el caso \( \displaystyle b\equiv 3\pmod{5}, c\equiv 4\pmod{5} \). Planteamos el sistema de congruencias para el término \( \displaystyle b \):

\( \displaystyle
b\equiv 1\pmod{2} \\
b\equiv 0\pmod{3} \\
b\equiv 3\pmod{5}
 \)

Su solución es \( \displaystyle b\equiv 3\pmod{30} \).

El sistema de congruencias para el término \( \displaystyle c \) es:

\( \displaystyle
c\equiv 1\pmod{2} \\
c\equiv 2\pmod{3} \\
c\equiv 4\pmod{5}
 \)

Su solución es \( \displaystyle c\equiv 29\pmod{30} \).

Así, estos valores para \( \displaystyle b \) y \( \displaystyle c \) nos garantizan que los valores generados por el polinomio no serán divisibles por \( \displaystyle 2 \), \( \displaystyle 3 \) ni \( \displaystyle 5 \). Podemos realizar los cálculos para más primos, de forma que los valores generados por el polinomio no serán divisibles por dichos primos. Podemos también hacer esto eligiendo diferentes resultados de los obtenidos anteriormente por cada primo, lo que hace que el número de posibilidades crezca muy rápidamente a medida que aumenta el número de primos por el que no queremos que sean divisibles los valores del polinomio.

¿Hasta cuántos primos (primos consecutivos partiendo de \( \displaystyle 2 \)) tenemos que comprobar como mínimo para asegurarnos de que exista la posibilidad (pero no la seguridad) de que el polinomio genere un valor primo?. Recordemos que al polinomio \( \displaystyle q+b\cdot x+c\cdot x^2+d\cdot x^3+... \) le vamos dando valores a la variable \( \displaystyle x \) comprendidos entre \( \displaystyle x_0 \) y \( \displaystyle x_0+l-1 \), \( \displaystyle l \) la longitud de la cadena de primos generada. Es decir, \( \displaystyle x \) toma \( \displaystyle l \) valores consecutivos. Sabemos que una secuencia de \( \displaystyle l \) valores consecutivos tendrá múltiplos de los primos comprendidos entre \( \displaystyle 2 \) y \( \displaystyle l \), aparte de otros posibles primos y múltiplos de primos mayores a \( \displaystyle l \). Sea \( \displaystyle p \) uno de estos primos que toma el valor \( \displaystyle x_0+t \). Siendo \( \displaystyle x_0+t \) múltiplo de \( \displaystyle p \), entonces \( \displaystyle (x_0+t)^r \) también será múltiplo de \( \displaystyle p \) y, también lo será \( \displaystyle k\cdot(x_0+t)^r \). Por tanto, también lo será \( \displaystyle b\cdot (x_0+t)+c\cdot (x_0+t)^2+d\cdot (x_0+t)^3+... \). Tenemos, al final, que tiene que ocurrir que \( \displaystyle q+b\cdot x+c\cdot x^2+d\cdot x^3+... \) no sea múltiplo de \( \displaystyle p \). Y esto tiene que ocurrir para todos los valores comprendidos entre \( \displaystyle x_0 \) y \( \displaystyle x_0+l-1 \). Como los únicos primos que tenemos la seguridad que van a aparecer en los términos no independientes son los comprendidos entre \( \displaystyle 2 \) y \( \displaystyle l \), son éstos los primos que tenemos que comprobar como mínimo. Por tanto, debemos comprobar todos los primos menores o iguales a \( \displaystyle l \) para tener esa mínima seguridad de que el polinomio pueda generar una cadena de \( \displaystyle l \) valores primos.

Por supuesto, puede dar la casualidad de que demos a la primera con los coeficientes del polinomio sin haber comprobado todos los primos (como ocurrió en el anterior ejemplo). En este caso, basta comprobar que el polinomio genera un primo por cada valor que le demos a \( \displaystyle x \).

Podemos también comprobar primos \( \displaystyle p \) mayores a \( \displaystyle l \). En este caso, a la hora de construir las congruencias en las que le dábamos a \( \displaystyle x \) los valores comprendidos entre \( \displaystyle 0 \) y \( \displaystyle p-1 \), aquí no tenemos que darle todos esos valores, sino solamente \( \displaystyle l \) valores consecutivos, ya que solamente buscamos \( \displaystyle l \) primos a generar por el polinomio dándole a \( \displaystyle x \), \( \displaystyle l \) valores consecutivos. Tampoco es necesario partir de \( \displaystyle 0 \). Así, plantearíamos las congruencias:

\( \displaystyle
b=r,c=r,d=r,... \\
q+r\cdot 0+r\cdot 0^2+r\cdot 0^3+...\not\equiv 0\pmod{p} \\
q+r\cdot 1+r\cdot 0^2+r\cdot 0^3+...\not\equiv 0\pmod{p} \\
q+r\cdot 2+r\cdot 0^2+r\cdot 0^3+...\not\equiv 0\pmod{p} \\
... \\
q+r\cdot (l-1)+r\cdot (l-1)^2+r\cdot (l-1)^3+...\not\equiv 0\pmod{p} \\ \ \\


b=r+1,c=r,d=r,... \\
q+(r+1)\cdot 0+r\cdot 0^2+r\cdot 0^3+...\not\equiv 0\pmod{p} \\
q+(r+1)\cdot 1+r\cdot 0^2+r\cdot 0^3+...\not\equiv 0\pmod{p} \\
q+(r+1)\cdot 2+r\cdot 0^2+r\cdot 0^3+...\not\equiv 0\pmod{p} \\
... \\
q+(r+1)\cdot (l-1)+r\cdot (l-1)^2+r\cdot (l-1)^3+...\not\equiv 0\pmod{p} \\ \ \\

b=r+2,c=r,d=r,... \\
q+(r+2)\cdot 0+r\cdot 0^2+r\cdot 0^3+...\not\equiv 0\pmod{p} \\
q+(r+2)\cdot 1+r\cdot 0^2+r\cdot 0^3+...\not\equiv 0\pmod{p} \\
q+(r+2)\cdot 2+r\cdot 0^2+r\cdot 0^3+...\not\equiv 0\pmod{p} \\
... \\
q+(r+2)\cdot (l-1)+r\cdot (l-1)^2+r\cdot (l-1)^3+...\not\equiv 0\pmod{p} \\ \ \\

... \\ \ \\

b=r+l-1,c=r+l-1,d=r+l-1,... \\
q+(r+l-1)\cdot 0+(r+l-1)\cdot 0^2+(r+l-1)\cdot 0^3+...\not\equiv 0\pmod{p} \\
q+(r+l-1)\cdot 1+(r+l-1)\cdot 0^2+(r+l-1)\cdot 0^3+...\not\equiv 0\pmod{p} \\
q+(r+l-1)\cdot 2+(r+l-1)\cdot 0^2+(r+l-1)\cdot 0^3+...\not\equiv 0\pmod{p} \\
... \\
q+(r+l-1)\cdot (l-1)+(r+l-1)\cdot (l-1)^2+(r+l-1)\cdot (l-1)^3+...\not\equiv 0\pmod{p}
 \)

Y luego elegiríamos aquellas que se cumplan, como vimos antes, para plantear el sistema de congruencias lineales con el resto de las congruencias, y resolverlas con el Teorema Chino de los Restos.

¿Qué ocurre si queremos que el polinomio genere un determinado primo?. En ese caso, debemos asegurarnos de que en el planteamiento de las congruencias no prohibamos que aparezca dicho primo. Si planteamos una conguencia en la que el polinomio genere un valor congruente con ese primo, eso no nos garantiza que el polinomio genere tal primo. Sólo nos garantiza que generará un múltiplo de ese primo, que puede ser el propio primo, o un múltiplo del mismo. En este caso, no se me ocurre cómo determinar directamente los coeficientes del polinomio, salvo simplemente estableciendo como valor del término independiente el primo que queremos que aparezca, que aparecerá cuando \( \displaystyle x=0 \). Pero si queremos que el polinomio genere una cadena de primos de longitud \( \displaystyle l \) mayor que ese primo, esta solución no nos vale.

Y hasta aquí todo lo que he podido determinar sobre los polinomios generadores de primos. Espero no haberme equivocado en nada, ni haber aburrido al personal :).


----------------------------------------

Edición:

Como bien sugirió el_manco, voy a mostrar las conclusiones en un apartado que facilite la visión general de lo que he escrito.

Lo que muestro aquí es lo siguiente:

Sea el polinomio \( \displaystyle a+b\cdot x+c\cdot x^2+d\cdot x^3+...+k\cdot x^g \), de grado \( \displaystyle g \). Sea \( \displaystyle p \) el menor primo que divide al término independiente \( \displaystyle a \).

Primero, queremos ver cuántos primos como máximo genera este polinomio dándole a \( \displaystyle x \) valores consecutivos. Así, en lo que he expuesto, se llega a la conslusión de que el máximo número de primos diferentes que puede generar el polinomio dándole a \( \displaystyle x \) valores consecutivos será de \( \displaystyle p \) primos como máximo. Y el máximo número de primos, con repetición, que puede generar es de \( \displaystyle (g-1)\cdot p-1 \) primos como máximo. Esto no garantiza que genere esa cantidad de primos, lo que garantiza es que no podrán generarse más primos que esos, para valores consecutivos de \( \displaystyle x \).

Segundo, queremos encontrar algún método de poder encontrar polinomios que generen una cantidad especificada de primos diferentes. No se encuentra tal método, pero sí se encuentra una forma de descartar algunos polinomios que tendremos la seguridad de que no generarán esa cantidad de primos especificada. Aunque esas operaciones son poco eficientes al crecer muy deprisa el número de condiciones a comprobar. Esto se hace construyendo congruencias para que el polinomio no sea congruente con \( \displaystyle 0 \) módulo una serie de primos para los que no queremos que el polinomio genere sus múltiplos. Luego, de las congruencias encontradas, se elige una de cada primo, para construir un sistema de congruencias y resolverlo para obtener los coeficientes del polinomio que no generarán múltiplos de niguno de los primos.

Tercero, se indica que si se quiere que el polinomio genere un determinado primo, no debe prohibirse su aparición en el anterior procedimiento, y se indica un método para garantizar que aparezca, y es darle al término independiente \( \displaystyle a \) el valor de ese primo, pero esto sólo es válido si la cantidad de primos que queremos que genere el polinomio es menor que el valor de ese primo.

----------------------------------------

Nota: Se me olvidó indicar, aunque es implícito, que los coeficientes encontrados por el método indicado son módulo un determinado valor, lo que significa que cualquier valor congruente es válido. Por ejemplo, las soluciones encontradas: \( \displaystyle b\equiv 3\pmod{30} \) y \( \displaystyle c\equiv 29\pmod{30} \). Estas soluciones indican que \( \displaystyle b \) es de la forma \( \displaystyle 3+r\cdot 30 \) y \( \displaystyle c \) es de la forma \( \displaystyle 29+s\cdot 30 \), para cualquier valor entero de \( \displaystyle s \) y \( \displaystyle t \).

4
Teoría de números / Observaciones sobre los primos equidistantes
« en: 19 Diciembre, 2016, 02:08 pm »
Lo que voy a escribir aquí surgió como idea de otro hilo:

http://rinconmatematico.com/foros/index.php?topic=92069.0

Vamos a ver algunas características de los primos equidistantes. Primero definamos qué son primos equidistantes:

Dado el conjunto de tres o más primos impares \( \displaystyle \{p_i,p_j,p_k,...\} \), con \( \displaystyle p_i<p_j<p_k,... \), diremos que estos primos son equidistantes si se cumple \( \displaystyle p_j-p_i=p_k-p_j=...=d \), donde \( \displaystyle d \) es la distancia que separa a estos primos, \( \displaystyle d \) es par mayor que \( \displaystyle 0 \).

Para simplificar las explicaciones, daremos algunas definiciones. Al conjunto de primos que cumplen esta propiedad la llamaremos cadena de primos equidistantes a distancia \( \displaystyle d \) (que podremos simplificar si se sobreentiende a cadena de primos equidistantes, cadena de primos, cadena de primos a distancia \( \displaystyle d \)). El número de primos que componen este conjunto lo llamaremos longitud de la cadena, y al número de primos del conjunto menos \( \displaystyle 1 \) lo llamaremos número de saltos en la cadena. Para simplificar algunas explicaciones, consideraremos que un conjunto de sólo dos primos es un caso especial de primos equidistantes, y así nos referiremos a ellos, aunque en realidad no lo sean.

Lo primero que hay que tener en cuenta es que estos primos no son necesariamente consecutivos. Es decir, entre \( \displaystyle p_i \) y \( \displaystyle p_j \) puede, o no, haber uno o varios primos.

Nos preguntamos por la máxima longitud que puede tener una cadena de primos a una determinada distancia \( \displaystyle d \).

Partimos del primo \( \displaystyle p_i \). El siguiente primo debe ser \( \displaystyle p_i+d=p_j \). Para que \( \displaystyle p_j \) sea primo, no debe ser divisible por ningún primo menor a \( \displaystyle p_j \). En particular, \( \displaystyle p_j \) no debe ser divisible por \( \displaystyle 3 \). Para que esto ocurra, tiene que cumplirse \( \displaystyle p_j\equiv \{1,2\}\pmod{3} \).

Puesto que \( \displaystyle p_i \) también es primo, tiene que cumplirse \( \displaystyle p_i\equiv \{1,2\}\pmod{3} \) ó \( \displaystyle p_i=3 \).

Supongamos el primer caso, es decir, \( \displaystyle p_i\equiv \{1,2\}\pmod{3} \). Puesto que \( \displaystyle p_i+d=p_j \) y además \( \displaystyle p_j\equiv \{1,2\}\pmod{3} \), tiene que ocurrir que \( \displaystyle p_i+d\equiv \{1,2\}\pmod{3} \). El valor de \( \displaystyle d \) puede ser cualquier valor par, no importa su valor módulo \( \displaystyle 3 \). Veamos qué ocurre cuando \( \displaystyle d\equiv \{1,2\}\pmod{3} \).

Para que se cumpla \( \displaystyle p_i+d\equiv \{1,2\}\pmod{3} \), tiene que ocurrir que \( \displaystyle p_i\equiv 1\pmod{3} \) y \( \displaystyle d\equiv 1\pmod{3} \), o bien \( \displaystyle p_i\equiv 2\pmod{3} \) y \( \displaystyle d\equiv 2\pmod{3} \). Sólo en esos casos se cumplirá \( \displaystyle p_i+d\equiv \{1,2\}\pmod{3} \), que es la condición necesaria (pero no suficiente) para que \( \displaystyle p_j \) sea primo.

Supongamos que \( \displaystyle p_j=p_i+d \) es primo, y queremos hallar el siguiente primo equidistante sumándole a \( \displaystyle p_j \) la distancia \( \displaystyle d \). Cuando \( \displaystyle d\equiv 1\pmod{3} \), puesto que \( \displaystyle p_i\equiv 1\pmod{3} \) (por lo visto antes) y \( \displaystyle p_j=p_i+d \), se cumplirá que \( \displaystyle p_j\equiv 2\pmod{3} \). Y si \( \displaystyle d\equiv 2\pmod{3} \), por la misma razón que antes, se cumplirá que \( \displaystyle p_j\equiv 1\pmod{3} \). En ambos casos, al sumarle a \( \displaystyle p_j \) el valor \( \displaystyle d \), obtenemos como resultado \( \displaystyle p_j+d\equiv 0\pmod{3} \), que no es primo, sino múltiplo de \( \displaystyle 3 \).

Así, pues, si \( \displaystyle d\equiv \{1,2\}\pmod{3} \), la máxima longitud posible de la cadena de primos equidistantes será de \( \displaystyle 2 \), que serán \( \displaystyle p_i \) y \( \displaystyle p_i+d=p_j \).

Esto demuestra que distancias que no son múltiplos de \( \displaystyle 3 \) sólo generarán cadenas de primos equidistantes de, como máximo, dos primos. Como excepción a esta regla, tenemos el caso en el que \( \displaystyle p_i=3 \). En este caso, puesto que partimos de \( \displaystyle p_i\equiv 0\pmod{3} \), al sumarle el valor \( \displaystyle d \), obtenemos un valor de \( \displaystyle p_j\equiv \{1,2\}\pmod{3} \), y en caso de ser primo, estamos en el mismo caso anterior, en el que la cadena tendrá como máximo \( \displaystyle 2 \) primos, a los que añadimos el primo \( \displaystyle 3 \), obteniendo así una cadena de \( \displaystyle 3 \) primos. Y si hacemos los cálculos con, por ejemplo, \( \displaystyle d=4 \), vemos que sí que existe tal cadena de \( \displaystyle 3 \) primos: \( \displaystyle \{3,7,11\} \). Lo mismo ocurre con \( \displaystyle d=8 \): \( \displaystyle \{3,11,19\} \).

Veamos qué ocurre cuando \( \displaystyle d\equiv 0\pmod{3} \). Igual que antes, tenemos que \( \displaystyle p_i\equiv \{1,2\}\pmod{3} \) ó \( \displaystyle p_i=3 \).

Empecemos suponiendo \( \displaystyle p_i\equiv \{1,2\}\pmod{3} \). Sumemos la distancia \( \displaystyle d \) a \( \displaystyle p_i \) para obtener \( \displaystyle p_j \). Tenemos que \( \displaystyle p_i+d\equiv p_i+0\equiv p_i\equiv \{1,2\}\pmod{3} \). Es decir, que el valor de la congruencia se mantiene. Si volvemos a sumar \( \displaystyle d \), volveremos a obtener el mismo valor de la congruencia. Así, pues, podemos sumar cualquier cantidad de veces el valor \( \displaystyle d \), y tenemos la seguridad de que el valor obtenido no será múltiplo de \( \displaystyle 3 \).

Si suponemos el caso en el que \( \displaystyle p_i=3 \), nos encontramos con que \( \displaystyle p_i\equiv 0\pmod{3} \). Al sumarle el valor \( \displaystyle d \), igual que ocurría antes, la congruencia toma el mismo valor. Tenemos que \( \displaystyle p_j=p_i+d\equiv 0\pmod{3} \), que no es primo, sino múltiplo de \( \displaystyle 3 \). Por tanto, cuando \( \displaystyle d\equiv 0\pmod{3} \), para tener una cadena de primos equidistantes, \( \displaystyle p_i \) no puede ser \( \displaystyle 3 \), a diferencia de los casos anteriores.

Hemos visto que si \( \displaystyle p_i\equiv \{1,2\}\pmod{3} \) y \( \displaystyle d\equiv 0\pmod{3} \), podemos sumar a \( \displaystyle p_i \) cuantas veces queramos el valor \( \displaystyle d \) y tener la seguridad de que no obtendremos un múltiplo de \( \displaystyle 3 \). ¿Significa esto que podemos obtener cadenas de primos equidistantes de longitud arbitraria?. La respuesta es que no, y lo veremos a continuación.

Aunque ya sabemos que los enteros que obtenemos sumando \( \displaystyle d \) al primo \( \displaystyle p_i\ne 3 \) cuando \( \displaystyle d\equiv 0\pmod{3} \) no son múltiplos de \( \displaystyle 3 \), nos encontramos con el siguiente primo, a saber, el \( \displaystyle 5 \). Aquí nos encontramos ante el mismo problema que antes. Si \( \displaystyle d\equiv \{1,2,3,4\}\pmod{5} \), a medida que vayamos sumando el valor \( \displaystyle d \) a \( \displaystyle p_i \), iremos obteniendo diferentes valores en las congruencias \( \displaystyle p_j=p_i+d\equiv \{1,2,3,4\}\pmod{5} \), \( \displaystyle p_k=p_j+d=p_i+d+d=p_i+2\cdot d\equiv \{1,2,3,4\}\pmod{5} \), ....

Al final, acabaremos obteniendo un valor congruente con \( \displaystyle 0 \) módulo \( \displaystyle 5 \), es decir, un múltiplo de \( \displaystyle 5 \). Por tanto, en estas condiciones, tarde o temprano nos encontraremos con un múltiplo de \( \displaystyle 5 \). En el mejor de los casos, si \( \displaystyle p_i\ne 5 \), el máximo número de primos equidistantes posible será de \( \displaystyle 4 \). Esto es fácil de ver. Sea \( \displaystyle p_i\equiv 1\pmod{5} \) y \( \displaystyle d\equiv 1\pmod{5} \). Podemos sumar \( \displaystyle d \) hasta \( \displaystyle 3 \) veces antes de encontrarnos con un múltiplo de \( \displaystyle 5 \). Es decir, podemos obtener como máximo \( \displaystyle 3 \) primos a distancia \( \displaystyle d \), al que hay que añadir el primo de partida, \( \displaystyle p_i \), para obtener la cadena de primos equidistante \( \displaystyle \{p_i,p_i+d,p_i+2d,p_i+3d\} \). Como caso excepcional, tenemos el caso en el que \( \displaystyle p_i=5 \), en el que podremos obtener como mucho una cadena de longitud máxima de \( \displaystyle 5 \) primos.

Como antes, para que al sumar la distancia \( \displaystyle d \) no obtengamos un múltiplo de \( \displaystyle 5 \), es necesario que \( \displaystyle d\equiv 0\pmod{5} \) y \( \displaystyle p_i\ne 5 \). Puesto que también debe cumplirse que \( \displaystyle d\equiv 0\pmod{3} \), para poder obtener cadenas de primos equidistantes de longitud mayor de \( \displaystyle 4 \), es necesario que se cumpla \( \displaystyle d\equiv 0\pmod{3\cdot 5} \).

Pero como antes, la última condición no nos asegura que obtengamos una cadena de longitud ilimitada, puesto que ahora tenemos que hacer lo mismo con el siguiente primo, el \( \displaystyle 7 \). El razonamiento es el mismo que antes. Si \( \displaystyle d\not\equiv 0\pmod{7} \), la máxima longitud posible para una cadena de primos equidistante es de \( \displaystyle 6 \), y como caso excepcional, de \( \displaystyle 7 \) si \( \displaystyle p_i=7 \). Para poder obtener cadenas de longitud mayor, es necesario que se cumpla \( \displaystyle d\equiv 0\pmod{\{3,5,7\}} \), o lo que es lo mismo, que \( \displaystyle d\equiv 0\pmod{3\cdot 5\cdot 7} \).

Generalizando, podemos deducir lo siguente. Sea \( \displaystyle q \) el menor primo que no divide a \( \displaystyle d \). Tenemos que se cumple \( \displaystyle d\not\equiv 0\pmod{q} \). Las cadenas de primos a distancia \( \displaystyle d \) no pueden tener una longitud mayor de \( \displaystyle q-1 \) y, como caso excepcional, no pueden tener una longitud mayor de \( \displaystyle q \) si \( \displaystyle p_i=q \).

Esto no demuestra que existan cadenas de esa longitud. Simplemente demuestra que no pueden existir cadenas de longitud mayor.

El programa, tomando 100.000 números consecutivos, no detecta cuatro primos seguidos a distancia de 4, ni de 8 ni de 10 ni de 12 (y no he probado más) por lo que de haber esas sucesiones largas (quizá infinitas) vaticino que tendrían que estar siempre a distancia de 6; a falta de más pruebas empíricas con programación, ya que, analíticamente lo veo muy difícil.

feriva, creo que esto responde a tus dudas. Ahora queda claro por qué no encuentras cadenas de longitud 4 con distancias de 4, 8, 10. Es porque el menor primo que no divide a \( \displaystyle 4 \) es \( \displaystyle 3 \) y, por tanto, la mayor longitud posible es de \( \displaystyle 3-1=2 \). Lo que no sé es por qué no encuentra cadenas de longitud \( \displaystyle 4 \) cuando \( \displaystyle d=12 \), pues el menor primo que no divide a \( \displaystyle 12 \) es \( \displaystyle 5 \), lo que limita la longitud máxima a \( \displaystyle 5-1=4 \). Imagino que es porque buscas primos consecutivos, y en lo que he expuesto no he considerado primos consecutivos, sino primos en general. Es posible que los primos consecutivos tengan mayores restricciones.

Visto esto, voy a continuar con otras curiosidades.

Con lo visto antes, vemos que, para que una cadena pueda tener una longitud de al menos \( \displaystyle q_i-1 \) primos, es necesario que se cumpla \( \displaystyle d\equiv 0\pmod{3\cdot 5\cdot 7\cdot ... \cdot q_{i-1}} \), es decir, \( \displaystyle d\equiv 0\pmod{q_{i-1}\#} \), donde \( \displaystyle q_{i-1}\# \) es el primorial de \( \displaystyle q_{i-1} \). Puesto que para todo \( \displaystyle d \) siempre hay un primo mínimo \( \displaystyle q_j \) para el que se cumple \( \displaystyle d\not\equiv 0\pmod{q_j} \), y cuando ocurre esto la máxima longitud posible de la cadena es de \( \displaystyle q_j-1 \), siempre habrá un límite para la longitud máxima posible de una cadena de primos equidistantes. Es decir, no existen cadenas de primos equidistantes de longitud infinita.

Otra curiosidad es la siguiente. Hemos visto que la máxima longitud de la cadena es \( \displaystyle q-1 \), siendo \( \displaystyle q \) el menor primo que no divide a \( \displaystyle d \). Pero esto es el mejor de los casos, el más simple de los cuales es cuando \( \displaystyle p_i\equiv 1\pmod{q} \) y \( \displaystyle d\equiv 1\pmod{q} \). ¿Podemos obtener la máxima longitud posible de la cadena conociendo los valores de \( \displaystyle p_i \) y de \( \displaystyle d \) módulo \( \displaystyle q \)?. La respuesta es que sí, como vamos a ver. Antes de nada, vamos a suponer que \( \displaystyle p_i \) es el menor primo de la cadena que queremos obtener. No tendremos en cuenta si \( \displaystyle p_i-d \) es primo o no, simplemente consideraremos a \( \displaystyle p_i \) el primer primo de la cadena, y los que hay después de él serán los demás primos de la cadena.

Queremos determinar cuántas veces podemos sumar \( \displaystyle d \) a \( \displaystyle p_i \) antes de obtener un múltiplo de \( \displaystyle q \). Esto es resolver la congruencia lineal \( \displaystyle p_i+d\cdot x\equiv 0\pmod{q} \), que tendrá una única solución por cumplirse \( \displaystyle mcd(d,q)=1 \), ya que \( \displaystyle q \) es el menor primo que no divide a \( \displaystyle d \). El valor de \( \displaystyle x \) estará comprendido entre \( \displaystyle 0 \) y \( \displaystyle q-1 \). Este valor nos indica el número de veces que debemos sumar \( \displaystyle d \) a \( \displaystyle p_i \) para obtener un múltiplo de \( \displaystyle q \). En este punto, pueden ocurrir dos cosas.

La primera es que obtengamos como solución \( \displaystyle x=0 \). Esto significa que \( \displaystyle p_i \) es múltiplo de \( \displaystyle q \). Si \( \displaystyle p_i=q \), por lo visto antes, es un caso excepcional, y la máxima longitud posible de la cadena es \( \displaystyle q \). Si \( \displaystyle p_i\ne q \), entonces \( \displaystyle p_i \) no es primo, sino múltiplo de \( \displaystyle q \), y no puede formar parte de una cadena de primos equidistantes.

La segunda cosa que puede ocurrir es que \( \displaystyle x\ne 0 \). En este caso, esta solución nos da directamente la longitud máxima posible de la cadena (podría pensarse que esta solución nos lleva a un múltiplo de \( \displaystyle q \), pero no buscamos un múltiplo de \( \displaystyle q \), sino el anterior valor, por lo que habría que restar \( \displaystyle 1 \) a \( \displaystyle x \). Esto es el número de veces máximo que podemos sumar \( \displaystyle d \) a \( \displaystyle p_i \) antes de obtener un múltiplo de \( \displaystyle q \), que es también el número de saltos de la cadena de primos. Como el número de primos de la cadena es uno más que el número de saltos, a este valor habría que sumarle \( \displaystyle 1 \) para obtener la longitud de la cadena, con lo que se vuelve a obtener el valor de \( \displaystyle x \)).

Otra curiosidad es, si pretendemos buscar cadenas de primos de una determinada longitud, si hay alguna forma de acelerar la búsqueda. Con lo visto hasta ahora, sí que podemos acelerar la búsqueda, aunque no tenemos garantía de que encontremos cadenas de la longitud deseada, pues no hemos demostrado que existan, sino simplemente la máxima longitud que pueden tener.

Sea \( \displaystyle k \) la longitud de la cadena que queremos buscar. Lo primero que tenemos que hacer es obtener la distancia que debe haber entre primos para asegurarnos de que pueden existir cadenas de esa longitud. Sabemos que las cadenas de una longitud \( \displaystyle k \) deben tener una distancia \( \displaystyle d \) tal que el menor primo que divida a \( \displaystyle d \) debe ser mayor que \( \displaystyle k \). Sea \( \displaystyle q_i>k \) este primo mínimo (se cumple \( \displaystyle k>q_{i-1} \)).

Puesto que los primos menores que \( \displaystyle q_i \) deben dividir a \( \displaystyle d \), tiene que ocurrir que \( \displaystyle d \) sea múltiplo del producto de todos ellos, es decir, \( \displaystyle d=r\cdot (3\cdot 5\cdot 7\cdot ... \cdot q_{i-1}) \), con \( \displaystyle r\ge 1 \), \( \displaystyle mcd(r,q)=1 \) (pues \( \displaystyle q \) no puede dividir a \( \displaystyle d \)), a nuestra elección.

Una vez establecida la distancia entre primos, tenemos que ver qué primos nos aseguran que pueden generar cadenas de longitud \( \displaystyle k \). Sea \( \displaystyle p_i \) un primo. Debe cumplirse que la solución de la congruencia \( \displaystyle p_i+x\cdot d\equiv 0\pmod{q_i} \) sea mayor o igual a \( \displaystyle k \). Aquí, la incógnita es \( \displaystyle p_i \), y a \( \displaystyle x \) le daremos los valores \( \displaystyle k,k+1,k+2,...,q_i-1 \) para obtener los diferentes valores de \( \displaystyle p_i \) módulo \( \displaystyle q_i \). Así, sólo los primos que sean congruentes con estos valores hallados módulo \( \displaystyle q_i \) podrán generar cadenas de longitud \( \displaystyle k \) o mayor, con distancia \( \displaystyle d \). Esto no garantiza que las encontremos, puesto que no se ha demostrado que existan y podrían no existir. Simplemente se ha demostrado que la máxima longitud posible es \( \displaystyle k,k+1,k+2,...,q_i-1 \).

5
Teoría de números / Observaciones sobre la conjetura de Goldbach
« en: 03 Julio, 2016, 12:57 pm »
A raíz de unas conversaciones entre Victor Luis y Feriva, sobre la conjetura de Goldbach, se me ocurrió esta forma de verla, que me parece interesante. Imagino que todo esto ya es conocido de sobra por los matemáticos. Pero si hubiera algo nuevo, pues mira que bien :) . Quería haber hecho las tablas en MathJax, pero no me salían bien, así que al final opté por utilizar imágenes. Las reduje de tamaño para que cupieran en pantallas normales. También tuve que dividir el mensaje en varias partes, porque sólo se permiten 4 imágenes por mensaje, y tenía un total de 10 imágenes que añadir. Y dicho esto, comienzo la explicación.

Para entender el procedimiento, lo primero que vamos a ver es una forma rudimentaria de suma. Si queremos sumar dos valores \( \displaystyle a \) y \( \displaystyle b \), construiremos una tabla. En la primera fila de esta tabla escribiremos todos los enteros, partiendo del \( \displaystyle 0 \), de esta forma:



Para hacer la suma \( \displaystyle a+b \), lo siguiente que tenemos que hacer es añadir una nueva fila de enteros partiendo del valor \( \displaystyle 0 \), pero este valor \( \displaystyle 0 \) debajo del valor \( \displaystyle a \) de la primera fila. Por ejemplo, supongamos que queremos realizar la suma \( \displaystyle 5+7 \). La segunda fila que vamos a escribir tendrá su valor \( \displaystyle 0 \) debajo del valor \( \displaystyle 5 \) de la primera fila, así:



Para hallar el resultado de la suma \( \displaystyle 5+7 \), sólo tenemos que buscar el valor \( \displaystyle 7 \) en la fila de abajo, y el resultado estará en la casilla de la primera fila que tiene encima:



El resultado, como cabía esperar, es \( \displaystyle 5+7=12 \).

Este método de suma puede aplicarse a la conjetura de Goldbach, ya que lo que vamos a obtener son sumas de primos. Lo único que tenemos que hacer es obtener sumas de la forma \( \displaystyle p+q \), con \( \displaystyle p \) y \( \displaystyle q \) primos. No consideraremos el caso \( \displaystyle 4=2+2 \), que claramente cumple la conjetura de Goldbach. Sólo trataremos con primos impares.

Páginas: [1]