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. (y también como 15·1)

    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 10 10 10 10 11 12 13 13 13 14 15 15 16 16 17 17 181
1 3 7 9 3 7 1 7 9 9 1 7 3 7 3 9
19 19 19 19 21 22 22 22 23 23 24 25 25 26 26 27 27 28 28 29 307
1 3 7 9 1 3 7 9 3 9 1 1 7 3 9 1 7 1 3 3
31 31 31 33 33 34 34 35 35 36 37 37 38 38 39 40 40 41 42 43 433
1 3 7 1 7 7 9 3 9 7 3 9 3 9 7 1 9 9 1 1
43 44 44 45 46 46 46 47 48 49 49 50 50 52 52 54 54 55 56 56 571
9 3 9 7 1 3 7 9 7 1 9 3 9 1 3 1 7 7 3 9
57 58 59 59 60 60 61 61 61 63 64 64 64 65 65 66 67 67 68 69 701
7 7 3 9 1 7 3 7 9 1 1 3 7 3 9 1 3 7 3 1
70 71 72 73 73 74 75 75 76 76 77 78 79 80 81 82 82 82 82 83 853
9 9 7 3 9 3 1 7 1 9 3 7 7 9 1 1 3 7 9 9
85 85 86 87 88 88 88 90 91 91 92 93 94 94 95 96 97 97 98 99 997
7 9 3 7 1 3 7 7 1 9 9 7 1 7 3 7 1 7 3 1

Póster con los números primos hasta 1000 (pdf)     Listado con los primos menores que
1.000.000 (txt) 
 Para ver los 10.000 primeros números primos pincha aquí

Primos en el anillo de los enteros de Gauss

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 1025. Si un ordenador hace 1000 millones de
divisiones por segundo, necesitará 1025/109 segundos; es decir, 1016 segundos. Este tiempo equivale,
aproximadamente, a 1'6*1014 minutos, que son 2'7*1012 horas, o también 1'16*1011 días,
aproximadamente  3'17*108 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 an-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 214 (mod 15). La respuesta es 214 ≡ 4
(mod 15). Podemos asegurar entonces que 15 es compuesto. Probemos con a = 2, n =
341, evaluamos 2340 (mod 341) y obtenemos que 2340 ≡ 1 (mod 341). Esto no nos
permite deducir que 341 sea compuesto, pero tampoco que sea primo. Al probar con
a=3 tenemos 3340 ≡ 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 2560 ≡ 1 (mod 561), 3560 ≡ 1 (mod 561), 5560 ≡ 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) > n2/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 245 ≡ 57 (mod 91). ¿Y que
pasa con un número de Carmichael como el 561?. Veamos 2280 ≡ 1(mod 561), pero 5280 ≡
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 Zn
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 Z561 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 2280 (mod 561) ≡ 1 ,  2140 (mod 561) ≡ 67, que
continuaría con 270 y  235, 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 235 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·log2n  (¿¿teorema de bach, aukemy, montgomery 1985??)

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

    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 103
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
10 2
0 0 0 0
103 1 3 1 0
10 4
7 22 12 5
10 5
16 78 36 16
10 6
43 245 114 46
107 105 750 375 162
10 8
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

Tabla 2: Pseudoprimos y números de Carmichael

    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·109, 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 > ee existe un entero positivo t 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 pi les llamamos primos iniciales.
Paso4: Factorizamos s. A sus factores qi 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)  np-1 ≠ 1 (mod p2)
    b)  np-1 ≡ 1 (mod p2) 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) ξ: Zq* --------> Gp de
orden p y conductor q, tal que G(ξ)n ∈ η(ξ)n·G(ξn) módulo nZ[ξp, ξq] para algún 1 ≠ η(ξ)
∈ Gp (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( ni (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 = { p1, p2, ... pn }
el conjunto formado por todos ellos. Consideremos ahora el número M = p1×p2× ...
pn+1. Como cada primo pi es mayor que 1, M es un número mayor que cualquiera de los
pi; 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 | p1×p2× ... pn. Por consiguiente, q divide a la diferencia M - p1×p2× ... ×pn
(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 no puede
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 Fn=2^(2n)+1. Así, F1=5, F2=17, F3=257, etc. Polya
observó y demostró que para todo k>0 se tiene que Fn y Fn+k son coprimos; es decir, no
tienen factores comunes. Esto implica la infinitud de los números primos, ya que cada
uno de los Fn 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 Fn+k-2 es múltiplo de Fn para todo k>0. Para ello sólo
hay que seguir este cálculo:

Ahora, si m 1 es un divisor común de Fn y Fn+k , entonces m es divisor de Fn+k - 2 y Fn+k

, y por tanto de su diferencia; es decir, m es divisor de 2 al mismo tiempo que de Fn 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 p1, p2, ..., pn  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 ei ∈ {0, 1} y Q2 ≤ x. Podemos elegir los ei de 2n 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 2n·r(x) formas, o sea, x ≤ 2n·r(x). Ahora, despejamos n de esta
expresión, x ≤ 4n, 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)

Euler commented "Mathematicians have tried in vain to this day to discover some order in the sequence
of prime numbers, and we have reason to believe that it is a mystery into which the mind will never
penetrate" (Havil 2003, p. 163). In a 1975 lecture, D. Zagier commented "There are two facts about the
distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be
permanently engraved in your hearts. The first is that, despite their simple definition and role as the
building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers,
seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout.
The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit
stunning regularity, that there are laws governing their behavior, and that they obey these laws with
almost military precision" (Havil 2003, p. 171).

        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 10n-ésimo. Lectura: El
primo que ocupa el lugar 1000 (103) en la sucesión de los números primos es 7919.

 = n Número de |  = n Número de
Primo 10n Primo 10n
=  cifras =  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

Tabla 3: Dígitos del 10n-ésimo primo

    

        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

Tabla 4: Recuento de primos de la forma 4k+1 y 4k+3 desde 3 hasta x

    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.