Número de Carmichael

format_list_bulleted Contenido keyboard_arrow_down
ImprimirCitar
Número compuesto en la teoría de números

En teoría de números, a Número de carmichael es un número compuesto n{displaystyle n}, que en el aritmético modular satisface la relación congruencia:

bn↑ ↑ b()modn){displaystyle b^{n}equiv B{pmod {n}}

para todos los enteros b{displaystyle b}. La relación también puede expresarse en la forma:

bn− − 1↑ ↑ 1()modn){displaystyle b^{n-1}equiv 1{pmod {n}}.

para todos los enteros b{displaystyle b} que son relativamente primos n{displaystyle n}. Los números de carmichael son nombrados por el matemático estadounidense Robert Carmichael, el término que fue introducido por Nicolaas Beeger en 1950 (Øystein Ore les había referido en 1948 como números con la "propiedad de Fermat", o "F números" para corto). Son infinitas en número.

Robert Daniel Carmichael

constituyen los casos relativamente raros en los que no se mantiene el estricto Converse del pequeño teorema de Fermat. Este hecho impide el uso de ese teorema como una prueba absoluta de primalidad.

Los números de Carmichael forman el subconjunto k 1 de los números de Knödel.

Descripción general

El pequeño teorema de Fermat establece que si p es un número primo, entonces para cualquier número entero b , el número b p - b es un múltiplo entero de p . Los números de Carmichael son números compuestos que tienen esta propiedad. Los números de Carmichael también se llaman pseudoprímenes de Fermat o Pseudoprimes de Fermat absoluto . Un número de Carmichael pasará una prueba de Primalidad Fermat a cada base b relativamente primo al número, aunque en realidad no es primo. Esto hace que las pruebas se basen en el pequeño teorema de Fermat menos efectivo que las pruebas primarias probables fuertes, como la prueba de Primalidad Baillie -PSW y la prueba de Primalidad Miller -Rabin.

Sin embargo, ningún número de Carmichael es un pseudoprime euler -jacobi o un pseudoprime fuerte a cada base relativamente mejor para él Entonces, en teoría, una prueba primaria de Euler o una fuerte probable podría probar que un número de Carmichael es, de hecho, compuesto.

Arnault da un número de Carmichael de 397 dígitos N{displaystyle N} que es fuerte pseudoprime a todos primo bases inferiores a 307:

N=p⋅ ⋅ ()313()p− − 1)+1)⋅ ⋅ ()353()p− − 1)+1){displaystyle N=pcdot (313(p-1)+1)cdot (353(p-1)+1)}

donde

p={displaystyle p=}29674495668685510550154174642905332777199179985304335099507553127683875317701995942385964281211880336647542183455624931687883

es un primo de 131 dígitos. p{displaystyle p} es el factor primario más pequeño N{displaystyle N}, por lo que este número de Carmichael es también un (no necesariamente fuerte) pseudoprime a todas las bases menos que p{displaystyle p}.

A medida que los números se hacen más grandes, los números de Carmichael se vuelven cada vez más raros. Por ejemplo, hay 20,138,200 números de Carmichael entre 1 y 10 21 (aproximadamente uno en 50 billones (5 · 10 13 ) números).

criterio de Korselt ' s

Una definición alternativa y equivalente de números de Carmichael viene dada por el criterio de Korselt ' s .

Theorem (A. Korselt 1899): Un entero compuesto positivo n{displaystyle n} es un número de Carmichael si y sólo si n{displaystyle n} es libre de cuadrados, y para todos los divisores primos p{displaystyle p} de n{displaystyle n}, es cierto que p− − 1▪ ▪ n− − 1{displaystyle p-1mid n-1}.

De este teorema se desprende que todos los números de Carmichael son extraños, ya que cualquier número compuesto que sea libre de cuadrado (y por lo tanto sólo tiene un factor primario de dos) tendrá por lo menos un factor principal impar, y por lo tanto p− − 1▪ ▪ n− − 1{displaystyle p-1mid n-1} resulta en una divisoria incluso de una contradicción extraña. (La rareza de los números de Carmichael también sigue del hecho de que − − 1{displaystyle -1} es un testigo de Fermat para cualquier número incluso compuesto.) Del criterio también sigue que los números de Carmichael son cíclicos. Además, sigue que no hay números de Carmichael con exactamente dos divisores principales.

Discovery

Korselt fue el primero que observó las propiedades básicas de los números de Carmichael, pero no dio ningún ejemplo. En 1910, Carmichael encontró el primer y más pequeño número de este tipo, 561, que explica el nombre " Carmichael Number ".

Václav Šimerka enumera los siete primeros números de Carmichael

Ese 561 es un número de Carmichael se puede ver con el criterio de Korselt. De hecho, 561=3⋅ ⋅ 11⋅ ⋅ 17{displaystyle 561=3cdot 11cdot 17} es libre de cuadrado y 2▪ ▪ 560{displaystyle 2mid 560}, 10▪ ▪ 560{displaystyle 10mid 560} y 16▪ ▪ 560{displaystyle 16mid 560}.

Los siguientes seis números Carmichael son (secuencia A002997 en el OEIS)::

1105=5⋅ ⋅ 13⋅ ⋅ 17()4▪ ▪ 1104;12▪ ▪ 1104;16▪ ▪ 1104){displaystyle 1105=5cdot 13cdot 17qquad (4mid 1104;quad 12mid 1104;quad 16mid 1104)}
1729=7⋅ ⋅ 13⋅ ⋅ 19()6▪ ▪ 1728;12▪ ▪ 1728;18▪ ▪ 1728){displaystyle 1729=7cdot 13cdot 19qquad (6mid 1728;quad 12mid 1728;quad 18mid 1728)}
2465=5⋅ ⋅ 17⋅ ⋅ 29()4▪ ▪ 2464;16▪ ▪ 2464;28▪ ▪ 2464){displaystyle 2465=5cdot 17cdot 29qquad (4mid 2464;quad 16mid 2464;quad 28mid 2464)}
2821=7⋅ ⋅ 13⋅ ⋅ 31()6▪ ▪ 2820;12▪ ▪ 2820;30▪ ▪ 2820){displaystyle 2821=7cdot 13cdot 31qquad (6mid 2820;quad 12mid 2820;quad 30mid 2820)}
6601=7⋅ ⋅ 23⋅ ⋅ 41()6▪ ▪ 6600;22▪ ▪ 6600;40▪ ▪ 6600){displaystyle 6601=7cdot 23cdot 41qquad (6mid 6600;quad 22mid 6600;quad 40mid 6600)}
8911=7⋅ ⋅ 19⋅ ⋅ 67()6▪ ▪ 8910;18▪ ▪ 8910;66▪ ▪ 8910).{displaystyle 8911=7cdot 19cdot 67qquad (6mid 8910;quad 18mid 8910;quad 66mid 8910).}

Estos primeros siete números de Carmichael, de 561 a 8911, fueron encontrados por el matemático checo Václav Šimerka en 1885 (por lo tanto, precediendo no solo a Carmichael sino también a Korselt, aunque Šimerka no encontró nada como Korselt ' s Criterion). Su trabajo, sin embargo, pasó desapercibido.

J. Chernick demostró un teorema en 1939 que se puede utilizar para construir un subconjunto de números de Carmichael. El número ()6k+1)()12k+1)()18k+1){displaystyle (6k+1)(12k+1)(18k+1)} es un número de Carmichael si sus tres factores son todos primos. Si esta fórmula produce una cantidad infinita de números de Carmichael es una pregunta abierta (aunque está implicada por la conjetura de Dickson).

Paul Erdős argumentó heurísticamente que debería haber infinitamente muchos números de Carmichael. En 1994 W. R. (Red) Alford, Andrew Granville y Carl Pomerance utilizaron un límite en la constante de Olson para demostrar que realmente existen números infinitamente muchos Carmichael. Específicamente, mostraron que para lo suficientemente grande n{displaystyle n}, hay al menos n2/7{displaystyle n^{2/7} Números de carmichael entre 1 y 1 n.{displaystyle n.}

Thomas Wright demostró que si a{displaystyle a} y m{displaystyle m} son relativamente primos, entonces hay infinitamente muchos números de Carmichael en la progresión aritmética a+k⋅ ⋅ m{displaystyle a+kcdot m}, Donde k=1,2,...... {displaystyle k=1,2,ldots }.

Löh y Niebuhr en 1992 encontraron algunos números de Carmichael muy grandes, incluido uno con 1,101,518 factores y más de 16 millones de dígitos. Esto se ha mejorado a 10,333,229,505 factores primos y 295,486,761,787 dígitos, por lo que el número de Carmichael más grande es mucho mayor que el mejor mayor conocido.

Propiedades

Factorizaciones

Los números de carmichael tienen al menos tres factores principales positivos. Los primeros números de Carmichael con k=3,4,5,...... {displaystyle k=3,4,5,ldots } los factores principales son (secuencia A006931 en el OEIS:

k
3561=3⋅ ⋅ 11⋅ ⋅ 17{displaystyle 561=3cdot 11cdot 17,}
441041=7⋅ ⋅ 11⋅ ⋅ 13⋅ ⋅ 41{displaystyle 41041=7cdot 11cdot 13cdot 41,}
5825265=5⋅ ⋅ 7⋅ ⋅ 17⋅ ⋅ 19⋅ ⋅ 73{displaystyle 825265=5cdot 7cdot 17cdot 19cdot 73,}
6321197185=5⋅ ⋅ 19⋅ ⋅ 23⋅ ⋅ 29⋅ ⋅ 37⋅ ⋅ 137{displaystyle 321197185=5cdot 19cdot 23cdot 29cdot 37cdot 137,}
75394826801=7⋅ ⋅ 13⋅ ⋅ 17⋅ ⋅ 23⋅ ⋅ 31⋅ ⋅ 67⋅ ⋅ 73{displaystyle 5394826801=7cdot 13cdot 17cdot 23cdot 31cdot 67cdot 73,}
8232250619601=7⋅ ⋅ 11⋅ ⋅ 13⋅ ⋅ 17⋅ ⋅ 31⋅ ⋅ 37⋅ ⋅ 73⋅ ⋅ 163{displaystyle 232250619601=7cdot 11cdot 13cdot 17cdot 31cdot 37cdot 73cdot 163,}
99746347772161=7⋅ ⋅ 11⋅ ⋅ 13⋅ ⋅ 17⋅ ⋅ 19⋅ ⋅ 31⋅ ⋅ 37⋅ ⋅ 41⋅ ⋅ 641{displaystyle 9746347772161=7cdot 11cdot 13cdot 17cdot 19cdot 31cdot 37cdot 41cdot 641,}

Los primeros números de Carmichael con 4 factores prime son (secuencia A074379 en el OEIS):

i
141041=7⋅ ⋅ 11⋅ ⋅ 13⋅ ⋅ 41{displaystyle 41041=7cdot 11cdot 13cdot 41,}
262745=3⋅ ⋅ 5⋅ ⋅ 47⋅ ⋅ 89{displaystyle 62745=3cdot 5cdot 47cdot 89,}
363973=7⋅ ⋅ 13⋅ ⋅ 19⋅ ⋅ 37{displaystyle 63973=7cdot 13cdot 19cdot 37,}
475361=11⋅ ⋅ 13⋅ ⋅ 17⋅ ⋅ 31{displaystyle 75361=11cdot 13cdot 17cdot 31cdot}
5101101=7⋅ ⋅ 11⋅ ⋅ 13⋅ ⋅ 101{displaystyle 101=7cdot 11cdot 13cdot 101,}
6126217=7⋅ ⋅ 13⋅ ⋅ 19⋅ ⋅ 73{displaystyle 126217=7cdot 13cdot 19cdot 73,}
7172081=7⋅ ⋅ 13⋅ ⋅ 31⋅ ⋅ 61{displaystyle 172081=7cdot 13cdot 31cdot 61,}
8188461=7⋅ ⋅ 13⋅ ⋅ 19⋅ ⋅ 109{displaystyle 188461=7cdot 13cdot 19cdot 109,}
9278545=5⋅ ⋅ 17⋅ ⋅ 29⋅ ⋅ 113{displaystyle 278545=5cdot 17cdot 29cdot 113,}
10340561=13⋅ ⋅ 17⋅ ⋅ 23⋅ ⋅ 67{displaystyle 340561=13cdot 17cdot 23cdot 67cdot}

El segundo número Carmichael (1105) se puede expresar como la suma de dos cuadrados en más formas que cualquier número más pequeño. El tercer número de Carmichael (1729) es el número Hardy-Ramanujan: el número más pequeño que se puede expresar como la suma de dos cubos (de números positivos) de dos maneras diferentes.

distribución

Vamos C()X){displaystyle C(X)} denota el número de números de Carmichael menos o igual a X{displaystyle X}. La distribución de los números de Carmichael por poderes de 10 (secuencia A055553 en el OEIS:

n{displaystyle n}1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
C()10n){displaystyle C(10^{n}}0 0 1 7 16 43 105 255 646 1547 3605 8241 19279 44706 105212 246683 585355 1401644 3381806 8220777 20138200

En 1953, Knödel probó el límite superior:

<math alttext="{displaystyle C(X)C()X).Xexp⁡ ⁡ ()− − k1()log⁡ ⁡ Xlog⁡ ⁡ log⁡ ⁡ X)12){displaystyle C(X) wonXexp left({-k_{1}left(log Xlog log Xright)^{frac {1}{2}}right)}<img alt="C(X)

para alguna constante k1{displaystyle K_{1}.

En 1956, Erdős mejoró el límite a

<math alttext="{displaystyle C(X)C()X).Xexp⁡ ⁡ ()− − k2log⁡ ⁡ Xlog⁡ ⁡ log⁡ ⁡ log⁡ ⁡ Xlog⁡ ⁡ log⁡ ⁡ X){displaystyle C(X) {-K_{2}log Xlog log log X}{log log X}right)}}<img alt="C(X)

para alguna constante k2{displaystyle K_{2}. También dio un argumento heurístico que sugiere que este límite superior debe estar cerca de la verdadera tasa de crecimiento C()X){displaystyle C(X)}.

En la otra dirección, Alford, Granville y Pomerance demostraron en 1994 que para X suficientemente grande,

X^{frac {2}{7}}.}" xmlns="http://www.w3.org/1998/Math/MathML">C()X)■X27.{displaystyle C(X) {2}{7}} X^frac{2}{7}." aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ded6498b6e5a53b50beaf3de598a2b702a7d9592" style="vertical-align: -0.838ex; width:13.034ex; height:4.009ex;"/>

En 2005, Harman mejoró aún más este límite para

X^{0.332}}" xmlns="http://www.w3.org/1998/Math/MathML">C()X)■X0.332{displaystyle C(X) X^{0.332}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d25c8f47e36923ead99edae9adba12f0dae7b4a1" style="vertical-align: -0.838ex; width:14.629ex; height:3.176ex;"/>

que posteriormente mejoró el exponente 1/3}" xmlns="http://www.w3.org/1998/Math/MathML">039⋅ ⋅ 0.4736=0,3336704■1/3{displaystyle 0.7039cdot 0,4736=0.33336704]1/3}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f50f706b02ab7549949718a048215943c0033c19" style="vertical-align: -0.838ex; width:35.391ex; height:2.843ex;"/>.

En cuanto a la distribución asintotica de los números de Carmichael, ha habido varias conjeturas. In 1956, Erdős conjectured that there were X1− − o()1){displaystyle X^{1-o(1)} Números de carmichael para X suficientemente grande. En 1981, Pomerance agudizó los argumentos heurísticos de Erdős para conjeturar que hay al menos

X⋅ ⋅ L()X)− − 1+o()1){displaystyle Xcdot L(X)^{-1+o(1)}

Carmichael números hasta X{displaystyle X}, donde L()x)=exp⁡ ⁡ ()log⁡ ⁡ xlog⁡ ⁡ log⁡ ⁡ log⁡ ⁡ xlog⁡ ⁡ log⁡ ⁡ x){displaystyle L(x)=exp {left({frac {log xloglog log x}{log log x}}right)}}}.

Sin embargo, dentro de los rangos computacionales actuales (como los recuentos de números de Carmichael realizados por Pinch hasta 1021), los datos aún no confirman estas conjeturas.

En 2021, Daniel Larsen, estudiante de secundaria de 17 años de Indiana, demostró ser un análogo del postulado de Bertrand para los números de Carmichael primero conjeturado por Alford, Granville y Pomerance en 1994. Usando técnicas desarrolladas por Yitang Zhang y James Maynard para establecer resultados relativos a pequeñas brechas entre los primeros, su trabajo dio la declaración mucho más fuerte que, para cualquier 0}" xmlns="http://www.w3.org/1998/Math/MathML">δ δ ■0{displaystyle delta >0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/595d5cea06fdcaf2642caf549eda2cfc537958a9" style="vertical-align: -0.338ex; width:5.31ex; height:2.343ex;"/> y suficientemente grandes x{displaystyle x} en términos de δ δ {displaystyle delta }, siempre habrá al menos

exp⁡ ⁡ ()log⁡ ⁡ x()log⁡ ⁡ log⁡ ⁡ x)2+δ δ ){displaystyle exp {left({frac {log {x}{log log {x}}{2+delta}}}right)}}

Números de carmichael entre x{displaystyle x} y

x+x()log⁡ ⁡ x)12+δ δ .{displaystyle x+{frac {x}{log {x}}{frac}{frac} {1}{2+delta - Sí.

Generalizaciones

La noción de Carmichael número generaliza a un Carmichael ideal en cualquier campo número K. Para cualquier ideal no cero p{displaystyle {Mathfrak}} dentro OK{fnMicrosoft Sans Serif}, tenemos α α N()p)↑ ↑ α α modp{displaystyle alpha ^{rm {N}({mathfrak {p})}equiv alpha {bmod {cHFF}} para todos α α {displaystyle alpha } dentro OK{fnMicrosoft Sans Serif}, donde N()p){displaystyle {rm {fn} {fn}} {fnMithfrak}}}} es la norma del ideal p{displaystyle {Mathfrak}}. (Esto generaliza el pequeño teorema de Fermat, que mp↑ ↑ mmodp{displaystyle m^{p}equiv # para todos los enteros m cuando p es primo.) Llame a un no cero ideal a{displaystyle {Mathfrak}} dentro OK{fnMicrosoft Sans Serif} Carmichael si no es un ideal primario α α N()a)↑ ↑ α α moda{displaystyle alpha ^{rm {N}({mathfrak {a})}equiv alpha {bmod {fn}} para todos α α ▪ ▪ OK{displaystyle alpha in {matcal {fnK}, donde N()a){displaystyle {rm {fn} {\fnK}} {fn}} {fn}} {fn}}} {\fn}}}} {fnK}}}}}} {fnfn}}}} es la norma del ideal a{displaystyle {Mathfrak}}. Cuando K es Q{displaystyle mathbf {Q}, el ideal a{displaystyle {Mathfrak}} es el director, y si lo dejamos a ser su generador positivo entonces el ideal a=()a){displaystyle {mathfrak}=(a)} Es Carmichael exactamente cuando a es un número de Carmichael en el sentido habitual.

Cuando K es más grande que los racionales es fácil escribir los ideales de Carmichael en OK{fnMicrosoft Sans Serif}: para cualquier número primo p que se divide completamente en K, el ideal principal pOK{displaystyle p{sfnMitcal {fnK} es un Carmichael ideal. Desde infinitamente muchos números primos se dividen completamente en cualquier campo número, hay infinitamente muchos ideales de Carmichael en OK{fnMicrosoft Sans Serif}. Por ejemplo, si p es cualquier número primo que es 1 mod 4, el ideal (p) en los enteros gaussianos Z[iEs un Carmichael ideal.

Tanto los números primos como los de Carmichael satisfacen la siguiente igualdad:

gcd().. x=1n− − 1xn− − 1,n)=1.{displaystyle gcd left(sum _{x=1}^{n-1}x^{n-1},nright)=1.}

Número de Lucas-Carmichael

Un entero compuesto positivo n{displaystyle n} es un número Lucas-Carmichael si y sólo si n{displaystyle n} es libre de cuadrados, y para todos los divisores primos p{displaystyle p} de n{displaystyle n}, es cierto que p+1▪ ▪ n+1{displaystyle p+1mid n+1}. Los primeros números de Lucas-Carmichael son:

399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31535, 46079, 51359, 60059, 63503, 67199, 73535, 76751, 80189, 81719, 88559, 90287,... (secuencia) A006972 en el OEIS)

Cuasi-número de Carmichael

Los cuasi-números de Carmichael son números compuestos sin cuadrados n con la propiedad de que para cada factor primo p de n, p + b divide n + b positivamente, siendo b cualquier número entero además de 0. Si b = −1, estos son números de Carmichael, y si b = 1, estos son números de Lucas-Carmichael. Los primeros números Cuasi-Carmichael son:

35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527, 561, 589, 598, 713, 715, 899, 935, 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 154729 A257750 en el OEIS)

Número de Knödel

An n-Knödel number para un entero positivo dado n es un número compuesto m con la propiedad que cada uno i.m coprime m satisfizo im− − n↑ ↑ 1()modm){displaystyle i^{m-n}equiv 1{pmod {m}}. El n = 1 caso son los números de Carmichael.

Números de Carmichael de orden superior

Los números de Carmichael se pueden generalizar usando conceptos de álgebra abstracta.

La definición anterior establece que un entero compuesto n es Carmichael precisamente cuando la nésima función de aumento de poder pn del anillo Zn de enteros módulo n a sí mismo es la función identidad. La identidad es el único endomorfismo Zn-álgebra en Zn para que podamos reformular la definición pidiendo que pn sea un endomorfismo algebraico de Z n. Como arriba, pn satisface la misma propiedad siempre que n sea primo.

La nésima función de aumento de potencia pn también se define en cualquier Z n-álgebra A. Un teorema establece que n es primo si y solo si todas esas funciones pn son endomorfismos de álgebra.

Entre estas dos condiciones se encuentra la definición de número de Carmichael de orden m para cualquier número entero positivo m como cualquier número compuesto n tal que pn es un endomorfismo en cada Zn-álgebra que se puede generar como módulo Zn por elementos m. Los números de Carmichael de orden 1 son simplemente los números de Carmichael ordinarios.

Un número Carmichael de orden 2

Según Howe, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 es un número de Carmichael de orden 2. Este producto es igual a 443.372.888.629.441.

Propiedades

El criterio de Korselt se puede generalizar a números de Carmichael de orden superior, como lo muestra Howe.

Un argumento heurístico, dado en el mismo documento, parece sugerir que hay infinitos números de Carmichael de orden m, para cualquier m. Sin embargo, no se conoce ni un solo número de Carmichael de orden 3 o superior.

Contenido relacionado

Anillo noetheriano

División (matemáticas)

Multiplicador de Lagrange

El método puede resumirse como sigue: Para encontrar el máximo o mínimo de una función f} sujetos a la limitación de la igualdad g()x)=0,{displaystyle...
Más resultados...
Te puede interesar
Tamaño del texto:
undoredo
format_boldformat_italicformat_underlinedstrikethrough_ssuperscriptsubscriptlink
save
cancelcheck_circle