En teoría de números, un número primo largo, (o también primo repetitivo completo, o primo propio)Dickson, Leonard E., 1952, History of the Theory of Numbers, Volume 1, Chelsea Public. Co. en base b, es un número primo impar p tal que el cociente de Fermat
(donde p no divide a b) genera un número cíclico. Por lo tanto, la expansión en base b de repite infinitamente los dígitos del número cíclico correspondiente, al igual que con la rotación de los dígitos para cualquier a entre 1 y p − 1. El número cíclico correspondiente al primo p poseerá p − 1 dígitos si y solo si p es un número primo largo. Es decir, el orden multiplicativo = p − 1, lo que equivale a que b cumpla el ser una raíz
numérica
módulo p.
El término primo largo fue utilizado por John Conway y Richard Guy en su "Libro de los Números". De manera confusa, Sloane de OEIS se refiere a estos números primos como números cíclicos.
Base 10 Se puede suponer que se trabaja en base 10 si no se especifica la base, en cuyo caso la expansión del número se denomina número decimal periódico. En base 10, si una repetición completa termina en el dígito 1, entonces cada dígito 0, 1, ..., 9 aparece en la repetición el mismo número de veces que los demás dígitos (para tales números primos en base 10, consúltese ). De hecho, en base b, si un primo largo termina en el dígito 1, entonces cada dígito 0, 1, ..., b − 1 aparece en la repetición el mismo número de veces que los demás dígitos, pero tal número primo no existe cuando b = 12, ya que cada número primo completo en base 12 termina en el dígito 5 o 7 en la misma base. Generalmente, no existe tal número primo cuando b es congruente a 0 o 1 módulo 4.
Los valores de p menores a 1000 para los cuales esta fórmula produce números cíclicos en expresión decimal son: 7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983, ...
Por ejemplo, el caso b = 10, p = 7 da el número cíclico 142857; por lo tanto, 7 es un número primo largo. Además, 1 dividido por 7 escrito en base 10 es
No todos los valores de p producirán un número cíclico usando esta fórmula; por ejemplo, p = 13 da Estos casos fallidos siempre contendrán una repetición de dígitos (posiblemente varios) en el transcurso de p − 1 dígitos.
El patrón conocido de esta sucesión viene de la teoría de números algebraicos. Específicamente, esta sucesión es el conjunto de primos p tal que 10 es una raíz primitiva módulo p. La conjetura de Artin sobre raíces primitivas es que esta secuencia contiene el 37.395...% de los números primos.
Patrones de aparición de números primos largos Mediante aritmética modular avanzada se puede demostrar que cualquier número primo de las siguientes formas:
nunca puede ser un primo largo en base 10. Los primeros primos de estas formas, con sus periodos, son:
40k + 140k + 340k + 940k + 1340k + 2740k + 3140k + 3740k + 3941periodo 53periodo 189periodo 4413periodo 667periodo 3331periodo 1537periodo 379periodo 13241periodo 3043periodo 21409periodo 20453periodo 13107periodo 5371periodo 35157periodo 78199periodo 99281periodo 2883periodo 41449periodo 32173periodo 43227periodo 113151periodo 75197periodo 98239periodo 7401periodo 200163periodo 81569periodo 284293periodo 146307periodo 153191periodo 95277periodo 69359periodo 179521periodo 52283periodo 141769periodo 192373periodo 186347periodo 173271periodo 5317periodo 79439periodo 219601periodo 300443periodo 221809periodo 202613periodo 51467periodo 233311periodo 155397periodo 99479periodo 239
Sin embargo, los estudios muestran que dos tercios de los primos de la forma 40k + n, donde n ∈ {7, 11, 17, 19, 21, 23, 29, 33} son primos largos. Para algunas secuencias, la preponderancia de números primos largos es mucho mayor. Por ejemplo, 285 de los 295 primos de la forma 120k + 23 por debajo de 100000 son números primos largos, siendo 20903 el primero que no lo es.
Números primos largos binarios En sistema binario, los primos largos son: (menores que 1000)
3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821, 827, 829, 853, 859, 877, 883, 907, 941, 947, ...
Para estos números primos, 2 es una raíz primitiva módulo p, por lo que 2n módulo p puede ser cualquier número natural entre 1 y p − 1.
Estas secuencias de período p − 1 tienen una función de autocorrelación que tiene un pico negativo de −1 para el desplazamiento de . La aleatoriedad de estas secuencias ha sido examinada mediante los tests diehard.Bellamy, J. "Randomness of D sequences via diehard testing". 2013. .
Todos ellos son de la forma 8k + 3 o 8k + 5, porque si p = 8k + 1 o 8k + 7, entonces 2 es un residuo cuadrático módulo p, por lo que p divide a , y el periodo de en base 2 debe dividir a y no puede ser p − 1, por lo que no son primos largos en base 2.
Además, todos los primos seguros congruentes con 3 módulo 8 son primos largos en base 2. Por ejemplo, 3, 11, 59, 83, 107, 179, 227, 347, 467, 563, 587, 1019, 1187, 1283, 1307, 1523, 1619, 1907, etc. (menores de 2000).
Las secuencias de primos largos binarios (también llamadas secuencias decimales de longitud máxima) han encontrado aplicaciones en criptografía y código de corrección de errores.Kak, Subhash, Chatterjee, A. "On decimal sequences". IEEE Transactions on Information Theory, vol. IT-27, pp. 647–652, September 1981. En estas aplicaciones, generalmente se utilizan decimales periódicos en base 2, lo que da lugar a secuencias binarias. También se ha analizado la secuencia binaria de longitud máxima para (cuando 2 es una raíz primitiva de p).Kak, Subhash, "Encryption and error-correction using d-sequences". IEEE Trans. On Computers, vol. C-34, pp. 803–809, 1985.
La siguiente tabla contiene los períodos (en binario) de los números primos congruentes con 1 o 7 (mod 8): (menores de 1000)
8k + 11741738997113137193233241257281313337353401409433449457521569periodo8209114828689629241670156218820020472224762602848k + 15775936016176416737617698098578819299379539771009103310491097112911531193periodo14414825154644838038440442855464117684885042582622745642882988k + 772331477179103127151167191199223239263271311359367383431439periodo3115233539517158395993711913113515517918319143738k + 74634794875035996076316477197277437518238398638879119199679839911031periodo2312392432512993034532335912137137541141943144391153483491495515
Ninguno de ellos es un número primo largo binario.
El periodo binario de cada n-ésimo primo es
2, 4, 3, 10, 12, 8, 18, 11, 28, 5, 36, 20, 14, 23, 52, 58, 60, 66, 35, 9, 39, 82, 11, 48, 100, 51, 106, 36, 28, 7, 130, 68, 138, 148, 15, 52, 162, 83, 172, 178, 180, 95, 96, 196, 99, 210, 37, 226, 76, 29, 119, 24, 50, 16, 131, 268, 135, 92, 70, 94, 292, 102, 155, 156, 316, 30, 21, 346, 348, 88, 179, 183, 372, 378, 191, 388, 44, ... (esta secuencia comienza en n = 2, o primo = 3)
El nivel del período binario de cada n-ésimo primo es
1, 1, 2, 1, 1, 2, 1, 2, 1, 6, 1, 2, 3, 2, 1, 1, 1, 1, 2, 8, 2, 1, 8, 2, 1, 2, 1, 3, 4, 18, 1, 2, 1, 1, 10, 3, 1, 2, 1, 1, 1, 2, 2, 1, 2, 1, 6, 1, 3, 8, 2, 10, 5, 16, 2, 1, 2, 3, 4, 3, 1, 3, 2, 2, 1, 11, 16, 1, 1, 4, 2, 2, 1, 1, 2, 1, 9, 2, 2, 1, 1, 10, 6, 6, 1, 2, 6, 1, 2, 1, 2, 2, 1, 3, 2, 1, 2, 1, 1, ...
Sin embargo, estudios numéricos demuestran que las tres cuartas partes de los números primos de la forma 8k + n, donde n ∈ {3, 5} son números primos largos en base 2 (por ejemplo, hay 87 números primos por debajo de 1000 congruentes con 3 o 5 módulo 8, y 67 de ellos son números primos largos en base 2, lo que supone un total del 77 %). Para algunas secuencias, la preponderancia de números primos largos es mucho mayor. Por ejemplo, 1078 de los 1206 números primos de la forma 24k + 5 por debajo de 100000 son números primos de largos en base 2, siendo 1013 el primero que no lo es en base 2.
Primos largos de n-ésimo nivel
Un primo largo de n-ésimo nivel es un primo p que tiene n ciclos diferentes en expansiones de (k es un número entero, 1 ≤ k ≤ p−1). En base 10, los números primos largos de nivel n más pequeños son
7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289, 859, 239, 27581, 9613, 18131, 13757, 33931, 9161, 118901, 6763, 18233, 1409, 88741, 4003, 5171, 19489, 86143, 23201, ...
En base 2, los números primos largos de nivel n más pequeños son
3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593, 17029, 2687, 42701, 11161, 13099, 1103, 71293, 13121, 17467, 2143, 83077, 25609, 5581, 5153, 26227, 2113, 51941, 2351, ...