Os números primos são um dos fenômenos matemáticos mais interessantes que atraem a atenção de cientistas e cidadãos comuns há mais de dois milênios. Apesar de vivermos agora na era dos computadores e dos programas de informação mais modernos, muitos mistérios dos números primos ainda não foram resolvidos, existem até aqueles que os cientistas não sabem como abordar.

Os números primos são, como se sabe no curso da aritmética elementar, aqueles que são divisíveis sem resto apenas por um e por ele mesmo. A propósito, se um número natural é divisível, além dos listados acima, por outro número, ele é chamado de composto. Um dos teoremas mais famosos afirma que qualquer número composto pode ser representado como o único produto possível de números primos.

Alguns fatos interessantes. Primeiro, a unidade é única no sentido de que, de fato, não pertence a números primos ou compostos. Ao mesmo tempo, na comunidade científica ainda é costume atribuí-lo ao primeiro grupo, pois formalmente atende plenamente aos seus requisitos.

Em segundo lugar, o único número par que se infiltrou no grupo dos “números primos” é, obviamente, dois. Qualquer outro número par simplesmente não pode chegar aqui, pois por definição, além de si mesmo e um, também é divisível por dois.

Os números primos, cuja lista, como mencionado acima, pode começar com um, são uma série infinita, tão infinita quanto a série dos números naturais. Com base no teorema fundamental da aritmética, pode-se concluir que os números primos nunca são interrompidos e nunca terminam, pois de outra forma a série dos números naturais seria inevitavelmente interrompida.

Os números primos não aparecem aleatoriamente na série natural, como pode parecer à primeira vista. Depois de analisá-los cuidadosamente, você pode notar imediatamente vários recursos, dos quais os mais curiosos estão associados aos chamados números "gêmeos". São chamados assim porque, de alguma forma incompreensível, acabaram um ao lado do outro, separados apenas por um delimitador par (cinco e sete, dezessete e dezenove).

Se você olhar atentamente para eles, notará que a soma desses números é sempre um múltiplo de três. Além disso, ao dividir por um triplo do companheiro esquerdo, o restante sempre permanece dois e o direito - um. Além disso, a própria distribuição desses números ao longo da série natural pode ser prevista se toda essa série for representada na forma de senoides oscilatórias, cujos pontos principais são formados quando os números são divididos por três e dois.

Os números primos não são apenas objeto de escrutínio minucioso por matemáticos de todo o mundo, mas há muito tempo são usados ​​com sucesso na compilação de várias séries de números, que é a base, inclusive para a cifragem. Ao mesmo tempo, deve-se reconhecer que um grande número de mistérios associados a esses maravilhosos elementos ainda está esperando para ser resolvido, muitas questões têm significado não apenas filosófico, mas também prático.

Definição 1. número primoé um número natural maior que 1 que só é divisível por ele mesmo e por 1.

Em outras palavras, um número é primo se tiver apenas dois divisores naturais distintos.

Definição 2. Qualquer número natural que tenha outros divisores além de si mesmo e um é chamado número composto.

Em outras palavras, os números naturais que não são primos são chamados de números compostos. A definição 1 implica que um número composto tem mais de dois divisores naturais. O número 1 não é primo nem composto. tem apenas um divisor 1 e, além disso, muitos teoremas sobre números primos não valem para a unidade.

Segue-se das Definições 1 e 2 que todo número inteiro positivo maior que 1 é um número primo ou composto.

Abaixo está um programa para exibição de números primos até 5000. Preencha as células, clique no botão "Criar" e aguarde alguns segundos.

Tabela de números primos

Declaração 1. Se um pé um número primo e uma qualquer número inteiro, então ou uma dividido por p, ou p e uma números relativamente primos.

Sério. Se um p número primo, então ele só é divisível por ele mesmo e 1 se uma não divisível por p, então o máximo divisor comum uma e pé igual a 1. Então p e uma números relativamente primos.

Declaração 2. Se o produto de vários números de números uma 1 , uma 2 , uma 3 , ... é divisível por um número primo p, então pelo menos um dos números uma 1 , uma 2 , uma 3 , ... é divisível por p.

Sério. Se nenhum dos números for divisível por p, então os números uma 1 , uma 2 , uma 3 , ... seriam números relativamente primos em relação a p. Mas do Corolário 3 () segue-se que o seu produto uma 1 , uma 2 , uma 3 , ... também é coprimo em relação a p, o que contraria a condição da afirmação. Portanto, pelo menos um dos números é divisível por p.

Teorema 1. Qualquer número composto pode sempre ser representado, e mais ainda de forma única, como o produto de um número finito de números primos.

Prova. Deixar k número composto, e seja uma 1 é um de seus divisores diferentes de 1 e de si mesmo. Se um uma 1 é composto, então tem além de 1 e uma 1 e outro divisor uma 2. Se um uma 2 é um número composto, então ele tem, além de 1 e uma 2 e outro divisor uma 3 . Argumentando desta forma e tendo em conta que os números uma 1 , uma 2 , uma 3 , ... diminuir e esta série contém um número finito de termos, chegaremos a algum número primo p 1 . Então k pode ser representado como

Suponha que haja duas expansões de um número k:

Porque k=p 1 p 2 p 3 ... é divisível por um número primo q 1 , então pelo menos um dos fatores, por exemplo p 1 é divisível por q 1 . Mas p 1 é primo e só é divisível por 1 e por ele mesmo. Consequentemente p 1 =q 1 (porque q 1 ≠1)

Então de (2) podemos excluir p 1 e q 1:

Assim, garantimos que qualquer número primo que entre na primeira expansão como fator uma ou mais vezes entre na segunda expansão pelo menos o mesmo número de vezes e vice-versa, qualquer número primo que entre na segunda expansão como fator um ou vários times também entra na primeira expansão pelo menos tantas vezes. Portanto, qualquer número primo entra como fator em ambas as expansões o mesmo número de vezes e, portanto, essas duas expansões são iguais.■

Decomposição de um número composto k pode ser escrito da seguinte forma

Onde p 1 , p 2 , ... números primos distintos, α, β, γ ... números inteiros positivos.

A decomposição (3) é chamada decomposição canônica números.

Números primos na série de números naturais ocorrem de forma desigual. Em algumas partes da série há mais deles, em outros - menos. Quanto mais avançamos na série numérica, mais raros são os números primos. A questão é: existe um maior número primo? O antigo matemático grego Euclides provou que existem infinitos números primos. Apresentamos esta prova a seguir.

Teorema 2. O número de números primos é infinito.

Prova. Suponha que haja um número finito de primos, e seja o maior primo p. Vamos considerar todos os números p. Pela suposição da afirmação, esses números devem ser compostos e devem ser divisíveis por pelo menos um dos números primos. Vamos escolher um número que é o produto de todos esses primos mais 1:

Número z mais p Porque 2p já mais p. p não é divisível por nenhum desses números primos, pois quando dividido por cada um deles, dá um resto de 1. Assim chegamos a uma contradição. Portanto, há um número infinito de números primos.

Este teorema é um caso especial de um teorema mais geral:

Teorema 3. Seja dada uma progressão aritmética

Então qualquer número primo em n, também deve ser incluído m, assim em n não pode incluir outros fatores primos que não estão incluídos em m e, além disso, esses fatores primos em n não aparecem mais vezes do que em m.

O contrário também é verdade. Se todo fator primo de um número n ocorre pelo menos o mesmo número de vezes m, então m dividido por n.

Declaração 3. Deixar uma 1 ,uma 2 ,uma 3 ,... vários primos que aparecem em m assim

Onde eu=0,1,...α , j=0,1,...,β , k=0,1,..., γ . notar que um eu aceita α +1 valores, β j aceita β +1 valores, γ k leva γ valores +1, ... .

• Tradução

As propriedades dos números primos foram estudadas pela primeira vez pelos matemáticos da Grécia antiga. Os matemáticos da escola pitagórica (500 - 300 aC) estavam principalmente interessados ​​nas propriedades místicas e numerológicas dos números primos. Eles foram os primeiros a ter ideias sobre números perfeitos e amigáveis.

Um número perfeito tem seus próprios divisores iguais a ele mesmo. Por exemplo, os divisores próprios do número 6 são: 1, 2 e 3. 1 + 2 + 3 = 6. Os divisores do número 28 são 1, 2, 4, 7 e 14. Além disso, 1 + 2 + 4 + 7 + 14 = 28.

Os números são chamados amigáveis ​​se a soma dos divisores próprios de um número for igual a outro, e vice-versa - por exemplo, 220 e 284. Podemos dizer que um número perfeito é amigável consigo mesmo.

Na época do aparecimento da obra de "Começos" de Euclides em 300 aC. Vários fatos importantes sobre os números primos já foram comprovados. No Livro IX dos Elementos, Euclides provou que há um número infinito de números primos. Aliás, este é um dos primeiros exemplos do uso da prova por contradição. Ele também prova o Teorema Básico da Aritmética - todo número inteiro pode ser representado de uma maneira única como um produto de números primos.

Ele também mostrou que se o número 2 n -1 for primo, então o número 2 n-1 * (2 n -1) será perfeito. Outro matemático, Euler, em 1747 foi capaz de mostrar que todos os números perfeitos pares podem ser escritos nesta forma. Até hoje não se sabe se existem números perfeitos ímpares.

No ano 200 a.C. O grego Eratóstenes criou um algoritmo para encontrar números primos chamado Peneira de Eratóstenes.

E então houve uma grande ruptura na história do estudo dos números primos associados à Idade Média.

As seguintes descobertas foram feitas já no início do século XVII pelo matemático Fermat. Ele provou a conjectura de Albert Girard de que qualquer número primo da forma 4n+1 pode ser escrito unicamente como uma soma de dois quadrados, e também formulou um teorema de que qualquer número pode ser representado como uma soma de quatro quadrados.

Ele desenvolveu um novo método de fatoração para números grandes e o demonstrou no número 2027651281 = 44021 × 46061. Ele também provou o Pequeno Teorema de Fermat: se p é um número primo, então a p = a módulo p será verdadeiro para qualquer inteiro a.

Esta afirmação prova metade do que era conhecido como a "hipótese chinesa" e data de 2000 anos antes: um inteiro n é primo se e somente se 2n-2 for divisível por n. A segunda parte da hipótese acabou sendo falsa - por exemplo, 2341 - 2 é divisível por 341, embora o número 341 seja composto: 341 = 31 × 11.

O Pequeno Teorema de Fermat foi a base para muitos outros resultados na teoria dos números e métodos para testar se os números são primos, muitos dos quais ainda estão em uso hoje.

Fermat correspondeu-se extensivamente com seus contemporâneos, especialmente com um monge chamado Marin Mersenne. Em uma de suas cartas, ele conjecturou que os números da forma 2 n + 1 sempre serão primos se n for uma potência de dois. Ele testou isso para n = 1, 2, 4, 8 e 16, e tinha certeza de que quando n não é uma potência de dois, o número não era necessariamente primo. Esses números são chamados de números de Fermat, e foi somente 100 anos depois que Euler mostrou que o próximo número, 232 + 1 = 4294967297, é divisível por 641 e, portanto, não é primo.

Números da forma 2 n - 1 também têm sido objeto de pesquisa, pois é fácil mostrar que se n é composto, então o próprio número também é composto. Esses números são chamados de números de Mersenne porque ele os estudou ativamente.

Mas nem todos os números da forma 2 n - 1, onde n é primo, são primos. Por exemplo, 2 11 - 1 = 2047 = 23 * 89. Isso foi descoberto pela primeira vez em 1536.

Por muitos anos, números desse tipo deram aos matemáticos os maiores primos conhecidos. Que o número M 19 foi provado por Cataldi em 1588, e por 200 anos foi o maior número primo conhecido, até Euler provar que M 31 também é primo. Esse recorde se manteve por mais cem anos, e então Lucas mostrou que M 127 é primo (e isso já é um número de 39 dígitos), e depois disso, as pesquisas continuaram com o advento dos computadores.

Em 1952, a primazia dos números M 521 , M 607 , M 1279 , M 2203 e M 2281 foi provada.

Em 2005, 42 primos de Mersenne foram encontrados. O maior deles, M 25964951 , consiste em 7816230 dígitos.

O trabalho de Euler teve um enorme impacto na teoria dos números, incluindo os números primos. Ele estendeu o Pequeno Teorema de Fermat e introduziu a função φ. Fatorizou o 5º número de Fermat 2 32 +1, encontrou 60 pares de números amigáveis ​​e formulou (mas não conseguiu provar) a lei quadrática da reciprocidade.

Ele foi o primeiro a introduzir os métodos de análise matemática e desenvolveu a teoria analítica dos números. Ele provou que não apenas a série harmônica ∑ (1/n), mas também uma série da forma

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Obtido pela soma de quantidades inversas a números primos, também diverge. A soma dos n termos da série harmônica cresce aproximadamente como log(n), enquanto a segunda série diverge mais lentamente, como log[log(n)]. Isso significa que, por exemplo, a soma dos recíprocos de todos os números primos encontrados até hoje dará apenas 4, embora a série ainda divirja.

À primeira vista, parece que os números primos são distribuídos entre os inteiros de forma bastante aleatória. Por exemplo, entre os 100 números imediatamente anteriores a 1.0000.000, existem 9 números primos, e entre os 100 números imediatamente após esse valor, existem apenas 2. Mas em segmentos grandes, os números primos são distribuídos de maneira bastante uniforme. Legendre e Gauss trataram de sua distribuição. Gauss disse uma vez a um amigo que em qualquer 15 minutos livres ele sempre conta o número de primos nos próximos 1000 números. No final de sua vida, ele havia contado todos os números primos até 3 milhões. Legendre e Gauss calcularam igualmente que para n grande a densidade de primos é 1/log(n). Legendre estimou o número de primos entre 1 e n como

π(n) = n/(log(n) - 1,08366)

E Gauss - como uma integral logarítmica

π(n) = / 1/log(t) dt

Com um intervalo de integração de 2 a n.

A afirmação sobre a densidade de primos 1/log(n) é conhecida como Teorema dos Números Primos. Eles tentaram provar isso ao longo do século 19, e Chebyshev e Riemann fizeram progressos. Eles a conectaram com a Hipótese de Riemann, uma conjectura até então não comprovada sobre a distribuição de zeros da função zeta de Riemann. A densidade dos primos foi provada simultaneamente por Hadamard e de la Vallée-Poussin em 1896.

Na teoria dos números primos, ainda existem muitas questões não resolvidas, algumas das quais com muitas centenas de anos:

• hipótese dos primos gêmeos - sobre um número infinito de pares de números primos que diferem um do outro por 2
• Conjectura de Goldbach: qualquer número par, a partir de 4, pode ser representado como a soma de dois números primos
• Existe um número infinito de números primos da forma n 2 + 1 ?
• é sempre possível encontrar um número primo entre n 2 e (n + 1) 2 ? (o fato de que há sempre um número primo entre n e 2n foi provado por Chebyshev)
• Existe um número infinito de primos de Fermat? existem primos de Fermat após o dia 4?
• existe uma progressão aritmética de primos consecutivos para qualquer comprimento dado? por exemplo, para comprimento 4: 251, 257, 263, 269. O comprimento máximo encontrado é 26 .
• Existe um número infinito de conjuntos de três primos consecutivos em uma progressão aritmética?
• n 2 - n + 41 é um número primo para 0 ≤ n ≤ 40. Existe um número infinito desses números primos? A mesma pergunta para a fórmula n 2 - 79 n + 1601. Esses números são primos para 0 ≤ n ≤ 79.
• Existe um número infinito de números primos da forma n# + 1? (n# é o resultado da multiplicação de todos os números primos menores que n)
• Existe um número infinito de números primos da forma n# -1 ?
• Existe um número infinito de números primos da forma n! +1?
• Existe um número infinito de números primos da forma n! - 1?
• se p é primo, 2 p -1 sempre não inclui entre os fatores dos primos ao quadrado
• A sequência de Fibonacci contém um número infinito de primos?

Os maiores números primos gêmeos são 2003663613 × 2 195000 ± 1. Eles consistem em 58711 dígitos e foram encontrados em 2007.

O maior número primo fatorial (da forma n! ± 1) é 147855! - 1. É composto por 142.891 dígitos e foi encontrado em 2002.

O maior número primo primoroso (um número da forma n# ± 1) é 1098133# + 1.

Lista de divisores. Por definição, o número né primo apenas se não for divisível por 2 e quaisquer inteiros diferentes de 1 e ele mesmo. A fórmula acima elimina etapas desnecessárias e economiza tempo: por exemplo, após verificar se um número é divisível por 3, não há necessidade de verificar se é divisível por 9.

• A função floor(x) arredonda x para o inteiro mais próximo menor ou igual a x.

Aprenda sobre aritmética modular. A operação "x mod y" (mod é a abreviação da palavra latina "modulo", que significa "módulo") significa "dividir x por y e encontrar o restante". Em outras palavras, na aritmética modular, ao atingir um determinado valor, que é chamado de módulo, os números "voltam" para zero. Por exemplo, um relógio mede o tempo no módulo 12: mostra 10, 11 e 12 horas e depois volta para 1.

• Muitas calculadoras têm uma tecla mod. O final desta seção mostra como calcular manualmente essa função para números grandes.

Os números são diferentes: naturais, naturais, racionais, inteiros e fracionários, positivos e negativos, complexos e primos, ímpares e pares, reais, etc. Neste artigo você pode aprender o que são números primos.

Que números são chamados de palavra inglesa "simples"?

Muitas vezes, os alunos não sabem responder a uma das perguntas aparentemente mais simples da matemática, sobre o que é um número primo. Eles costumam confundir números primos com números naturais (ou seja, os números que as pessoas usam ao contar objetos, enquanto em algumas fontes começam do zero e em outras - de um). Mas estes são dois conceitos completamente diferentes. Os números primos são números naturais, ou seja, números inteiros e positivos que são maiores que um e que possuem apenas 2 divisores naturais. Nesse caso, um desses divisores é um determinado número e o segundo é uma unidade. Por exemplo, três é um número primo porque não é divisível por qualquer número que não seja ele mesmo e um.

Números compostos

O oposto dos números primos são os números compostos. Eles também são naturais, também maiores que um, mas não têm dois, mas mais divisores. Assim, por exemplo, os números 4, 6, 8, 9, etc. são números naturais, compostos, mas não primos. Como você pode ver, estes são principalmente números pares, mas não todos. Mas o “dois” é um número par e o “primeiro número” em uma série de números primos.

Subsequência

Para construir uma série de números primos, é necessário fazer uma seleção de todos os números naturais, levando em consideração sua definição, ou seja, você precisa agir por contradição. É necessário considerar cada um dos números naturais positivos sobre se ele tem mais de dois divisores. Vamos tentar construir uma série (sequência) que consiste em números primos. A lista começa com dois, depois vem três, pois só é divisível por ele mesmo e um. Considere o número quatro. Tem divisores diferentes de quatro e um? Sim, esse número é 2. Portanto, quatro não é um número primo. Cinco também é primo (além de 1 e 5, não é divisível por nenhum outro número), mas seis é divisível. E, em geral, se você seguir todos os números pares, notará que, além de “dois”, nenhum deles é primo. Disso concluímos que os números pares, exceto dois, não são primos. Outra descoberta: todos os números que são divisíveis por três, exceto o próprio triplo, seja par ou ímpar, também não são primos (6, 9, 12, 15, 18, 21, 24, 27, etc.). O mesmo se aplica aos números que são divisíveis por cinco e sete. Todo o seu conjunto também não é simples. Vamos resumir. Assim, todos os números ímpares, exceto um e nove, pertencem a números simples de um dígito, e apenas “dois” de pares. As próprias dezenas (10, 20,... 40, etc.) não são primos. Números primos de dois dígitos, três dígitos, etc. podem ser definidos com base nos princípios acima: se eles não tiverem outros divisores além deles mesmos e um.

Teorias sobre as propriedades dos números primos

Existe uma ciência que estuda as propriedades dos inteiros, incluindo os primos. Este é um ramo da matemática, que é chamado de superior. Além das propriedades dos números inteiros, ela também lida com números algébricos, transcendentais, bem como funções de várias origens relacionadas à aritmética desses números. Nesses estudos, além de métodos elementares e algébricos, também são utilizados métodos analíticos e geométricos. Especificamente, o estudo dos números primos trata da “Teoria dos Números”.

Os números primos são os “blocos de construção” dos números naturais

Em aritmética existe um teorema chamado teorema principal. Segundo ele, qualquer número natural, exceto a unidade, pode ser representado como um produto, cujos fatores são números primos, e a ordem dos fatores é única, o que significa que o método de representação é único. É chamada de decomposição de um número natural em fatores primos. Existe outro nome para esse processo - fatoração de números. A partir disso, os números primos podem ser chamados de “material de construção”, “blocos” para a construção de números naturais.

Procure por números primos. Testes de Simplicidade

Muitos cientistas de diferentes épocas tentaram encontrar alguns princípios (sistemas) para encontrar uma lista de números primos. A ciência conhece sistemas chamados peneira de Atkin, peneira de Sundartam, peneira de Eratóstenes. No entanto, eles não fornecem resultados significativos e um teste simples é usado para encontrar números primos. Algoritmos também foram criados por matemáticos. Eles são chamados de testes de primalidade. Por exemplo, existe um teste desenvolvido por Rabin e Miller. É usado por criptógrafos. Há também um teste Kayala-Agrawala-Saskena. No entanto, apesar de sua precisão suficiente, é muito difícil de calcular, o que diminui seu valor prático.

O conjunto dos primos tem limite?

O fato de o conjunto dos primos ser infinito foi escrito no livro "Beginnings" do antigo cientista grego Euclides. Ele disse o seguinte: “Vamos imaginar por um momento que os números primos tenham um limite. Então vamos multiplicá-los entre si e adicionar um ao produto. O número obtido como resultado dessas operações simples não pode ser divisível por nenhuma das séries de números primos, pois o resto será sempre um. E isso significa que há algum outro número que ainda não está incluído na lista de números primos. Portanto, nossa suposição não é verdadeira e esse conjunto não pode ter limite. Além da prova de Euclides, há uma fórmula mais moderna dada pelo matemático suíço do século XVIII Leonhard Euler. Segundo ele, a soma, o recíproco da soma dos n primeiros números, cresce indefinidamente com o crescimento do número n. E aqui está a fórmula do teorema sobre a distribuição de números primos: (n) cresce como n / ln (n).

Qual é o maior número primo?

Mesmo assim, Leonard Euler foi capaz de encontrar o maior número primo de sua época. Isso é 2 31 - 1 = 2147483647. No entanto, em 2013, outro maior mais preciso na lista de números primos foi calculado - 2 57885161 - 1. É chamado de número de Mersenne. Ele contém cerca de 17 milhões de dígitos decimais. Como você pode ver, o número encontrado por um cientista do século XVIII é várias vezes menor que isso. Deveria ter sido assim, porque Euler fez esse cálculo manualmente, mas nosso contemporâneo provavelmente foi ajudado por um computador. Além disso, esse número foi obtido no Departamento de Matemática de um dos departamentos americanos. Números com o nome deste cientista passam pelo teste de primalidade de Luc-Lehmer. No entanto, a ciência não quer parar por aí. A Electronic Frontier Foundation, fundada em 1990 nos Estados Unidos da América (EFF), ofereceu uma recompensa monetária por encontrar grandes números primos. E se até 2013 o prêmio era dado aos cientistas que os encontrariam entre 1 e 10 milhões de números decimais, hoje esse número passou de 100 milhões a 1 bilhão. Os prêmios variam de 150 a 250 mil dólares americanos.

Nomes de números primos especiais

Esses números que foram encontrados graças a algoritmos criados por certos cientistas e passaram no teste de simplicidade são chamados de especiais. Aqui estão alguns deles:

1. Mersina.

4. Cullen.

6. Mills et al.

A simplicidade desses números, nomeados em homenagem aos cientistas acima, é estabelecida usando os seguintes testes:

1. Lucas-Lemer.

2. Pepina.

3. Riesel.

4. Billhart - Lehmer - Selfridge e outros.

A ciência moderna não para por aí, e provavelmente em um futuro próximo o mundo conhecerá os nomes daqueles que conseguiram ganhar um prêmio de 250.000 dólares ao encontrar o maior número primo.