Mersenne prime - Mersenne prime

Um primo de Mersenne é um número primo que é um a menos que uma potência de dois . Ou seja, é um número primo da forma M _n = 2 ⁿ − 1 para algum inteiro n . Eles são nomeados após Marin Mersenne , um frade mínimo francês , que os estudou no início do século XVII. Se n é um número composto , então 2 ⁿ − 1 também o é . Portanto, uma definição equivalente dos primos de Mersenne é que eles são os números primos da forma M _p = 2 ^p − 1para algum primo p .

Os expoentes n que dão primos de Mersenne são 2, 3, 5, 7, 13, 17, 19, 31, ... (sequência A000043 no OEIS ) e os primos de Mersenne resultantes são 3 , 7 , 31 , 127 , 8191, 131071, 524287, 2147483647 , ... (sequência A000668 no OEIS ).

Números da forma M _n = 2 ⁿ − 1 sem o requisito de primalidade podem ser chamados de números de Mersenne . Às vezes, no entanto, os números de Mersenne são definidos para ter o requisito adicional de que n seja primo. O menor número composto de Mersenne com expoente primo n é 2 ¹¹ − 1 = 2047 = 23 × 89 .

Os primos de Mersenne foram estudados na antiguidade por causa de sua estreita conexão com os números perfeitos : o teorema de Euclides-Euler afirma uma correspondência biunívoca entre os números perfeitos pares e os primos de Mersenne. Muitos dos maiores primos conhecidos são primos de Mersenne porque os números de Mersenne são mais fáceis de verificar quanto à primalidade.

Em outubro de 2020, 51 primos de Mersenne são conhecidos. O maior número primo conhecido , 2 ^82.589.933 − 1 , é um primo de Mersenne. Desde 1997, todos os primos de Mersenne recém-descobertos foram descobertos pelo Great Internet Mersenne Prime Search , um projeto de computação distribuída . Em dezembro de 2020, um marco importante no projeto foi alcançado depois que todos os expoentes abaixo de 100 milhões foram verificados pelo menos uma vez.

Sobre os primos de Mersenne

Muitas questões fundamentais sobre os primos de Mersenne permanecem sem solução. Nem se sabe se o conjunto dos primos de Mersenne é finito ou infinito. A conjectura de Lenstra-Pomerance-Wagstaff afirma que existem infinitos primos de Mersenne e prevê sua ordem de crescimento . Também não se sabe se infinitos números de Mersenne com expoentes primos são compostos , embora isso decorra de conjecturas amplamente aceitas sobre números primos, por exemplo, a infinidade de primos de Sophie Germain congruentes a 3 ( mod 4 ). Para esses primos p , 2 p + 1 (que também é primo) dividirá M _p , por exemplo, 23 | M ₁₁ , 47 | M ₂₃ , 167 | M ₈₃ , 263 | M ₁₃₁ , 359 | M ₁₇₉ , 383 | M ₁₉₁ , 479 | M ₂₃₉ e 503 | M ₂₅₁ (sequência A002515 no OEIS ). Como para esses primos p , 2 p + 1 é congruente a 7 mod 8, então 2 é um resíduo quadrático mod 2 p + 1 , e a ordem multiplicativa de 2 mod 2 p + 1 deve dividir = p . Como p é primo, deve ser p ou 1. No entanto, não pode ser 1, pois e 1 não tem fatores primos , portanto, deve ser p . Portanto, 2 p + 1 divide e não pode ser primo. ${\displaystyle {\frac {(2p+1)-1}{2}}}$${\estilo de exibição \Phi _{1}(2)=1}$${\displaystyle \Phi _{p}(2)=2^{p}-1}$${\displaystyle 2^{p}-1=M_{p}}$

Os primeiros quatro primos de Mersenne são M ₂ = 3 , M ₃ = 7 , M ₅ = 31 e M ₇ = 127 e porque o primeiro primo de Mersenne começa em M ₂ , todos os primos de Mersenne são congruentes a 3 (mod 4). Além de M ₀ = 0 e M ₁ = 1 , todos os outros números de Mersenne também são congruentes a 3 (mod 4). Conseqüentemente, na fatoração primo de um número de Mersenne (  ≥  M ₂  ) deve haver pelo menos um fator primo congruente a 3 (mod 4).

Um teorema básico sobre os números de Mersenne afirma que se M _p é primo, então o expoente p também deve ser primo. Isso decorre da identidade

${\displaystyle {\begin{aligned}2^{ab}-1&=(2^{a}-1)\cdot \left(1+2^{a}+2^{2a}+2^{3a} +\cdots +2^{(b-1)a}\right)\\&=(2^{b}-1)\cdot \left(1+2^{b}+2^{2b}+2 ^{3b}+\cdots +2^{(a-1)b}\right).\end{aligned}}}$

Isso exclui a primalidade para números de Mersenne com um expoente composto, como M ₄ = 2 ⁴ − 1 = 15 = 3 × 5 = (2 ² − 1) × (1 + 2 ² ) .

Embora os exemplos acima possam sugerir que M _p é primo para todos os primos p , este não é o caso, e o menor contra-exemplo é o número de Mersenne

M ₁₁ = 2 ¹¹ − 1 = 2047 = 23 × 89 .

A evidência disponível sugere que um número de Mersenne selecionado aleatoriamente é muito mais provável de ser primo do que um número inteiro ímpar selecionado aleatoriamente de tamanho semelhante. No entanto, os valores primos de M _p parecem se tornar cada vez mais esparsos à medida que p aumenta. Por exemplo, oito dos primeiros 11 primos p dão origem a um primo de Mersenne M _p (os termos corretos na lista original de Mersenne), enquanto M _p é primo para apenas 43 dos primeiros dois milhões de números primos (até 32.452.843).

A falta de qualquer teste simples para determinar se um determinado número de Mersenne é primo torna a busca por primos de Mersenne uma tarefa difícil, uma vez que os números de Mersenne crescem muito rapidamente. O teste de primalidade Lucas–Lehmer (LLT) é um teste de primalidade eficiente que ajuda muito nessa tarefa, tornando muito mais fácil testar a primalidade dos números de Mersenne do que a maioria dos outros números do mesmo tamanho. A busca pelo maior primo conhecido tem um certo culto de seguidores . Conseqüentemente, uma grande quantidade de poder computacional foi gasto na busca de novos primos de Mersenne, muitos dos quais agora são feitos usando computação distribuída .

O módulo aritmético de um número de Mersenne é particularmente eficiente em um computador binário , tornando-os escolhas populares quando um módulo primo é desejado, como o gerador de números aleatórios Park–Miller . Encontrar um polinômio primitivo de ordem numérica de Mersenne requer conhecer a fatoração desse número, então os primos de Mersenne permitem encontrar polinômios primitivos de ordem muito alta. Tais trinômios primitivos são usados ​​em geradores de números pseudo-aleatórios com períodos muito grandes como o twister de Mersenne , registrador de deslocamento generalizado e geradores de Fibonacci Lagged .

Números perfeitos

Os primos de Mersenne M _p estão intimamente ligados aos números perfeitos . No século 4 aC, Euclides provou que se 2 ^p − 1 é primo, então 2 ^{p − 1} (2 ^p − 1 ) é um número perfeito. No século 18, Leonhard Euler provou que, inversamente, todos os números perfeitos pares têm esta forma. Isso é conhecido como o teorema de Euclides-Euler . Não se sabe se existem números perfeitos ímpares .

História

Os primos de Mersenne levam o nome do estudioso francês do século XVII Marin Mersenne , que compilou o que deveria ser uma lista de primos de Mersenne com expoentes de até 257. Os expoentes listados por Mersenne foram os seguintes:

2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.

Sua lista replicou os primos conhecidos de seu tempo com expoentes de até 19. Sua próxima entrada, 31, estava correta, mas a lista tornou-se amplamente incorreta, pois Mersenne incluiu erroneamente M ₆₇ e M ₂₅₇ (que são compostos) e omitiu M ₆₁ , M ₈₉ e M ₁₀₇ (que são primos). Mersenne deu pouca indicação de como ele chegou à sua lista.

Édouard Lucas provou em 1876 que M ₁₂₇ é de fato primo, como afirmou Mersenne. Este foi o maior número primo conhecido por 75 anos até 1951, quando Ferrier encontrou um primo maior, , usando uma máquina de calcular de mesa. M ₆₁ foi determinado como primo em 1883 por Ivan Mikheevich Pervushin , embora Mersenne afirmasse que era composto, e por esta razão às vezes é chamado de número de Pervushin. Este foi o segundo maior número primo conhecido, e assim permaneceu até 1911. Lucas havia mostrado outro erro na lista de Mersenne em 1876. Sem encontrar um fator, Lucas demonstrou que M ₆₇ é realmente composto. Nenhum fator foi encontrado até uma famosa palestra de Frank Nelson Cole em 1903. Sem dizer uma palavra, ele foi até um quadro-negro e elevou 2 à 67ª potência, então subtraiu um. Do outro lado do tabuleiro, ele multiplicou 193.707.721 × 761.838.257.287 e obteve o mesmo número, depois voltou ao seu lugar (para aplausos) sem falar. Mais tarde, ele disse que o resultado levou "três anos de domingos" para encontrar. Uma lista correta de todos os primos de Mersenne neste intervalo de números foi completada e rigorosamente verificada apenas cerca de três séculos depois que Mersenne publicou sua lista. ${\displaystyle (2^{148}+1)/17}$

Procurando por primos de Mersenne

Estão disponíveis algoritmos rápidos para encontrar primos de Mersenne e, em junho de 2019, os oito maiores números primos conhecidos são primos de Mersenne.

Os primeiros quatro primos de Mersenne M ₂ = 3 , M ₃ = 7 , M ₅ = 31 e M ₇ = 127 eram conhecidos na antiguidade. O quinto, M ₁₃ = 8191 , foi descoberto anonimamente antes de 1461; os dois seguintes ( M ₁₇ e M ₁₉ ) foram encontrados por Pietro Cataldi em 1588. Depois de quase dois séculos, Leonhard Euler verificou que M ₃₁ era primo em 1772. O próximo (em ordem histórica, não numérica) foi M ₁₂₇ , encontrado por Édouard Lucas em 1876, depois M ₆₁ por Ivan Mikheevich Pervushin em 1883. Mais dois ( M ₈₉ e M ₁₀₇ ) foram encontrados no início do século 20, por RE Powers em 1911 e 1914, respectivamente.

O método mais eficiente atualmente conhecido para testar a primalidade dos números de Mersenne é o teste de primalidade Lucas-Lehmer . Especificamente, pode-se mostrar que para primo p > 2 , M _p = 2 ^p − 1 é primo se e somente se M _p divide S _{p − 2} , onde S ₀ = 4 e S _k = ( S _{k − 1} ) ² − 2 para k > 0 .

Durante a era do cálculo manual, todos os expoentes até 257, inclusive, foram testados com o teste de Lucas-Lehmer e considerados compostos. Uma contribuição notável foi feita pelo professor de física aposentado de Yale Horace Scudder Uhler, que fez os cálculos para os expoentes 157, 167, 193, 199, 227 e 229. Infelizmente para esses pesquisadores, o intervalo que eles estavam testando contém a maior lacuna relativa conhecida entre Primos de Mersenne: o próximo expoente primo de Mersenne, 521, seria mais de quatro vezes maior que o recorde anterior de 127.

Gráfico do número de dígitos no maior primo de Mersenne conhecido por ano – era eletrônica. A escala vertical é logarítmica no número de dígitos, sendo assim uma função no valor do primo.${\displaystyle \log(\log(y))}$

A busca por primos de Mersenne foi revolucionada pela introdução do computador digital eletrônico. Alan Turing procurou por eles no Manchester Mark 1 em 1949, mas a primeira identificação bem sucedida de um primo de Mersenne, M ₅₂₁ , por este meio foi alcançada às 22:00 em 30 de janeiro de 1952, usando o US National Bureau of Standards Western Computador Automático (SWAC) no Instituto de Análise Numérica da Universidade da Califórnia, Los Angeles , sob a direção de DH Lehmer , com um programa de busca de computador escrito e dirigido pelo Prof. RM Robinson . Foi o primeiro primo de Mersenne a ser identificado em trinta e oito anos; o próximo, M ₆₀₇ , foi encontrado pelo computador pouco menos de duas horas depois. Mais três — M ₁₂₇₉ , M ₂₂₀₃ e M ₂₂₈₁  — foram encontrados pelo mesmo programa nos meses seguintes. M _4.423 foi o primeiro primo titânico descoberto , M _44.497 foi o primeiro primo gigante descoberto e M _6.972.593 foi o primeiro megaprime a ser descoberto, sendo um primo com pelo menos 1.000.000 dígitos. O número de dígitos na representação decimal de M _n é igual a ⌊ n × log ₁₀ 2⌋ + 1 , onde ⌊ x ⌋ denota a função piso (ou equivalentemente ⌊log ₁₀ M _n ⌋ + 1 ).

Em setembro de 2008, matemáticos da UCLA que participaram do Great Internet Mersenne Prime Search (GIMPS) ganharam parte de um prêmio de US$ 100.000 da Electronic Frontier Foundation pela descoberta de um primo de Mersenne de quase 13 milhões de dígitos. O prêmio, finalmente confirmado em outubro de 2009, é para o primeiro prime conhecido com pelo menos 10 milhões de dígitos. O prime foi encontrado em um Dell OptiPlex 745 em 23 de agosto de 2008. Este foi o oitavo Mersenne prime descoberto na UCLA.

Em 12 de abril de 2009, um log do servidor GIMPS informou que um 47º primo de Mersenne possivelmente havia sido encontrado. A descoberta foi notada pela primeira vez em 4 de junho de 2009 e verificada uma semana depois. O primo é 2 ^42.643.801 − 1 . Embora seja cronologicamente o 47º primo de Mersenne a ser descoberto, é menor do que o maior conhecido na época, que foi o 45º a ser descoberto.

Em 25 de janeiro de 2013, Curtis Cooper , matemático da University of Central Missouri , descobriu um 48º primo de Mersenne, 2 ^57.885.161 − 1 (um número com 17.425.170 dígitos), como resultado de uma busca executada por uma rede de servidores GIMPS.

Em 19 de janeiro de 2016, Cooper publicou sua descoberta de um 49º primo de Mersenne, 2 ^74.207.281 − 1 (um número com 22.338.618 dígitos), como resultado de uma pesquisa executada por uma rede de servidores GIMPS. Este foi o quarto primo de Mersenne descoberto por Cooper e sua equipe nos últimos dez anos.

Em 2 de setembro de 2016, o Great Internet Mersenne Prime Search terminou de verificar todos os testes abaixo de M _37.156.667 , confirmando oficialmente sua posição como o 45º Mersenne prime.

Em 3 de janeiro de 2018, foi anunciado que Jonathan Pace, um engenheiro elétrico de 51 anos que mora em Germantown, Tennessee , havia encontrado um 50º primo de Mersenne, 2 ^77.232.917 - 1 (um número com 23.249.425 dígitos), como resultado de uma pesquisa executada por uma rede de servidores GIMPS. A descoberta foi feita por um computador nos escritórios de uma igreja na mesma cidade.

Em 21 de dezembro de 2018, foi anunciado que o The Great Internet Mersenne Prime Search (GIMPS) descobriu o maior número primo conhecido, 2 ^82.589.933 − 1 , com 24.862.048 dígitos. Um computador oferecido por Patrick Laroche, de Ocala, Flórida, fez a descoberta em 7 de dezembro de 2018.

No final de 2020, o GIMPS começou a usar uma nova técnica para descartar possíveis primos de Mersenne chamado teste Probable prime (PRP), baseado no desenvolvimento de Robert Gerbicz em 2017 e uma maneira simples de verificar testes desenvolvidos por Krzysztof Pietrzak em 2018. Devido a a baixa taxa de erro e a facilidade de prova, isso reduziu quase pela metade o tempo de computação para descartar possíveis primos no teste de Lucas-Lehmer (já que dois usuários não precisariam mais realizar o mesmo teste para confirmar o resultado do outro), embora os expoentes passando no teste O teste de PRP ainda requer um para confirmar sua primalidade.

Teoremas sobre os números de Mersenne

1. Se a e p são números naturais tais que a ^p − 1 é primo, então a = 2 ou p = 1 .
   • Prova : a ≡ 1 ( mod a − 1) . Então a ^p ≡ 1 (mod a − 1) , então a ^p − 1 ≡ 0 (mod a − 1) . Assim a − 1 | uma ^p - 1 . No entanto, a ^p − 1 é primo, então a − 1 = a ^p − 1 ou a − 1 = ±1 . No primeiro caso, a = a ^p , portanto a = 0, 1 (o que é uma contradição, pois nem −1 nem 0 são primos) ou p = 1. No último caso, a = 2 ou a = 0 . Se a = 0 , no entanto, 0 ^p − 1 = 0 − 1 = −1 que não é primo. Portanto, a = 2 .
2. Se 2 ^p − 1 é primo, então p é primo.
   • Prova : Suponha que p é composto, portanto pode ser escrito p = ab com a e b > 1 . Então 2 ^p − 1 = 2 ^ab − 1 = (2 ^a ) ^b − 1 = (2 ^a − 1) ( (2 ^a ) ^{b −1} + (2 ^a ) ^{b −2} + … + 2 ^a + 1 ) então 2 ^p − 1 é composto. Por contrapositiva, se 2 ^p − 1 é primo então p é primo.
3. Se p é um primo ímpar, então todo primo q que divide 2 ^p − 1 deve ser 1 mais um múltiplo de 2 p . Isso vale mesmo quando 2 ^p − 1 é primo.
   • Por exemplo, 2 ⁵ − 1 = 31 é primo e 31 = 1 + 3 × (2 × 5) . Um exemplo composto é 2 ¹¹ − 1 = 23 × 89 , onde 23 = 1 + (2 × 11) e 89 = 1 + 4 × (2 × 11) .
   • Prova : Pelo pequeno teorema de Fermat , q é um fator de 2 ^{q −1} − 1 . Como q é um fator de 2 ^p − 1 , para todos os inteiros positivos c , q também é um fator de 2 ^pc − 1 . Como p é primo e q não é um fator de 2 ¹ − 1 , p também é o menor inteiro positivo x tal que q é um fator de 2 ^x − 1 . Como resultado, para todos os inteiros positivos x , q é um fator de 2 ^x − 1 se e somente se p é um fator de x . Portanto, como q é um fator de 2 ^{q −1} − 1 , p é um fator de q − 1 então q ≡ 1 (mod p ) . Além disso, como q é um fator de 2 ^p − 1 , que é ímpar, q é ímpar. Portanto, q ≡ 1 (mod 2 p ) .
   • Este fato leva a uma prova do teorema de Euclides , que afirma a infinitude dos primos, distinta da prova escrita por Euclides: para todo primo ímpar p , todos os primos que dividem 2 ^p − 1 são maiores que p ; assim, sempre há primos maiores do que qualquer primo em particular.
   • Segue-se deste fato que para todo primo p > 2 , existe pelo menos um primo da forma 2 kp +1 menor ou igual a M _p , para algum inteiro k .
4. Se p é um primo ímpar, então todo primo q que divide 2 ^p − 1 é congruente a ±1 (mod 8) .
   • Prova : 2 ^{p +1} ≡ 2 (mod q ) , então 2 ^1/2(p+1) é uma raiz quadrada de 2 mod q . Por reciprocidade quadrática , todo módulo primo em que o número 2 tem uma raiz quadrada é congruente a ±1 (mod 8) .
5. Um primo de Mersenne não pode ser um primo de Wieferich .
   • Prova : Mostramos que se p = 2 ^m − 1 é um primo de Mersenne, então a congruência 2 ^{p −1} ≡ 1 (mod p ² ) não é válida. Pelo pequeno teorema de Fermat, m | p - 1 . Portanto, pode-se escrever p − 1 = mλ . Se a congruência dada for satisfeita, então p ² | 2 ^mλ − 1 , portanto 0 ≡2 ^mλ - 1/2 ^m - 1 = 1 + 2 ^m + 2 ^{2 m} + ... + 2 ^{( λ − 1) m} ≡ − λ mod (2 ^m − 1) . Portanto, 2 ^m − 1 | λ , e portanto λ ≥ 2 ^m − 1 . Isso leva a p − 1 ≥ m (2 ^m − 1) , o que é impossível já que m ≥ 2 .
6. Se m e n são números naturais então m e n são primos se e somente se 2 ^m − 1 e 2 ⁿ − 1 são primos. Consequentemente, um número primo divide no máximo um número de Mersenne expoente primo. Ou seja, o conjunto de números de Mersenne perniciosos é coprimo aos pares.
7. Se p e 2 p + 1 são ambos primos (o que significa que p é um primo de Sophie Germain ), e p é congruente a 3 (mod 4) , então 2 p + 1 divide 2 ^p − 1 .
   • Exemplo : 11 e 23 são ambos primos, e 11 = 2 × 4 + 3 , então 23 divide 2 ¹¹ − 1 .
   • Prova : Let q seja 2 p + 1 . Pelo pequeno teorema de Fermat, 2 ^{2 p} ≡ 1 (mod q ) , então ou 2 ^p ≡ 1 (mod q ) ou 2 ^p ≡ −1 (mod q ) . Supondo que o último seja verdadeiro, então 2 ^{p +1} = (2^{1/2( p + 1)} ) ² ≡ −2 (mod q ) , então −2 seria um resíduo quadrático mod q . No entanto, como p é congruente a 3 (mod 4) , q é congruente a 7 (mod 8) e, portanto, 2 é um resíduo quadrático mod q . Além disso, como q é congruente a 3 (mod 4) , −1 é um nãoresíduoquadrático mod q , então −2 é o produto de um resíduo e um não resíduo e, portanto, é um não resíduo, o que é uma contradição. Portanto, a primeira congruência deve ser verdadeira e 2 p + 1 divide M _p .
8. Todos os divisores compostos de números de Mersenne com expoentes primos são pseudoprimos fortes para a base 2.
9. Com exceção de 1, um número de Mersenne não pode ser uma potência perfeita. Ou seja, e de acordo com o teorema de Mihăilescu , a equação 2 ^m - 1 = n ^k não tem soluções, onde m , n e k são números inteiros com m > 1 e k > 1 .

Lista de primos de Mersenne conhecidos

Em outubro de 2021, os 51 primos de Mersenne conhecidos são 2 ^p − 1 para o seguinte p :

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933. (sequência A000043 no OEIS )

Fatoração de números compostos de Mersenne

Como são números primos, os primos de Mersenne são divisíveis apenas por 1 e por eles mesmos. No entanto, nem todos os números de Mersenne são primos de Mersenne. Os números de Mersenne são casos de teste muito bons para o algoritmo de peneira de campo de número especial , muitas vezes o maior número fatorado com este algoritmo tem sido um número de Mersenne. Em junho de 2019, 2 ^1.193 − 1 é o recordista, tendo sido fatorado com uma variante da peneira de campo de número especial que permite a fatoração de vários números de uma só vez. Consulte os registros de fatoração de inteiros para obter links para mais informações. A peneira de campo de número especial pode fatorar números com mais de um fator grande. Se um número tiver apenas um fator muito grande, outros algoritmos podem fatorar números maiores primeiro encontrando fatores pequenos e depois executando um teste de primalidade no cofator. Em julho de 2021, a maior fatoração com fatores primos prováveis permitida é 2 ^10.443.557 − 1 = 37.289.325.994.807 × q , onde q é um primo provável de 3.143.811 dígitos. Foi descoberto por um participante do GIMPS com o apelido "fre_games". Em julho de 2021, o número de Mersenne M ₁₂₇₇ é o menor número de Mersenne composto sem fatores conhecidos; não tem fatores primos abaixo de 2 ⁶⁸ .

A tabela abaixo mostra as fatorações para os primeiros 20 números compostos de Mersenne (sequência A244453 no OEIS ).

O número de fatores para os primeiros 500 números de Mersenne pode ser encontrado em (sequência A046800 no OEIS ).

Números de Mersenne na natureza e em outros lugares

No problema matemático Torre de Hanói , resolver um quebra-cabeça com uma torre de n discos requer M _n etapas, supondo que nenhum erro seja cometido. O número de grãos de arroz em todo o tabuleiro de xadrez no problema do trigo e do tabuleiro de xadrez é M ₆₄ .

O asteróide com o número de planeta menor 8191 é nomeado 8191 Mersenne após Marin Mersenne, porque 8191 é um primo de Mersenne ( 3 Juno , 7 Iris , 31 Euphrosyne e 127 Johanna foram descobertos e nomeados durante o século XIX).

Em geometria , um triângulo retângulo inteiro que é primitivo e tem seu cateto par uma potência de 2 (  ≥ 4  ) gera um único triângulo retângulo tal que seu raio é sempre um número de Mersenne. Por exemplo, se o cateto par é 2 ^{n  + 1} então, por ser primitivo, ele restringe o cateto ímpar a 4 ⁿ  − 1 , a hipotenusa a ser 4 ⁿ  + 1 e seu raio a 2 ⁿ  − 1 .

Os números de Mersenne foram estudados em relação ao número total de caminhos de aceitação de máquinas de Turing de tempo polinomial não determinístico em 2018 e inclusões intrigantes foram descobertas.

Primos de Mersenne-Fermat

Um número de Mersenne-Fermat é definido como2 ^{p r} − 1/2 ^{p r − 1} − 1, com p primo, r número natural, e pode ser escrito como MF( p , r ) . Quando r = 1 , é um número de Mersenne. Quando p = 2 , é um número de Fermat . Os únicos primos de Mersenne-Fermat conhecidos com r > 1 são

MF(2, 2), MF(2, 3), MF(2, 4), MF(2, 5), MF(3, 2), MF(3, 3), MF(7, 2) e MF(59, 2) .

De fato, MF( p , r ) = Φ _{p ^r} (2) , onde Φ é o polinômio ciclotômico .

Generalizações

Os primos de Mersenne generalizados mais simples são números primos da forma f (2 ⁿ ) , onde f ( x ) é um polinômio de baixo grau com coeficientes inteiros pequenos . Um exemplo é o 2 ⁶⁴ - 2 ³² + 1 , neste caso, n = 32 , e f ( x ) = x ² - x + 1 ; outro exemplo é 2 ¹⁹² - 2 ⁶⁴ - 1 , neste caso, n = 64 , e f ( x ) = x ³ - x - 1 .

Também é natural tentar generalizar primos da forma 2 ⁿ − 1 para primos da forma b ⁿ − 1 (para b ≠ 2 e n > 1 ). No entanto (veja também os teoremas acima ), b ⁿ − 1 é sempre divisível por b − 1 , então a menos que o último seja uma unidade , o primeiro não é primo. Isso pode ser remediado permitindo que b seja um inteiro algébrico em vez de um inteiro:

Números complexos

No anel dos inteiros (em números reais ), se b − 1 é uma unidade , então b é 2 ou 0. Mas 2 ⁿ − 1 são os primos de Mersenne usuais, e a fórmula 0 ⁿ − 1 não leva a nada interessante (já que é sempre −1 para todo n > 0 ). Assim, podemos considerar um anel de "inteiros" em números complexos em vez de números reais , como inteiros de Gauss e inteiros de Eisenstein .

Primos Gaussianos de Mersenne

Se considerarmos o anel de inteiros gaussianos , obtemos o caso b = 1 + i e b = 1 − i , e podemos perguntar ( WLOG ) para qual n o número (1 + i ) ⁿ − 1 é um primo gaussiano que será então ser chamado de primo gaussiano de Mersenne .

(1 + i ) ⁿ − 1 é um primo gaussiano para o seguinte n :

2, 3, 5, 7, 11, 19, 29, 47, 73, 79, 113, 151, 157, 163, 167, 239, 241, 283, 353, 367, 379, 457, 997, 1367, 3041, 10141, 14699, 27529, 49207, 77291, 85237, 106693, 160423, 203789, 364289, 991961, 1203793, 1667321, 3704053, 4792057, ... (sequência A057429 no OEIS )

Como a sequência de expoentes para os primos de Mersenne usuais, essa sequência contém apenas números primos (racionais).

Como para todos os primos gaussianos, as normas (ou seja, quadrados de valores absolutos) desses números são primos racionais:

5, 13, 41, 113, 2113, 525313, 536903681, 140737471578113, ... (sequência A182300 no OEIS ).

Primos de Eisenstein Mersenne

Pode-se encontrar casos em que tal primo de Mersenne também é um primo de Eisenstein , sendo da forma b = 1 + ω e b = 1 − ω . Nesses casos, esses números são chamados de primos de Eisenstein Mersenne .

(1 + ω ) ⁿ − 1 é um primo de Eisenstein para o seguinte n :

2, 5, 7, 11, 17, 19, 79, 163, 193, 239, 317, 353, 659, 709, 1049, 1103, 1759, 2029, 5153, 7541, 9049, 10453, 23743, 255361, 534827, 534827, 2237561, ... (sequência A066408 no OEIS )

As normas (ou seja, quadrados de valores absolutos) desses primos de Eisenstein são primos racionais:

7, 271, 2269, 176419, 129159847, 1162320517, ... (sequência A066413 no OEIS )

Dividir um inteiro

Recuperar primos

A outra maneira de lidar com o fato de que b ⁿ − 1 é sempre divisível por b − 1 , é simplesmente tirar esse fator e perguntar quais valores de n fazem

${\displaystyle {\frac {b^{n}-1}{b-1}}}$

seja primo. (O inteiro b pode ser positivo ou negativo.) Se, por exemplo, tomarmos b = 10 , obtemos n valores de:

2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, ... (sequência A004023 no OEIS ),
correspondente a números primos, 11 1111111111111111111, 11111111111111111111111, ... (sequência A004022 no OEIS ).

Esses primos são chamados de primos repunit. Outro exemplo é quando tomamos b = −12 , obtemos n valores de:

2, 5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, ... (sequência A057178 no OEIS ),
correspondendo aos primos -11, 19141, 57154490053, ....

É uma conjectura que para todo inteiro b que não é uma potência perfeita , existem infinitos valores de n tais queb ⁿ - 1/b - 1é primo. (Quando b é uma potência perfeita, pode-se mostrar que existe no máximo um n valor tal queb ⁿ - 1/b - 1 é primo)

menos n tal queb ⁿ - 1/b - 1é primo são (começando com b = 2 , 0 se tal n não existir)

2, 3, 2, 3, 2, 5, 3, 0, 2, 17, 2, 5, 3, 3, 2, 3, 2, 19, 3, 3, 2, 5, 3, 0, 7, 3, 2, 5, 2, 7, 0, 3, 13, 313, 2, 13, 3, 349, 2, 3, 2, 5, 5, 19, 2, 127, 19, 0, 3, 4229, 2, 11, 3, 17, 7, 3, 2, 3, 2, 7, 3, 5, 0, 19, 2, 19, 5, 3, 2, 3, 2, ... (sequência A084740 no OEIS )

Para bases negativas b , elas são (começando com b = −2 , 0 se tal n não existir)

3, 2, 2, 5, 2, 3, 2, 3, 5, 5, 2, 3, 2, 3, 3, 7, 2, 17, 2, 3, 3, 11, 2, 3, 11, 0, 3, 7, 2, 109, 2, 5, 3, 11, 31, 5, 2, 3, 53, 17, 2, 5, 2, 103, 7, 5, 2, 7, 1153, 3, 7, 21943, 2, 3, 37, 53, 3, 17, 2, 7, 2, 3, 0, 19, 7, 3, 2, 11, 3, 5, 2, ... (sequência A084742 na OEIS ) (observe que esta sequência OEIS não permite n = 2 )

Base mínima b tal queb linha ^{( n )} − 1/b - 1 é primo são

2, 2, 2, 2, 5, 2, 2, 2, 10, 6, 2, 61, 14, 15, 5, 24, 19, 2, 46, 3, 11, 22, 41, 2, 12, 22, 3, 2, 12, 86, 2, 7, 13, 11, 5, 29, 56, 30, 44, 60, 304, 5, 74, 118, 33, 156, 46, 183, 72, 606, 602, 223, 115, 37, 52, 104, 41, 6, 338, 217, ... (sequência A066180 no OEIS )

Para bases negativas b , elas são

3, 2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (sequência A103795 no OEIS )

Outros primos de Mersenne generalizados

Outro número de Mersenne generalizado é

${\displaystyle {\frac {a^{n}-b^{n}}{ab}}}$

com a , b quaisquer inteiros primos , a > 1 e − a < b < a . (Como a ⁿ − b ⁿ é sempre divisível por a − b , a divisão é necessária para que haja alguma chance de encontrar números primos. Na verdade, esse número é o mesmo que o número de Lucas U _n ( a + b , ab ) , uma vez que um e b são as raízes da equação quadrática x ² - ( a + b ) x + ab = 0 , e este número é igual a 1 quando n = 1 ) podemos pedir que n faz com que este número primo. Pode-se mostrar que tais n devem ser primos próprios ou iguais a 4, e n pode ser 4 se e somente se a + b = 1 e a ² + b ² é primo. (Desde aa ⁴ − b ⁴/a - b= ( a + b )( a ² + b ² ) . Assim, neste caso o par ( a , b ) deve ser ( x + 1, − x ) e x ² + ( x + 1) ² deve ser primo. Isto é, x deve estar em OEIS :  A027861 .) É uma conjectura que para qualquer par ( a , b ) tal que para cada número natural r > 1 , a e b não são ambos perfeito r th poderes, e -4 ab não é uma quarta potência perfeita . existem infinitos valores de n tais quea ⁿ − b ⁿ/a - bé primo. (Quando a e b são ambos potências r- ésimas perfeitas para an r > 1 ou quando −4 ab é uma quarta potência perfeita, pode-se mostrar que existem no máximo dois valores de n com esta propriedade, pois se sim, entãoa ⁿ − b ⁿ/a - bpode ser fatorado algebricamente) No entanto, isso não foi provado para nenhum valor único de ( a , b ) .

^* Nota: se b < 0 e n for par, então os números n não estão incluídos na sequência OEIS correspondente.

Uma conjectura relacionada aos primos de Mersenne generalizados: (a conjectura prevê onde está o próximo primo de Mersenne generalizado, se a conjectura for verdadeira, então existem infinitos primos para todos esses pares ( a , b ) )

Para quaisquer inteiros a e b que satisfaçam as condições:

1. a > 1 , − a < b < a .
2. a e b são primos . (assim, b não pode ser 0)
3. Para todo número natural r > 1 , a e b não são potências r- ésimas perfeitas . (uma vez que a e b são potências r- ésimas perfeitas , pode-se mostrar que existem no máximo dois valores de n tais quea ⁿ − b ⁿ/a - bé primo, e esses n valores são o próprio r ou uma raiz de r ou 2)
4. −4 ab não é uma quarta potência perfeita (se for, então o número tem fatoração aurifeuilleana ).

tem números primos da forma

${\displaystyle R_{p}(a,b)={\frac {a^{p}-b^{p}}{ab}}}$

para primo p , os números primos serão distribuídos perto da linha de melhor ajuste

${\displaystyle Y=G\cdot \log _{a}(\log _{a}(R_{(a,b)}(n)))+C}$

Onde

${\displaystyle \lim _{n\rightarrow \infty }G={\frac {1}{e^{\gamma }}}=0,561459483566\ldots }$

e há cerca de

${\displaystyle (\log _{e}(N)+m\cdot \log _{e}(2)\cdot \log _{e}\left(\log _{e}(N))+{\ frac {1}{\sqrt {N}}}-\delta \right)\cdot {\frac {e^{\gamma }}{\log _{e}(a)}}}$

números primos desta forma menores que N .

• e é a base do logaritmo natural .
• γ é a constante de Euler-Mascheroni .
• log _a é o logaritmo na base a .
• R _{( um , b )} ( n ) é o n th número primo do formulárioa ^p − b ^p/a - bpara primo p .
• C é uma constante de ajuste de dados que varia com a e b .
• δ é uma constante de ajuste de dados que varia com a e b .
• m é o maior número natural tal que a e − b são ambos perfeitos 2 ^{m − 1ª} potências.

Também temos as três propriedades a seguir:

1. O número de números primos da forma a ^p − b ^p/a - b(com prime p ) menor ou igual a n é cerca de e ^γ log _a (log _a ( n )) .
2. O número esperado de números primos da forma a ^p − b ^p/a - bcom primo p entre n e an é cerca de e ^γ .
3. A probabilidade de que o número da forma a ^p − b ^p/a - bé primo (para primo p ) é sobree ^γ/p log _e ( a ).

Se esta conjectura for verdadeira, então para todos esses pares ( a , b ) , seja q o n- ésimo primo da formaa ^p − b ^p/a - b, o gráfico de log _a (log _a ( q )) versus n é quase linear. (Ver )

Quando a = b + 1 , é ( b + 1) ⁿ − b ⁿ , uma diferença de duas n- ésimas potências perfeitas consecutivas , e se a ⁿ − b ⁿ é primo, então a deve ser b + 1 , porque é divisível por a − b .

Menos n tal que ( b + 1) ⁿ − b ⁿ é primo são

2, 2, 2, 3, 2, 2, 7, 2, 2, 3, 2, 17, 3, 2, 2, 5, 3, 2, 5, 2, 2, 229, 2, 3, 3, 2, 3, 3, 2, 2, 5, 3, 2, 3, 2, 2, 3, 3, 2, 7, 2, 3, 37, 2, 3, 5, 58543, 2, 3, 2, 2, 3, 2, 2, 3, 2, 5, 3, 4663, 54517, 17, 3, 2, 5, 2, 3, 3, 2, 2, 47, 61, 19, ... (sequência A058013 no OEIS )

O mínimo b tal que ( b + 1) ^{prime( n )} − b ^{prime( n )} é primo são

1, 1, 1, 1, 5, 1, 1, 1, 5, 2, 1, 39, 6, 4, 12, 2, 2, 1, 6, 17, 46, 7, 5, 1, 25, 2, 41, 1, 12, 7, 1, 7, 327, 7, 8, 44, 26, 12, 75, 14, 51, 110, 4, 14, 49, 286, 15, 4, 39, 22, 109, 367, 22, 67, 27, 95, 80, 149, 2, 142, 3, 11, ... (sequência A222119 no OEIS )

Veja também

Referências

links externos

• "Número de Mersenne" , Enciclopédia de Matemática , EMS Press , 2001 [1994]
• Página inicial do GIMPS
• Relatório de marcos do GIMPS – a página de status fornece várias estatísticas sobre o progresso da pesquisa, normalmente atualizada a cada semana, incluindo o progresso para provar o pedido dos maiores primos de Mersenne conhecidos
• GIMPS, fatores conhecidos dos números de Mersenne
• M _q = (8 x ) ² − (3 qy ) ² Propriedade dos números de Mersenne com expoente primo que são compostos (PDF)
• M _q = x ² + d · y ² tese de matemática (PS)
• Sujeira, James. "31 e Mersenne Primes" . Numberphile . Brady Haran . Arquivado a partir do original em 31/05/2013 . Recuperado em 2013-04-06 .
• bibliografia principal de Mersenne com hiperlinks para publicações originais
• relatório sobre primos de Mersenne – detecção em detalhes (em alemão)
• Wiki do GIMPS
• Will Edgington's Mersenne Page - contém fatores para pequenos números de Mersenne
• Fatores conhecidos de números de Mersenne
• Dígitos decimais e nomes em inglês de primos de Mersenne
• Curiosidades principais: 2305843009213693951
• http://www.leyland.vispa.com/numth/factorization/cunningham/2-.txt Arquivado em 2014-11-05 na Wayback Machine
• http://www.leyland.vispa.com/numth/factorization/cunningham/2+.txt Arquivado em 2013-05-02 na Wayback Machine
• Sequência OEIS A250197 (Números n tais que a parte primitiva Aurifeuilliana esquerda de 2^n+1 é primo) – Fatoração de números de Mersenne M _n ( n até 1280)
• Fatoração de números de Mersenne completamente fatorados
• O projeto Cunningham, fatoração de b ⁿ ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12
• http://www.leyland.vispa.com/numth/factorization/cunningham/main.htm Arquivado em 2016-03-04 na Wayback Machine
• http://www.leyland.vispa.com/numth/factorization/anbn/main.htm Arquivado em 2016-02-02 na Wayback Machine

Links do MathWorld

• Weisstein, Eric W. "Número de Mersenne" . MathWorld .
• Weisstein, Eric W. "Mersenne prime" . MathWorld .