Número Carmichael - Carmichael number

Na teoria dos números , um número de Carmichael é um número composto que satisfaz a relação de congruência aritmética modular : ${\ displaystyle n}$

${\ displaystyle b ^ {n-1} \ equiv 1 {\ pmod {n}}}$

para todos os inteiros que são relativamente primos a . Eles são nomeados em homenagem a Robert Carmichael . Os números de Carmichael são o subconjunto K ₁ dos números de Knödel . ${\ displaystyle b}$${\ displaystyle n}$

Equivalentemente, um número de Carmichael é um número composto para o qual ${\ displaystyle n}$

${\ displaystyle b ^ {n} \ equiv b {\ pmod {n}}}$

para todos os inteiros . ${\ displaystyle b}$

Visão geral

O pequeno teorema de Fermat afirma que se p é um número primo , então para qualquer inteiro b , o número b ^p  -  b é um múltiplo inteiro de p . Os números de Carmichael são números compostos que possuem esta propriedade. Os números de Carmichael também são chamados de pseudoprimas de Fermat ou pseudoprimas absolutas de Fermat . Um número de Carmichael passará no teste de primalidade de Fermat para cada base b relativamente primo do número, mesmo que ele não seja realmente primo. Isso torna os testes baseados no Pequeno Teorema de Fermat menos eficazes do que os testes de primários prováveis ​​fortes , como o teste de primalidade de Baillie – PSW e o teste de primalidade de Miller – Rabin .

No entanto, nenhum número de Carmichael é um pseudoprima de Euler-Jacobi ou um pseudoprime forte para cada base relativamente primo, então, em teoria, um teste de Euler ou um teste de primo provável forte poderia provar que um número de Carmichael é, de fato, composto.

Arnault fornece um número Carmichael de 397 dígitos que é um pseudoprime forte para todas as bases primos menores que 307: ${\ displaystyle N}$

${\ displaystyle N = p \ cdot (313 (p-1) +1) \ cdot (353 (p-1) +1)}$

Onde

${\ displaystyle p =}$29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883

é um primo de 131 dígitos. é o menor fator primo de , então este número de Carmichael também é um pseudoprime (não necessariamente forte) para todas as bases menores que . ${\ displaystyle p}$${\ displaystyle N}$${\ displaystyle p}$

Conforme os números se tornam maiores, os números de Carmichael se tornam cada vez mais raros. Por exemplo, existem 20.138.200 números de Carmichael entre 1 e 10 ²¹ (aproximadamente um em 50 trilhões (5 · 10 ¹³ ) de números).

Critério de Korselt

Uma definição alternativa e equivalente dos números de Carmichael é dada pelo critério de Korselt .

Teorema ( A. Korselt 1899): Um inteiro composto positivo é um número de Carmichael se, e somente se, for livre de quadrados , e para todos os divisores primos de , é verdade que .${\ displaystyle n}$${\ displaystyle n}$ ${\ displaystyle p}$${\ displaystyle n}$${\ displaystyle p-1 \ mid n-1}$

Segue-se deste teorema que todos os números de Carmichael são ímpares , uma vez que qualquer número composto par que é livre de quadrados (e, portanto, tem apenas um fator primo de dois) terá pelo menos um fator primo ímpar e, portanto, resulta em uma divisão par estranho, uma contradição. (A estranheza dos números de Carmichael também decorre do fato de que é uma testemunha de Fermat para qualquer número composto par.) Do critério também segue que os números de Carmichael são cíclicos . Além disso, segue-se que não há números de Carmichael com exatamente dois divisores primos. ${\ displaystyle p-1 \ mid n-1}$${\ displaystyle -1}$

Descoberta

Korselt foi o primeiro a observar as propriedades básicas dos números de Carmichael, mas não deu nenhum exemplo. Em 1910, Carmichael encontrou o primeiro e menor número, 561, o que explica o nome "número de Carmichael".

Que 561 é um número de Carmichael pode ser visto com o critério de Korselt. Na verdade, é livre de quadrados e , e . ${\ displaystyle 561 = 3 \ cdot 11 \ cdot 17}$${\ displaystyle 2 \ mid 560}$${\ displaystyle 10 \ mid 560}$${\ displaystyle 16 \ mid 560}$

Os próximos seis números de Carmichael são (sequência A002997 no OEIS ):

${\ displaystyle 1105 = 5 \ cdot 13 \ cdot 17 \ qquad (4 \ mid 1104; \ quad 12 \ mid 1104; \ quad 16 \ mid 1104)}$

${\ displaystyle 1729 = 7 \ cdot 13 \ cdot 19 \ qquad (6 \ mid 1728; \ quad 12 \ mid 1728; \ quad 18 \ mid 1728)}$

${\ displaystyle 2465 = 5 \ cdot 17 \ cdot 29 \ qquad (4 \ mid 2464; \ quad 16 \ mid 2464; \ quad 28 \ mid 2464)}$

${\ displaystyle 2821 = 7 \ cdot 13 \ cdot 31 \ qquad (6 \ mid 2820; \ quad 12 \ mid 2820; \ quad 30 \ mid 2820)}$

${\ displaystyle 6601 = 7 \ cdot 23 \ cdot 41 \ qquad (6 \ mid 6600; \ quad 22 \ mid 6600; \ quad 40 \ mid 6600)}$

${\ displaystyle 8911 = 7 \ cdot 19 \ cdot 67 \ qquad (6 \ mid 8910; \ quad 18 \ mid 8910; \ quad 66 \ mid 8910).}$

Esses primeiros sete números de Carmichael, de 561 a 8911, foram todos encontrados pelo matemático tcheco Václav Šimerka  [ de ; cs ] em 1885 (precedendo não apenas Carmichael, mas também Korselt, embora Šimerka não tenha encontrado nada como o critério de Korselt). Seu trabalho, no entanto, passou despercebido.

J. Chernick provou um teorema em 1939 que pode ser usado para construir um subconjunto de números de Carmichael. O número é um número de Carmichael se seus três fatores forem todos primos. Se esta fórmula produz uma quantidade infinita de números de Carmichael é uma questão em aberto (embora esteja implícito na conjectura de Dickson ). ${\ displaystyle (6k + 1) (12k + 1) (18k + 1)}$

Paul Erdős argumentou heuristicamente que deveria haver infinitos números de Carmichael. Em 1994, WR (Red) Alford , Andrew Granville e Carl Pomerance usaram um limite na constante de Olson para mostrar que realmente existem infinitos números de Carmichael. Especificamente, eles mostraram que, para tamanhos suficientemente grandes , existem pelo menos números de Carmichael entre 1 e . ${\ displaystyle n}$${\ displaystyle n ^ {2/7}}$${\ displaystyle n}$

Thomas Wright provou que se e são relativamente primos, então existem infinitos números de Carmichael na progressão aritmética , onde . ${\ displaystyle a}$${\ displaystyle m}$${\ displaystyle a + k \ cdot m}$${\ displaystyle k = 1,2, \ ldots}$

Löh e Niebuhr em 1992 encontraram alguns números de Carmichael muito grandes, incluindo um com 1.101.518 fatores e mais de 16 milhões de dígitos. Isso foi aprimorado para 10.333.229.505 fatores primos e 295.486.761.787 dígitos, portanto, o maior número de Carmichael conhecido é muito maior do que o maior número primo conhecido .

Propriedades

Factorizações

Os números de Carmichael têm pelo menos três fatores primos positivos. Os primeiros números de Carmichael com fatores primos são (sequência A006931 no OEIS ): ${\ displaystyle k = 3,4,5, \ ldots}$

k
3	${\ displaystyle 561 = 3 \ cdot 11 \ cdot 17 \,}$
4	${\ displaystyle 41041 = 7 \ cdot 11 \ cdot 13 \ cdot 41 \,}$
5	${\ displaystyle 825265 = 5 \ cdot 7 \ cdot 17 \ cdot 19 \ cdot 73 \,}$
6	${\ displaystyle 321197185 = 5 \ cdot 19 \ cdot 23 \ cdot 29 \ cdot 37 \ cdot 137 \,}$
7	${\ displaystyle 5394826801 = 7 \ cdot 13 \ cdot 17 \ cdot 23 \ cdot 31 \ cdot 67 \ cdot 73 \,}$
8	${\ displaystyle 232250619601 = 7 \ cdot 11 \ cdot 13 \ cdot 17 \ cdot 31 \ cdot 37 \ cdot 73 \ cdot 163 \,}$
9	${\ displaystyle 9746347772161 = 7 \ cdot 11 \ cdot 13 \ cdot 17 \ cdot 19 \ cdot 31 \ cdot 37 \ cdot 41 \ cdot 641 \,}$

Os primeiros números de Carmichael com 4 fatores primos são (sequência A074379 no OEIS ):

eu
1	${\ displaystyle 41041 = 7 \ cdot 11 \ cdot 13 \ cdot 41 \,}$
2	${\ displaystyle 62745 = 3 \ cdot 5 \ cdot 47 \ cdot 89 \,}$
3	${\ displaystyle 63973 = 7 \ cdot 13 \ cdot 19 \ cdot 37 \,}$
4	${\ displaystyle 75361 = 11 \ cdot 13 \ cdot 17 \ cdot 31 \,}$
5	${\ displaystyle 101101 = 7 \ cdot 11 \ cdot 13 \ cdot 101 \,}$
6	${\ displaystyle 126217 = 7 \ cdot 13 \ cdot 19 \ cdot 73 \,}$
7	${\ displaystyle 172081 = 7 \ cdot 13 \ cdot 31 \ cdot 61 \,}$
8	${\ displaystyle 188461 = 7 \ cdot 13 \ cdot 19 \ cdot 109 \,}$
9	${\ displaystyle 278545 = 5 \ cdot 17 \ cdot 29 \ cdot 113 \,}$
10	${\ displaystyle 340561 = 13 \ cdot 17 \ cdot 23 \ cdot 67 \,}$

O segundo número de Carmichael (1105) pode ser expresso como a soma de dois quadrados de mais maneiras do que qualquer número menor. O terceiro número de Carmichael (1729) é o número de Hardy-Ramanujan : o menor número que pode ser expresso como a soma de dois cubos (de números positivos) de duas maneiras diferentes.

Distribuição

Deixe denotar o número de números de Carmichael menor ou igual a . A distribuição dos números de Carmichael por potências de 10 (sequência A055553 no OEIS ): ${\ displaystyle C (X)}$${\ displaystyle X}$

${\ displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
${\ 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

Em 1953, Knödel provou o limite superior :

${\ displaystyle C (X) <X \ exp \ left ({- k_ {1} \ left (\ log X \ log \ log X \ right) ^ {\ frac {1} {2}}} \ right)}$

por alguma constante . ${\ displaystyle k_ {1}}$

Em 1956, Erdős melhorou o limite para

${\ displaystyle C (X) <X \ exp \ left ({\ frac {-k_ {2} \ log X \ log \ log \ log X} {\ log \ log X}} \ right)}$

por alguma constante . Ele também apresentou um argumento heurístico sugerindo que esse limite superior deveria ser próximo à taxa de crescimento real de . ${\ displaystyle k_ {2}}$${\ displaystyle C (X)}$

Na outra direção, Alford , Granville e Pomerance provaram em 1994 que para X suficientemente grande ,

${\ displaystyle C (X)> X ^ {\ frac {2} {7}}.}$

Em 2005, esse limite foi aprimorado por Harman para

${\ displaystyle C (X)> X ^ {0,332}}$

que posteriormente melhorou o expoente para . ${\ displaystyle 0,7039 \ cdot 0,4736 = 0,333336704> 1/3}$

Em relação à distribuição assintótica dos números de Carmichael, houve várias conjecturas. Em 1956, Erdős conjecturou que havia números de Carmichael para X suficientemente grandes. Em 1981, Pomerance aguçou os argumentos heurísticos de Erdős para conjeturar que há pelo menos ${\ displaystyle X ^ {1-o (1)}}$

${\ displaystyle X \ cdot L (X) ^ {- 1 + o (1)}}$

Carmichael numera até , onde . ${\ displaystyle X}$${\ displaystyle L (x) = \ exp {\ left ({\ frac {\ log x \ log \ log \ log x} {\ log \ log x}} \ right)}}$

No entanto, dentro dos intervalos computacionais atuais (como as contagens dos números de Carmichael realizadas por Pinch até 10 ²¹ ), essas conjecturas ainda não são confirmadas pelos dados.

Generalizações

A noção de número Carmichael generaliza a um ideal Carmichael em qualquer campo de número K . Para qualquer ideal principal diferente de zero em , temos para todos em , onde está a norma do ideal . (Isso generaliza o pequeno teorema de Fermat, que para todos os inteiros m quando p é primo.) Chame um ideal diferente de zero em Carmichael se não for um ideal primo e para todos , onde está a norma do ideal . Quando K é , o ideal é principal , e se deixarmos a ser seu gerador positivo, então o ideal é Carmichael exatamente quando a é um número de Carmichael no sentido usual. ${\ displaystyle {\ mathfrak {p}}}$${\ displaystyle {\ mathcal {O}} _ {K}}$${\ displaystyle \ alpha ^ {{\ rm {N}} ({\ mathfrak {p}})} \ equiv \ alpha {\ bmod {\ mathfrak {p}}}}$${\ displaystyle \ alpha}$${\ displaystyle {\ mathcal {O}} _ {K}}$${\ displaystyle {\ rm {N}} ({\ mathfrak {p}})}$ ${\ displaystyle {\ mathfrak {p}}}$${\ displaystyle m ^ {p} \ equiv m {\ bmod {p}}}$${\ displaystyle {\ mathfrak {a}}}$${\ displaystyle {\ mathcal {O}} _ {K}}$${\ displaystyle \ alpha ^ {{\ rm {N}} ({\ mathfrak {a}})} \ equiv \ alpha {\ bmod {\ mathfrak {a}}}}$${\ displaystyle \ alpha \ in {\ mathcal {O}} _ {K}}$${\ displaystyle {\ rm {N}} ({\ mathfrak {a}})}$${\ displaystyle {\ mathfrak {a}}}$${\ displaystyle \ mathbf {Q}}$${\ displaystyle {\ mathfrak {a}}}$${\ displaystyle {\ mathfrak {a}} = (a)}$

Quando K é maior do que os racionais , é fácil escrever os ideais de Carmichael em : para qualquer número primo p que se divide completamente em K , o ideal principal é um ideal de Carmichael. Uma vez que infinitos números primos se dividem completamente em qualquer campo numérico, existem infinitos ideais de Carmichael em . Por exemplo, se p for qualquer número primo que seja 1 mod 4, o ideal ( p ) nos inteiros gaussianos Z [ i ] é um ideal de Carmichael. ${\ displaystyle {\ mathcal {O}} _ {K}}$${\ displaystyle p {\ mathcal {O}} _ {K}}$${\ displaystyle {\ mathcal {O}} _ {K}}$   

Os números primos e de Carmichael satisfazem a seguinte igualdade:

${\ displaystyle \ gcd \ left (\ sum _ {x = 1} ^ {n-1} x ^ {n-1}, n \ right) = 1.}$

Número Lucas-Carmichael

Um inteiro composto positivo é um número de Lucas-Carmichael se, e somente se, for livre de quadrados , e para todos os divisores primos de , é verdade isso . Os primeiros números Lucas-Carmichael são: ${\ displaystyle n}$${\ displaystyle n}$ ${\ displaystyle p}$${\ displaystyle n}$${\ displaystyle p + 1 \ mid n + 1}$

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, ... (sequência A006972 no OEIS )

Número quase-Carmichael

Os números quase-Carmichael são números compostos livres de quadrados n com a propriedade de que para cada fator primo p de n , p  +  b divide n  +  b positivamente com b sendo qualquer inteiro além de 0. Se b = −1, estes são números de Carmichael, e se b = 1, esses são números de Lucas-Carmichael. Os primeiros números Quasi-Carmichael são:

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, 1547, 1591, 1595, 1705, 1729, ... (sequência A257750 no OEIS )

Número Knödel

Um número n - Knödel para um dado inteiro positivo n é um número composto m com a propriedade que cada coprime i  <  m para m satisfaz . O caso n = 1 são números de Carmichael. ${\ displaystyle i ^ {mn} \ equiv 1 {\ pmod {m}}}$

Números de Carmichael de ordem superior

Os números de Carmichael podem ser generalizados usando conceitos de álgebra abstrata .

A definição acima afirma que um inteiro composto n é Carmichael precisamente quando a n -ésima função de aumento de potência p _n do anel Z _n do módulo n de inteiros para si mesmo é a função de identidade. A identidade é o único Z _n - endomorfismo de álgebra em Z _n, então podemos reafirmar a definição pedindo que p _n seja um endomorfismo de álgebra de Z _n . Como acima, p _n satisfaz a mesma propriedade sempre que n for primo.

O n função th-poder elevar p _n também é definido em qualquer Z _n -álgebra Uma . Um teorema afirma que n é primo se e somente se todas essas funções p _n são endomorfismos de álgebra.

Entre essas duas condições está a definição do número de Carmichael de ordem m para qualquer inteiro positivo m como qualquer número composto n tal que p _n é um endomorfismo em cada Z _n -álgebra que pode ser gerado como Z _n - módulo por m elementos . Os números de Carmichael de ordem 1 são apenas os números de Carmichael comuns.

Um número Carmichael do pedido 2

De acordo com Howe, 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 é um número de ordem 2 de Carmichael. Este produto é igual a 443.372.888.629.441.

Propriedades

O critério de Korselt pode ser generalizado para números de Carmichael de ordem superior, como mostrado por Howe.

Um argumento heurístico, dado no mesmo artigo, parece sugerir que existem infinitos números de Carmichael de ordem m , para qualquer m . No entanto, nem um único número de Carmichael de ordem 3 ou superior é conhecido.

Notas

Referências

• Carmichael, RD (1910). "Nota sobre uma nova função da teoria dos números" . Boletim da American Mathematical Society . 16 (5): 232–238. doi : 10.1090 / s0002-9904-1910-01892-9 .
• Carmichael, RD (1912). "Em números compostos P que satisfaçam a congruência de Fermat ". American Mathematical Monthly . 19 (2): 22–27. doi : 10.2307 / 2972687 . JSTOR 2972687 .${\ displaystyle a ^ {P-1} \ equiv 1 {\ bmod {P}}}$ 
• Chernick, J. (1939). "Sobre o teorema simples de Fermat" (PDF) . Touro. Amer. Matemática. Soc . 45 (4): 269–274. doi : 10.1090 / S0002-9904-1939-06953-X .
• Korselt, AR (1899). "Problème chinois". L'Intermédiaire des Mathématiciens . 6 : 142–143.
• Löh, G .; Niebuhr, W. (1996). "Um novo algoritmo para construir grandes números de Carmichael" (PDF) . Matemática. Comp . 65 (214): 823–836. Bibcode : 1996MaCom..65..823L . doi : 10.1090 / S0025-5718-96-00692-8 .
• Ribenboim, P. (1989). O livro de registros de números primos . Springer. ISBN 978-0-387-97042-4.
• Šimerka, V. (1885). "Zbytky z arithmetické posloupnosti (Sobre os restos de uma progressão aritmética)" . Časopis Pro Pěstování Matematiky a Fysiky . 14 (5): 221–225. doi : 10.21136 / CPMF.1885.122245 .

links externos

• "Número de Carmichael" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Enciclopédia de Matemática
• Tabela de números de Carmichael
• Tabelas de números de Carmichael com muitos fatores primos
• Tabelas de números de Carmichael abaixo ${\ displaystyle 10 ^ {18}}$
• "The Dullness of 1729" . MathPages.com .
• Weisstein, Eric W. "Carmichael Number" . MathWorld .
• Aritmética Modular das Respostas Finais