Números primos

INSTITUTO TECNOLÓGICO

            SUPERIOR

´´ CENTRAL TÉCNICO´´   



NOMBRE: Wladimir Amaguaña



CURSO: 4D ´1´

TEMA: Números primos 

DOCENTE: Ing. Julio Calvopiña H., MSc 

AÑO LECTIVO:

2014-2015 

Números primos

    Un número primo es un número entero mayor que cero, que tiene exactamente dos divisores positivos. También podemos definirlo como aquel número entero positivo que no puede expresarse como producto de dos números enteros positivos más pequeños que él, o bien, como producto de dos enteros positivos de más de una forma. Conviene observar que con cualquiera de las dos definiciones el 1 queda excluido del conjunto de los números primos.
    Ejemplos: 
a) El 7 es primo. Sus únicos divisores son 1 y 7. Sólo puede expresarse como producto de 7·1.
 b) El 15 no es primo. Sus divisores son 1, 3, 5 y 15. Puede expresarse como 3·5.
    El término primo no significa que sean parientes de alguien. Deriva del latín "primus" que significa primero (protos en griego). El teorema fundamental de la aritmética afirma que todo número entero se expresa de forma única como producto de números primos. Por eso se les considera los "primeros", porque a partir de ellos obtenemos todos los demás números enteros. (El 15 se obtiene multiplicando los primos 3 y 5)
    Los 25 primeros números primos son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97, que son todos los primos menores que 100.
    En la siguiente tabla tenemos todos los primos menores que 1000, que hacen un total de 168 (21×8)

2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73
79	83	89	97	101	103	107	109	113	127	131	137	139	149	151	157	163	167	173	179	181
191	193	197	199	211	223	227	229	233	239	241	251	257	263	269	271	277	281	283	293	307
311	313	317	331	337	347	349	353	359	367	373	379	383	389	397	401	409	419	421	431	433
439	443	449	457	461	463	467	479	487	491	499	503	509	521	523	541	547	557	563	569	571
577	587	593	599	601	607	613	617	619	631	641	643	647	653	659	661	673	677	683	691	701
709	719	727	733	739	743	751	757	761	769	773	787	797	809	811	821	823	827	829	839	853
857	859	863	877	881	883	887	907	911	919	929	937	941	947	953	967	971	977	983	991	997

Cómo averiguar si un número es primo.

    El algoritmo más sencillo que puede utilizarse para saber si un número n es primo es el de la división. Se trata de ir probando para ver si tiene algún divisor propio. Para ello vamos dividiendo el número n entre 2, 3, 4, 5, ... , n-1. Si alguna de las divisiones es exacta (da resto cero) podemos asegurar que el número n es compuesto. Si ninguna de estas divisiones es exacta, el número n es primo. Este método puede hacerse más eficiente observando simplemente, que si un número es compuesto alguno de sus factores (sin contar el 1) debe ser menor o igual que √ n. Por lo tanto, el número de divisiones a realizar es mucho menor. Sólo hay que dividir entre 2, 3, 4, 5, ... , [√ n]. En realidad, bastaría hacer las divisiones entre los números primos menores o iguales que √ n.

     Ejemplo: Para probar que 227 es primo sabiendo que √227 = 15'0665... basta con ver que no es divisible entre 2, 3, 5, 7, 11 y 13.

     Este procedimiento resulta eficiente para números pequeños o que tienen factores pequeños. Sin embargo si el número tiene por ejemplo unas 20 cifras y es primo, habrá que realizar miles de millones de divisiones para comprobarlo.  Aunque un ordenador pueda realizar millones de divisiones en un segundo, el tiempo necesario es bastante considerable. Y cuando el número de dígitos aumenta el tiempo necesario ¡¡crece de forma exponencial!!

    Ejemplo práctico: Supongamos que queremos saber si un número de unas 50 cifras es primo. La raíz cuadrada de un número de este orden está en torno a 10²⁵. Si un ordenador hace 1000 millones de divisiones por segundo, necesitará 10²⁵/10⁹ segundos; es decir, 10¹⁶ segundos. Este tiempo equivale, aproximadamente, a 1'6*10¹⁴ minutos, que son 2'7*10¹² horas, o también 1'16*10¹¹ días, aproximadamente  3'17*10⁸ años. Que para hacer esto se necesiten 317.097.920 años se me antoja una tarea poco recomendable. Y si nos decidiésemos a llevarla a cabo, ¿sería útil esta información pasado todo este tiempo?  O más drástico todavía, ¿seguiría existiendo nuestra especie entonces?

    Debemos pues, buscar una alternativa que nos permita responder a este problema de una forma más favorable; necesitamos un algoritmo más eficiente.

    Una respuesta puede ser el teorema pequeño de Fermat. Este teorema afirma que si n es primo y mcd(a,n) = 1, entonces a^n-1 ≡ 1 (mod n). Hay que tener en cuenta que la exponenciación modular puede realizarse en un tiempo bastante favorable, si se hace de forma adecuada (hay algoritmos que nos dan la respuesta en tiempo polinómico)

    Ejemplo: Queremos comprobar si el número 15 es primo o no (utilizando esta propiedad). Tomamos a = 2, n = 15, y evaluamos 2¹⁴ (mod 15). La respuesta es 2¹⁴ ≡ 4 (mod 15). Podemos asegurar entonces que 15 es compuesto. Probemos con a = 2, n = 341, evaluamos 2³⁴⁰ (mod 341) y obtenemos que 2³⁴⁰ ≡ 1 (mod 341). Esto no nos permite deducir que 341 sea compuesto, pero tampoco que sea primo. Al probar con a=3 tenemos 3³⁴⁰ ≡ 56 (mod 341), lo cual implica que 341 es compuesto. 

    A los números que se comportan como el 341 en el ejemplo anterior se les llama pseudoprimos para la base 2 (se comportan como un primo para a=2). Este comportamiento es bastante más peculiar peculiar para algunos números. Tomando por ejemplo a=2 y n=561, obtenemos que 2⁵⁶⁰ ≡ 1 (mod 561), 3⁵⁶⁰ ≡ 1 (mod 561), 5⁵⁶⁰ ≡ 1 (mod 561)  y así con todas las bases con las que probemos. Es decir, se comporta como un primo para cualquier base que elijamos. Sin embargo, 561 es compuesto (561 = 3·11·17). A los números que como éste, son pseudoprimos para todas las bases se les llama números de Carmichael. Los números de Carmichael menores que 100.000 son 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973 y 75361. 

Desde luego, no parecen muy abundantes. Los expertos se preguntaban en los años 80 si serían un conjunto finito, con lo cual una vez identificados se podrían "evitar" fácilmente, aunque la creencia generalizada apuntaba a que el conjunto era infinito. Se demostró que si un número es de Carmichael debe ser libre de cuadrados y producto de al menos tres primos distintos. En 1994, Alford, Granville y Pomerance demostraron que existen infinitos números de Carmichael. De hecho, su resultado indica que para n suficientemente grande C(n) > n^2/7, donde C(n) es la cantidad de números de Carmichael menores que n.

    Para evitar este contratiempo, podemos recurrir a un teorema un poco más fino debido a Euler. Este resultado afirma que si n es primo y mcd (a,n)=1, entonces a^(n-1)/2 ≡ ±1 (mod n). Con esto evitamos que algunos números compuestos puedan pasar por primos como ocurre utilizando el teorema pequeño de Fermat.

    Ejemplo: Para comprobar que 91 es compuesto basta ver 2⁴⁵ ≡ 57 (mod 91). ¿Y que pasa con un número de Carmichael como el 561?. Veamos 2²⁸⁰ ≡ 1(mod 561), pero 5²⁸⁰ ≡ 67 (mod 561). Parece que esto funciona.

    Pero todavía podemos afinar un poco más. La idea es que si n es primo, entonces Z_n es un cuerpo. Y en un cuerpo las únicas raíces cuadradas de 1 son 1 y -1. En el último ejemplo estamos diciendo que Z₅₆₁ no es un cuerpo porque en él, la raíz de 1 es 67, y por tanto 561 no es primo. Si tomamos n-1 y lo dividimos entre 2 de forma sucesiva, mientras sea posible, estamos extrayendo raíces cuadradas y se trata de comprobar si los resultados dan siempre 1 ó -1. Esto da lugar al test de Miller-Rabin.

    Ejemplo: Tomando n = 561 hacemos 2²⁸⁰ (mod 561) ≡ 1 ,  2¹⁴⁰ (mod 561) ≡ 67, que continuaría con 2⁷⁰ y  2³⁵, pero ya no es necesario calcularlos porque tenemos que la raíz cuadrada de 1 es 67 (mod 561). Por tanto, 561 es compuesto.

    Si al llegar a 2³⁵ no obtenemos un resultado distinto de +1 ó -1, tendríamos que elegir otra base. Y ahí es donde podemos tener dificultades, porque si n es bastante grande quizá tengamos que probar con muchas bases y la respuesta tardará en llegar. Y podemos empezar a preguntarnos si la tardanza se debe a que n es primo o porque es un compuesto que se comporta como un primo para un conjunto "grande" de bases. ¿Qué debemos hacer entonces? La solución es determinar el número de bases con las que tenemos que probar para asegurar que un número compuesto no pase la prueba como si fuese primo.

Definiciones: 

Si un entero n compuesto e impar verifica la congruencia de Euler para la base b, entonces n es un pseudoprimo de Euler para la base b. Asímismo, si n pasa el test de Miller-Rabin para la base b, entonces n es un pseudoprimo fuerte para la base b. Los siguientes resultados nos dan la respuesta a la cuestión del párrafo anterior.

Proposición: Si n es compuesto e impar, al menos la mitad de las bases b que verifican 0<b<n, no satisfacen la congruencia de Euler.

Teorema (Rabin): Si n es un entero compuesto impar, entonces n es un pseudoprimo fuerte para la base b, para a lo sumo un 25% de las posibles bases que verifican 0 < b < n, mcd(b,n) = 1.

    Desde luego que el teorema anterior no es para tirar cohetes. Probar con un 25% de las bases es algo descomunal si n es un número grande. Sin embargo, también hay que decir, que experimentalmente se ha comprobado que el test es mucho más eficiente de lo que indica la acotación del 25%. Es decir, cuando el número es compuesto, basta probar con unas pocas bases (la mayoría de veces con una sola) para demostrar que el número es compuesto. Si probamos con varias bases y nuestro número pasa el test, la probabilidad de que sea primo es muy pequeña. Y se puede elegir el número de bases que queramos de manera que la probabilidad sea menor que una cota prefijada de antemano.

Yendo un poco más lejos, hay un resultado de Miller basado en la hipótesis generalizada de Riemann, que afirma lo siguiente:

Teorema (Miller, 1976): 

Si la hipótesis generalizada de Riemann es cierta y n es un entero compuesto impar, entonces n no pasa el test de Miller-Rabin para alguna base b < 2·log²n  (¿¿teorema de bach, aukemy, montgomery 1985??)

    Este resultado implicaría un test de primalidad en tiempo polinómico del orden de O(log⁵n).

    En la tabla de abajo podemos ver la cantidad de números de Carmichael y pseudoprimos para la base 2. Por ejemplo, el primer 1 de la fila que comienza con 10³ indica que sólo hay un número de Carmichael menor que 1000, y el 3 que sigue que hay 3 pseudoprimos para la base 2 menores que 1000. 

( Nota: Los pseudoprimos de Euler también son llamados a veces pseudoprimos de Euler-Jacobi )

10n	Carmichael	psprimos(2)	pspEuler(2)	pspFuerte(2)
101	0	0	0	0
102	0	0	0	0
103	1	3	1	0
104	7	22	12	5
105	16	78	36	16
106	43	245	114	46
107	105	750	375	162
108	255	2057	1071	488
109	646	5597	2939	1282
1010	1547	14884	7706	3291
1011	3605	38975	20417	8607
1012	8241	101629	53332	22407
1013	19279	264239	124882	58892

    Los primeros pseudoprimos para la base 2 son 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, ...
    Los primeros pseudoprimos para la base 3 son 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2821,...
    Los primeros pseudoprimos para la base 5 son 4, 124, 217, 561, 781, 1541, 1729, 1891, ...

    Los primeros pseudoprimos de Euler para la base 2 son 561, 1105, 1729, 1905, 2047, 2465, ...
    Los primeros pseudoprimos de Euler para la base 3 son 121, 703, 1729, 1891, 2821, 3281, 7381, ...

    Los primeros pseudoprimos fuertes para la base 2 son 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ...

    Los primeros pseudoprimos fuertes para la base 3 son 121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, ...

    Estos ejemplos nos permiten ver que si en lugar de la base 2 utilizamos las bases 2 y 3, los números que pueden pasar el test siendo compuestos son muchos menos. Y si tomamos más bases todavía, los resultados mejoran considerablemente. Por ejemplo, sólo hay un pseudoprimo fuerte para las bases 2, 3, 5 y 7 menor que 25·10⁹, y este número es 3,215,031,751.

    La sucesión de los números impares más pequeños que pasan el test de Miller-Rabin usando los primeros k números primos para k = 1, 2, 3,...  está dada por 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, ... (Sloane A014233; Jaeschke 1993). Por lo tanto, el test es totalmente determinista si usamos los siete primeros números primos (con 8 no da ninguna mejora) para números menores menores de 3,4·10^14.

    Lo que se hace en la práctica para números muy grandes es tomar una serie de bases al azar y comprobar si se verifican las congruencias. Si no se verifica en algún caso, el número es compuesto con total seguridad. Si se verifican todas, hay una "sospecha" muy grande de que el número es primo, aunque no puede asegurarse. La probabilidad de error puede hacerse tan pequeña como se quiera con solo coger un número suficiente de bases.

Gracias a los trabajos de Pomerance, Selfridge y Wagstaff (1980) y Jaeschke (1993) podemos elaborar tests de rápida ejecución y completamente deterministas (usando Miller-Rabin) si consideramos números hasta un cierto tamaño:

• Para números menores que 25,326,001 basta probar con las bases 2, 3 y 5.
• Para números menores que 4,759,123,141 basta probar con las bases 2, 7 y 61.
• Para números menores que 2,152,302,898,747 basta probar con las bases 2, 3, 5, 7 y 11.
• Para números menores que 341,550,071,728,321 basta probar con las bases 2, 3, 5, 7, 11, 13 y 17.

 En 1980, Adleman publica un artículo titulado "On distinguishing prime numbers from composite numbers". Sus resultados son mejorados por Pomerance, Rumely, Cohen, H.W. Lenstra y A.K. Lenstra. Esta trabajo conjunto junto con el teorema que viene a continuación dan lugar a un test de primalidad conocido como APR (hay más de una versión de este test)

Teorema (Odlyzko-Pomerance, 1982):

 Existe una constante c>0 efectivamente computable tal que para todo n > e^e existe un entero positivo  que satisface:
     i)  t es libre de cuadrados.
    ii)  0 < t < (log n)^{c·log(log(log n))} y tal que s(t) > √ n , donde s(t) = Π { q ∈ Z⁺ / q primo y q-1 divisor de t }

El test APR seguiría entonces los siguientes pasos:

Paso1: Introducimos un primo impar n.
Paso2: Buscamos (secuencialmente) un valor t que verifique s = s(t) > √ n.
Paso3: Factorizamos t. A sus factores p_i les llamamos primos iniciales.
Paso4: Factorizamos s. A sus factores q_i les llamamos primos euclídeos.
Paso5: Se comprueba que mcd (s·t, n) = 1 (si no es el caso, n no es primo)

Paso6: Para cada primo inicial p se tiene una de estas dos opciones:
    a)  n^p-1 ≠ 1 (mod p²)
    b)  n^p-1 ≡ 1 (mod p²) y para cada primo euclídeo q tal que p | q-1 existe un carácter ξ (aplicación de un grupo en el cuerpo de los números complejos) ξ: Z_q^* --------> G_p de orden p y conductor q, tal que G(ξ)ⁿ ∈ η(ξ)ⁿ·G(ξⁿ) módulo nZ[ξ_p, ξ_q] para algún 1 ≠ η(ξ) ∈ G_p (revisar)
    Si se da el caso a) probamos con otro primo inicial y si se da b) seguimos con el paso 7.

Paso7: Para cada i = 0, 1, 2, 3, ... , t-1 se calcula mcd( nⁱ (mod s) , n). Si alguno de los resultados obtenidos es un número comprendido estrictamente entre 1 y n entonces el número n es compuesto. Si todos los resultados dan 1 ó n, entonces podemos estar seguros de que n es primo. 

(continuará con AKS, Agrawal 2002)

Cuántos números primos hay

    Una de las primeras preguntas que podemos hacernos es si la cantidad de números primos es finita o infinita. Euclides de Alejandría demostró que hay infinitos. Supongamos que existe solamente un número finito de primos. Sea C = { p₁, p₂, ... p_n } el conjunto formado por todos ellos. Consideremos ahora el número M = p₁×p₂× ... p_n+1. Como cada primo p_i es mayor que 1, M es un número mayor que cualquiera de los p_i; es decir, M no está en el conjunto C y por tanto es compuesto. Admitirá entonces una descomposición como producto de factores primos (por el teorema fundamental de la aritmética). Por hipótesis, estos factores sólo pueden estar entre los primos que aparecen en el conjunto C. Por tanto, existirá un primo q del conjunto C, tal que q | M y obviamente, q | p₁×p₂× ... p_n. Por consiguiente, q divide a la diferencia M - p₁×p₂× ... ×p_n (que es 1). Pero ningún número primo divide a 1, y q es un número primo que divide a 1 (Contradicción). Concluimos entonces que el conjunto de los números primos nopuede ser finito (q.e.d.)

    Hay otras demostraciones posibles, como la de Euler, que se obtiene como corolario de un teorema que afirma que la suma de la serie de los inversos de los números primos es divergente. Otra demostración más reciente (y sencilla de hacer) fue obtenida por Polya basándose en los números de Fermat. Más adelante veremos más sobre estos números que se definen como F_n=2^(2ⁿ)+1. Así, F₁=5, F₂=17, F₃=257, etc. Polya observó y demostró que para todo k>0 se tiene que F_n y F_n+k son coprimos; es decir, no tienen factores comunes. Esto implica la infinitud de los números primos, ya que cada uno de los F_n da lugar a uno o varios números primos que no aparecen en los anteriores números de Fermat. Curioso, ¿no? La demostración es como sigue:

    Observamos en primer lugar que todos los números de Fermat son impares, evidente. En segundo lugar hay que ver que F_n+k-2 es múltiplo de F_n para todo k>0. Para ello sólo hay que seguir este cálculo:

Ahora, si m ¹ 1 es un divisor común de F_n y F_n+k , entonces m es divisor de F_n+k - 2 y F_n+k , y por tanto de su diferencia; es decir, m es divisor de 2 al mismo tiempo que de F_n que es impar. Contradicción. Podemos concluir entonces que cualesquiera dos números de Fermat no tienen ningún factor en común, q.e.d.

Otra demostración interesante se la debemos a Erdos: Consideremos un número x fijo y sean p₁, p₂, ..., p_n £ x, los números primos menores o iguales que x. .Como todo entero puede expresarse como producto de un cuadrado por un número libre de cuadrados, podemos escribir cada entero m £ x de la forma

donde e_i ∈ {0, 1} y Q² ≤ x. Podemos elegir los e_i de 2ⁿ formas diferentes, y Q de r(x) formas y, por tanto, podemos asegurar que todos los números m ≤ x pueden escribirse alguna de estas 2ⁿ·r(x) formas, o sea, x ≤ 2ⁿ·r(x). Ahora, despejamos n de esta expresión, x ≤ 4ⁿ, y por tanto, n ≥ ln x / ln 4. El número de primos es mayor que cualquier número x fijado de antemano, q.e.d.

 La sucesión de los números primos

        La sucesión de los números primos es poco predecible. No sabemos si obedecerán algún tipo de regla u orden que no hemos sido capaces de descubrir todavía. Durante siglos, las mentes más preclaras intentaron poner fin a esta situación pero sin éxito. Leonhard Euler comentó en una ocasión: "Los matemáticas han intentado en vano hasta la fecha descubrir algún orden en la sucesión de los números primos, y tenemos razones para creer que es un misterio en el que la mente no podrá penetrar nunca".  En una conferencia dada por D. Zagier en 1975, éste dijo: "Hay dos hechos en torno a la distribución de los números primos que espero crean tan abrumadoramente, que quedarán por siempre grabadas en sus corazones. La primera es que a pesar de su sencilla definición y de su papel como ladrillos que construyen los números naturales, los números primos crecen como  la mala hierba alrededor de los números naturales, simulando no obedecer otra ley que la del azar, y nadie puede predecir donde brotará el siguiente. El segundo hecho es incluso más asombroso, porque dice justamente lo opuesto: que los números primos hacen gala de una pasmosa regularidad, que hay leyes que gobiernan su comportamiento, y que obedecen esas leyes con una precisión casi militar" (Havil 2003)

      Pero el espíritu del hombre es obstinado y su inquietud por descubrir no conoce fronteras. Así, con el paso de los años y los siglos se ha ido avanzando a pequeños pasos, pero tantos, que al mirar atrás parecen gigantescos. En primer lugar presentamos una tabla con las cifras del número primo que ocupa el lugar 10ⁿ-ésimo. Lectura: El primo que ocupa el lugar 1000 (10³) en la sucesión de los números primos es 7919.

= n =	Primo 10n	Número de cifras	|	= n =	Primo 10n	Número de cifras
0	2	1	|	11	2760727302517	13
1	29	2	|	12	29996224275833	14
2	541	3	|	13	323780508946331	15
3	7919	4	|	14	3475385758524527	16
4	104729	6	|	15	37124508045065437	17
5	1299709	7	|	16	394906913903735329	18
6	15485863	8	|	17	4185296581467695669	19
7	179424673	9	|	18	44211790234832169331	20
8	2038074743	10	|	19	465675465116607065549	21
9	22801763489	11	|	20	4892055594575155744537	22
10	252097800623	12	|	21	?	23

    Otra posibilidad es contar cuántos primos acaban en una determinada cifra o cuántos son de una determinada forma como 4k+1 ó 4k+3. Por ejemplo, los números primos de la forma 4k+1 son 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97... y los de la forma 4k+3 son 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83... Para abreviar los llamaremos primos de tipo 1 y de tipo 3 respectivamente. Observamos que de los 24 primos enumerados, 11 son del tipo 1 y 13 del tipo 3. Contando el número de primos de cada tipo hasta 100.000 obtenemos:

x	Primos 4k+1	Primos 4k+3		x	Primos 4k+1	Primos 4k+3
100	11	13		10.000	609	619
200	21	24		20.000	1.125	1.136
300	29	32		50.000	2.549	2.583
400	37	40		70.000	3.491	3.443
500	44	50		100.000	4.783	4.808
600	51	57		200.000	8.995	8.988
700	59	65		300.000	13.026	12.970
800	67	71		400.000	16.967	16.892
900	74	79		500.000	20.804	20.733
1000	80	87		600.000	24.573	24.524
2000	147	155		700.000	28.306	28.236
3000	222	207		800.000	32.032	31.918
5000	329	339		900.000	35.676	35.597
7000	442	457		1.000.000	39.266	39.231

 Observamos que los primos de tipo 3 van ganando por un escaso margen a los de tipo 1. Este fenómeno fue observado ya por  Tchebychev, que se lo contaba en una carta a M. Fuss el 23 de marzo de 1853.Este sesgo resulta quizás inesperado en vista de un importante resultado en la teoría analítica de los números conocido como “el teorema de los números primos para progresiones aritméticas”. Este resultado nos dice que, para todo módulo a, los primos tienden a distribuirse equitativamente entre las diferentes progresiones an + b tales que mcd(a, b) = 1. Esto implica entre otras cosas que cualquier progresión aritmética contiene infinitos primos, hecho que fue conjeturado ya por Gauss y demostrado por Dirichlet en 1837. También nos permite deducir que existe "el mismo número de primos" acabados en 1, 3, 7 ó 9, tomando como progresiones aritméticas 10n+1, 10n+3, 10n+7 y 10n+9.

x	10n + 1	10n + 3	10n + 7	10n + 9
100	5	7	6	5
200	10	12	12	10
500	22	24	24	23
1.000	40	42	46	38
2.000	73	78	77	73
5.000	163	172	169	163
10.000	306	310	308	303
20.000	563	569	569	559
50.000	1274	1290	1288	1279
100.000	2387	2402	2411	2390
200.000	4478	4517	4503	4484
500.000	10386	10382	10403	10365
1.000.000	19617	19665	19621	19593

    El intento de "controlar" los números primos llevo a muchos a la búsqueda de algún tipo de fórmula o expresión algebraica que generase la sucesión de los números primos. Goldbach demuestra en 1752 que no existe ningún polinomio con coeficientes enteros que dé números primos para cualquier valor entero. Años después Legendre demuestra que no existe ninguna función algebraica racional que cumpla tal requisito. Queda por decir que todavía se puede buscar un polinomio de forma que produzca una sucesión de números primos lo más larga posible. Euler propuso el polinomio n² + n + 41 que da números primos para valores 0 ≤ n < 40 (también para 40 < n < 81 excepto n = 41, 44, 49, 56, 65 y 76 [sucesión cuadrática]).

    Otro resultado que hay que mencionar, a pesar de los resultados de Goldbach y Legendre, es que se ha podido encontrar un polinomio en 10 variables con coeficientes enteros que da números primos siempre que se sustituyan las variables por enteros no negativos. Jones, Sato, Wada y Wiens han hallado un polinomio de grado 25 en 26 variables cuyos valores positivos son exactamente los números primos.

    Otra fórmula que produce únicamente números primos tiene que ver con una constante q = 1'3063778..., conocida como constante de Mills (el menor número que tiene esta propiedad). Tomando f(n) = [θ^(3ⁿ)] siempre se obtienen números primos, donde [x] representa la parte entera de x. Los primeros valores de f(n) son 2, 11, 1361, 2521008887, ... No se sabe todavía si θ es racional o irracional (febrero 2012).

    Hacia 1845 Joseph Bertrand propone que para cada entero positivo n, existe al menos un primo p tal que n < p < 2n. Esta proposición conocida como postulado de Bertrand, fue demostrada por Tchebychev en 1850. En 1919, Ramanujan prueba que para n > 5, existen al menos dos primos entre n y 2n; para n > 8, existen al menos tres primos entre n y 2n; para n > ?, existen al menos cuatro primos entre n y 2n. De forma más general, demuestra que para cada k > 0, existen k primos entre n y 2n salvo para un número finito de casos. Erdös, en 1932, consigue una prueba bastante más simple del caso de dos primos entre n y 2n para n>6, añadiendo además que uno de esos dos primos debe ser de la forma 4k+1 y el otro de la forma 4k+3.

    Otra cuestión similar (pero más restrictiva) había sido propuesta por Legendre unos años antes de la demostración de Tchebychev. Legendre conjeturó que existe al menos un primo entre n² y (n+1)² para todo entero n > 0. La conjetura sigue sin demostrarse.

Fuente:

http://mimosa.pntic.mec.es/jgomez53/matema/conocer/primos.htm

Video relacionado sobre el tema: