Número primo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Número primo, é um número p cujo conjunto dos divisores não inversíveis não é vazio, e todos os seus elementos são produtos de p por números inteiros inversíveis. De acordo com esta definição, 0, 1 e -1 não são números primos.


Um número inteiro primo é aquele que tem exatamente quatro divisores distintos, p \in \mathbb{Z}: \pm 1 e \pm p. Já um número natural primo tem exatamente dois divisores naturais distintos: o número um e ele mesmo[1] .


Uma das questões pesquisadas sobre os números primos é de como eles se distribuem nos naturais, com que frequência isso ocorre e qual a distância que existem entre eles. Por exemplo, existem vários pares de números primos que se diferem em duas unidades: (3, 5), (5, 7), (11, 13), (17, 19), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109). Pares de números primos com essa propriedades são denominados de primos gêmeos. Não se sabe ainda se existe infinitos pares de números primos gêmeos. [2] .


A propriedade de ser um primo é chamada "primalidade", e a palavra "primo" também é utilizada como substantivo ou adjetivo, se um número inteiro tem módulo maior que um e não é primo, diz-se que é composto (0, 1 e -1 também não são compostos). Como "dois" é o único número primo par, o termo "primo ímpar" refere-se a todo primo maior do que dois.


Existem infinitos números primos, como demonstrado por Euclides por volta de 300 a.C..[3] O conceito de número primo é muito importante na teoria dos números. Um dos resultados da teoria dos números é o Teorema Fundamental da Aritmética, que afirma que qualquer número natural diferente de 1 pode ser escrito de forma única (desconsiderando a ordem) como um produto de números primos (chamados fatores primos): este processo se chama decomposição em fatores primos (fatorização).


Existem 168 números primos positivos menores do que 1000. São eles: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,  131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257,  263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401,  409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563,  569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709,  719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877,  881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991 \text{ e } 997.


Exemplos de decomposições:

  • 4 = 2 \times 2
  • 6 = 2 \times 3
  • 8 = 2 \times 2 \times 2
  • 9 = 3 \times 3
  • 10 = 2 \times 5
  • 472.342.734.872.390.487 = 3 \times 7 \times 827 \times 978.491 \times 27.795.571


(A última parte desta sessão tem como mfonte o livro RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.)

Para todo primo p seja p# o produto de todos os números primos q inferiores ou iguais a p. De acordo com a termologia empregada por Dubner (1987), p# é chamado o primorial de p. Temos dois problemas em aberto sobre a noção de primorial:[4]

a) Existe uma infinidade de números primos p tais que p# + 1 seja primo?
b) Existe uma infinidade de números primos p tais que p# + 1 seja composto?

O que se sabe:

  • O maior número primo conhecido da forma p# + 1 é 392113# + 1, com 169966 algarismos, foi descoberto por D. Heuer et al. Em 2001.
  • A lista completa dos números primos p < 632700 tais que p# + 1 seja primo é a seguinte: P = 2, 3, 5, 7, 11, 31, 379, 1019, 1021, 2657, 3229, 4547, 4787, 11549, 13649, 18523, 23801, 24029, 42209, 145823, 366439 e 392113.
  • Caldwell e Gallot publicaram em 2002 a lista para p < 120000. O primo 145823# + 1 foi descoberto em 2000 por A.E. Anderson, D.E. Robinson et al. O primo 366439# + 1 foi descoberto em 2001 por D. Heuer et al.
  • 15877# – 1 é o maior primo encontrado da forma p# – 1; tem 6845 algarismos e estava incluído na lista de Caldwell e Gallot de 2002.
  • A lista dos números primos p < 650000 tais que p# – 1 é primo é a seguinte: 3, 5, 11, 13, 41, 89, 317, 337, 991, 1873, 2053, 2377, 4093, 4297, 4583, 6569, 13033 e 15877.
  • A lista para p < 120000 foi publicada em 2002 por Caldwell e Gallot, posteriormente nenhum outro primo p# – 1 foi descoberto.


Os átomos da aritmética[editar | editar código-fonte]

Os gregos foram os primeiros a perceber que qualquer número natural, exceto o 1, pode ser gerado pela multiplicação de números primos, os chamados blocos de construção". A primeira pessoa, até onde se sabe, que produziu tabelas de números primos foi Eratóstenes, no terceiro século a.C. Ele escrevia inicialmente uma lista com todos os números de 1 a 100. Em seguida escolhia o primeiro primo, 2, e eliminava da lista todos os seus múltiplos. Passava ao número seguinte que não fora eliminado e procedia também eliminando todos os seus múltiplos. Desta forma Eratóstenes produziu tabelas de primos, mais tarde este procedimento passou a se chamar de crivo de Eratóstenes. Observe a ilustração a seguir:

Assim obtemos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89. 91, 97, ... A partir desse procedimento podemos simplificar a descobertas de primos usando o lema : Se um número natural n > 1 não é divisível por nenhum primo p tal que p^2 ≤ n , então ele é primo.(demonstrado adiante). Este lema fornece um teste de primalidade, pois, para verificar se um dado número n é primo, basta verificar que não é divisível por nenhum p que não supere \sqrt{n}..


Durante o século XVII os matemáticos descobriram o que acreditavam ser um método infalível para determinar se um número N era primo: calcule 2 elevado a potência N e divida-o por N, se o resto for 2, então o número será primo. Em termos da calculadora-relógio de Gauss, esses matemáticos estavam tentando calcular 2^N em um relógio com N horas. Em 1819, o teste dos números primos foi eliminado, pois funciona para todos os números até 340, mas falha para 341 = 11 \times 31. Exceção descoberta com uma calculadora-relógio de Gauss contendo 341 horas utilizada para simplificar a análise de um número como 2^{341}.


Teoremas sobre números primos[editar | editar código-fonte]

Existem vários teoremas e estudos sobre os números primos, desde resultados tratados na matemática elementar, até conjecturas que não foram provadas.
Todos os teoremas desta sessão tem como fonte o livro de HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.


Teorema 1: (Teorema Fundamental da Aritmética)[5]

Todo número natural maior do que 1 ou é primo ou se escreve de modo único (a menos da ordem dos fatores) como um produto de números primos.

Demonstração:

Tomemos a segunda forma do Princípio de Indução. Seja n = 2, sabemos que ele é primo. Suponha o resultado válido para todo número natural menor que n e vamos provar que vale para n. Observe que que se n é primo, nada temos a provar. Sendo n composto, existem números naturais x e y tais que n = xy com 1 < x < n e 1 < y < n. Por hipótese de indução, existem primos a_1, a_2, a_3, ..., a_k e b_1, b_2, b_3 ..., b_w, tais que x = a_1a_2a_3...a_k e y = b_1b_2b_3...b_w, logo n = a_1a_2a_3...a_kb_1b_2b_3...b_w.

Provaremos agora a unicidade da escrita. Suponha que n = a_1a_2a_3...a_k = b_1b_2b_3...b_w, onde os a_i e b_j são números primos. Como a_1|b_1b_2b_3...b_w, temos que a_1 = b_w, para algum w (provaremos mais adiante), que por conveniência, podemos supor que seja b_1, logo teremos então que a_2a_3...a_k = b_2b_3...b_w (já que temos a_1 = b_1). De forma análoga, podemos afirmar que como a_2|b_2b_3b_4...b_w temos que a_2 = b_w, para algum w, que por conveniência, podemos supor que seja b_2, assim teremos a_3a_4...a_k = b_3b_4...b_w. Como a_3._a4_.a_5...a_k < n, a hipótese de indução acarreta em que k = w, e os elementos a_k e b_w são iguais.


Teorema 2:[6]

Dado um número natural n > 1, existem primos a_1, a_2, a_3, ..., a_k, e naturais u_1, u_2, u_3 ... u_w, univocamente determinados, tais que n = (a_1)^{u_1} . (a_2)^{u_2} . (a_3)^{u_3} .  ...  . (a_k)^{u_k}.

Demonstração:

Decorre do Teorema Fundamental da Aritmética, agrupando-se os primos repetidos e ordenando os primos em ordem crescente.


Teorema 3:[7]

Sejam a = (p_1)^{k_1}. (p_2)^{k_2} . (p_3)^{k_3} . … . (p_n)^{k_n} , b = (p_1)^{w_1} . (p_2)^{w_2} . (p_3)^{w_3} .… . (p_n)^{w_n} , r_i = min\{k_i, w_i\} e q_i = max \{k_i, w_i\}, com i = 1, 2, 3, 4 ..., n, tem-se que mdc(a, b) =  (p_1)^{r_1} . (p_2)^{r_2} .  (p_3)^{r_3} .… . (p_n)^{r_n} e mmc(a, b) = (p_1)^{q_1} . (p_2)^{q_2} . (p_3)^{q_3} .… . (p_n)^{q_n}.

Demonstração:

Temos que (p_1)^{r_1} . (p_2)^{r_2} . (p_3)^{r_3} .… . (p_n)^{r_n} é um divisor comum de a e b. Seja c um divisor comum de a e b, logo c = (p_1)^{y_1} . (p_2)^{y_2} . (p_3)^{y_3} .… . (p_n)^{y_n}, onde y_imin\{k_i, w_i\} e, portanto c|(p_1)^{r_1}.(p_2)^{r_2}.(p_3)^{r_3}.… .(p_n)^{r_n}. Do mesmo modo, prova-se o mmc.


Teorema 4:[8]

Existem infinitos números primos.

Demonstração:

Suponha que exista apenas um número finito de números primos p_1, p_2, p_3, ..., p_r. Considere o número natural n =  (p_1)(p_2)(p_3)....(p_r) + 1. O número n possui um fator primo p que, portanto, deve ser um dos p_1, p_2, p_3, ..., p_n, Mas isso implica que p divide 1, o que é absurdo.


Teorema 5: (Pequeno Teorema de Fermat)[9]

Dado um número primo p, tem-se que p divide o número a^{p} - a, para todo a \in N.

Demonstração:

Vamos provar pelo Princípio da Indução Infinita. O resultado vale para a = 1, já que p|0. Supondo valido para um natural a, iremos provar que é válido para o natural a + 1.

(a + 1)^{p}( a + 1) = a^{p}a+ \begin{pmatrix} p \\ 1 \end{pmatrix}a^{p-1} + ... + \begin{pmatrix} p \\ p - 1 \end{pmatrix}a. O segundo membro da igualdade é divisível por p (Lema 2), o resultado se segue.


Teorema 6: (Euclides-Euler)[10]

Um número natural n é um número perfeito par se, e somente se, n = 2^{p-1} (2^p 1), onde 2^p 1 é um primo de Mersenne.

Demonstração:

Suponha que n = 2^{p-1} (2^p 1), onde  2^p - 1 é um primo de Mersenne. Logo p > 1 e consequentemente, n é par. Como 2^p - 1 é ímpar, temos que mdc(2^{p - 1}, 2^p - 1) = 1. Pela Proposição 5, Corolário 2 e Lema 3, temos: S(n) = S(2^{p - 1}(2^p - 1)) = S(2^{p - 1}).S(2^p - 1) = \frac{2^p-1}{2-1} 2^p = 2n. Portanto, n é perfeito. (Denota-se por S(n) a soma de todos os divisores de n).

Reciprocamente, suponha que n é perfeito e par. Seja 2^{p-1} a maior potência de 2 que divide n. Logo, p > 1, e n = 2^{p-1}b, com b ímpar. Temos então que mdc(2^{p-1},b) = 1 e, pela Proposição 5 e Corolário 2, segue-se que S(n) = (2^{p-1}).S(b). Como S(n) = 2n, segue-se que (2^{p-1}). S(b) = 2^pb.

Temos então, que (2^p-1)|b, pois mdc(2^p, 2^{p-1}) = 1. Logo, existe c \in N, com c < b tal que b = c(2^p-1). Substituindo, segue-se: (2^{p-1}). S(b) = 2^p.(2^{p-1}).c; portanto, S(b) = 2^p.c. Como c e b são dois divisores distintos de b tais que c + b = 2^p.c. Nesta situação, c = 1. De fato, suponha por absurdo que c \ne 1. Temos então que S(b) \ge 1 + c + b > c + b = 2^p.c, segue-se que 2^pc = c + b < S(b) = 2^pc, contradição. Logo, concluímos que S(b) = b + 1, assim b é primo. Temos então que n = 2^{p-1}(2^p-1) com 2^p-1 primo.


Teorema 7: (Legendre)[11]

Sejam n um número natural e p um número primo, Então E_p(n!) = \begin{bmatrix} \frac{n}{p} \end{bmatrix} + \begin{bmatrix} \frac{n}{p^2} \end{bmatrix} + \begin{bmatrix} \frac{n}{p^3} \end{bmatrix} + ⋯ . (Denotaremos E_p(m) pelo expoente de maior potência de p que divide m e por \begin{bmatrix} \frac{n}{p} \end{bmatrix} o quociente da divisão de a por b, na divisão euclidiana)

Demonstração:

A soma apresentada no teorema é finita, pois existe um números natural r tal que p^i > n para todo i \ge r, portanto \begin{bmatrix} \frac{n}{p} \end{bmatrix} = 0 , se i \ge r. Vamos demonstrar o resultado por indução sobre n. A fórmula vale para n = 0. Suponha que vale para um natural m com m < n. Sabemos que os múltiplos de p entre 1 e n são p, 2p, ..., \begin{bmatrix} \frac{n}{p} \end{bmatrix}p. Portanto, E_p(n!) = \begin{bmatrix} \frac{n}{p} \end{bmatrix} +  E_p \begin{bmatrix} \frac{n}{p} \end{bmatrix}! . Pela hipótese de indução temos que E_p\begin{pmatrix}\begin{bmatrix} \frac{n}{p} \end{bmatrix}!\end{pmatrix} = \begin{bmatrix} \frac{\begin{bmatrix} \frac{n}{p} \end{bmatrix}}{p} \end{bmatrix} + \begin{bmatrix} \frac{\begin{bmatrix} \frac{n}{p} \end{bmatrix}}{p^2} \end{bmatrix} + \begin{bmatrix} \frac{\begin{bmatrix} \frac{n}{p} \end{bmatrix}}{p^3} \end{bmatrix} + ... . O resultado decorre da Proposição 6.


Teorema 8:[12]

Sejam p,n \in N* com p primo. Suponha que n = n_rp^r + n_{r-1}p^{r-1} + ... + n_1p  + n_0 seja a representação p-ádica de n. Então E_p(n!) = \frac{n-(n_0+n_1+...+n_r)}{p-1}.

Demonstração:

Sendo 0 \le n_i \le p, temos que \begin{bmatrix} \frac{n}{p} \end{bmatrix} = n_rp^{r-1}+n_{r-1}p^{r-2}+...+n_2p+n_1, \begin{bmatrix} \frac{n}{p^2} \end{bmatrix} = n_rp^{r-2}+n_{r-1}p^{r-3}+...+n_2, ..., \begin{bmatrix} \frac{n}{p^r} \end{bmatrix} = n_r. Portanto, E_p(n!) = \begin{bmatrix} \frac{n}{p} \end{bmatrix} + \begin{bmatrix} \frac{n}{p^2} \end{bmatrix} + \begin{bmatrix} \frac{n}{p^3} \end{bmatrix} + ⋯ \begin{bmatrix} \frac{n}{p^r} \end{bmatrix} = n_r \frac{p^r-1}{p-1}+n_{r-1} \frac{p^{r-2}-1}{p-1} +... + n_1 =  \frac{n_rp^r+n_{r-1}p^{r-1}+...+n_1p+n_0-(n_r+n_{r-1}+...+n_1+n_0)}{p-1} = \frac{n-(n_0+n_1+...+n_r)}{p-1}.


Lemas sobre números primos[editar | editar código-fonte]

Todos os lemas desta sessão tem como fonte o livro de HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.


Lema 1:[13]

Se um número natural n > 1 não é divisível por nenhum primo p tal que p^2 \le n, então ele é primo.

Demonstração:

Suponha, por absurdo, que n não seja divisível por nenhum número p tal que p^2 \le n e que não seja primo. Seja q o menor número primo que divide n, logo, n = q.k, com q \le k, Desse modo temos q^2 \le qk = n, o que mostra que n é divisível pelo número primo q tal que q^2 \le n, absurdo.


Lema 2: [14]

Seja p um número primo. Os números \begin{pmatrix} p \\ i \end{pmatrix}, onde 0 < i < p, são todos divisíveis por p.

Demonstração:

O resultado é válido para 1. Suponha então, 1 < i < p. Neste caso, i!|p.(p-1) . (p-2) . ... . (p-i+1). Como o mdc(i!, p) = 1, concluímos que , i!|(p-1) . (p-2) . ... . (p-i+1), e o resultado se segue, pois \begin{pmatrix} p \\ i \end{pmatrix} = p.\frac{(p-1)(p-2)...(p-1+i)}{i!}.


Lema 3:[15]
Seja n \in N*, Tem-se que s(n) = n + 1 se, e somente se, n é um número primo.

Demonstração:

Se S(n) = n + 1, segue-se que n > 1 e que os únicos divisores de n são 1 e n, logo n é primo. Reciprocamente, se n é primo, pela Proposição 5, segue-se que S(n) = \frac{n^2-1}{n-1} = n + 1.


Corolários sobre números primos[editar | editar código-fonte]

Todos os corolários desta sessão tem como fonte o livro de HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.

Corolário 1:[16]

Se p é um número primo e se a é um número natural não divisível por p, então p divide a^{p-1}-1

Demonstração:

Sabendo que p|a^{p}-a (Pequeno Teorema de Fermat), então p|a(a^{p-1}-1) e como mdc(a, p) = 1, podemos concluir que p|a^{p-1}-1.


Corolário 2:[17]

A função S(n) é multiplicativa, isto é, se mdc(n, m) = 1 então S(n.m) = S(n).S(m).

Demonstração:

Segue-se diretamente da demonstração da Proposição 5.


Proposições sobre números primos[editar | editar código-fonte]

Todos as proposições desta sessão tem como fonte o livro de HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.

Proposição 1:[18]
Sejam a, b, p \in N*, com p primo. Se p|ab, então p|a ou p|b.

Demonstração:

Se p|ab e p \nmid a então p|b. Mas se p\nmid a , temos que mdc(a, b) = 1.


Proposição 2:[19]

Seja n_1 = a_1^{u_1}.a_2^{u_2}.a_3^{u_3}....a_k^{u_k}. um número natural escrito decomposto em números primos. Se n_2|n_1 então n_2 = a_1^{v_1}.a_2^{v_2}.a_3^{v_3}....a_k^{v_k}, onde 0 \le v_i \le u_i, para i natural.

Demonstração:

Seja n_2 um divisor de n_1 e seja a^v a potência de um primo a, presente na decomposição de n_2 em um produto de seus fatores primos. Sabendo que a^v|n_1 segue que a^v divide algum a_i^{v_1} por ser primo com os demais a_j^{v_1} e, consequentemente, p = p_i e v < u_i.


Proposição 3:[20]

Sejam a e n números naturais maiores do que 1. Se a^n+1 é primo, então a é par e n = 2^m, com m \in N.

Demonstração:

Suponha que a^n + 1 seja primo, onde a > 1 e n > 1. Logo a tem que ser par, pois caso contrário, a^n + 1 seria par e maior do que dois, o que contraria o fato de ser primo. Se n tivesse um divisor primo p diferente de 2, teríamos n = kp com k \in N*. Logo, a^k+1|(a^k)^p + 1 = a^n+1, concretizando o fato desse último número ser primo. Isto implica que n é da forma 2^m.


Proposição 4:[21]

Sejam a e n números naturais maiores que 1. Se a^n-1 é primo, então a = 2 e n é primo.

Demonstração:

Suponha que a^n-1 seja primo, com a > 1 e  n > 1. Suponha por absurdo, que a > 2. Logo a-1 > 1 e a-1| a^n-1 e, portanto, a^n-1 não é primo, contradição. Consequentemente, a = 2. Por outro lado, suponha, que n não é primo. Temos n = rs com r > 1 e s > 1. Como 2^r-1 divide (2^r)^s-1 = 2n-1, segue que 2^n-1 não é primo, contradição, logo n é primo.


Proposição 5:[22]

Seja n = a_1^{u_1}.a_2^{u_2}.a_3^{u_3} ....a_k^{u_k} onde a_1, a_2, a_3, ..., a_k são números primos e u_1, u_2, u_3 ... u_k \in N*. Então, S(n) = \frac{a_1^{u_1+1}-1}{a_1-1}...\frac{a_k^{u_k+1}-1}{a_k-1}.

Demonstração:

Considere a igualdade (1+a_1+...+ a_1^{u_1}) ... (1+a_k+...+a_k^{u_k}) = \sum a_1^{w_1}...a_k^{w_k} , onde o somatório do primeiro membro da igualdade é tomado por todas as k-uplas (w_1...w_k) ao variar cada w_i no intervalo 0 \le wi \le u_i, para i = 0, 1, ..., k. Como tal somatório, pela Proposição 2, representa soma de todos os divisores de n, a fórmula S(n) resulta aplicando a fórmula da soma de uma progressão geométrica a cada soma do segundo membro da igualdade.


Proposição 6:[23]

Sejam a \in N e b, c \in N*, temos que  \begin{bmatrix} \frac {\begin{bmatrix} \frac{a}{b}\end{bmatrix}}{c} \end{bmatrix} = \begin{bmatrix} \frac{a}{bc}\end{bmatrix}. (Denotaremos por \begin{bmatrix} \frac{a}{b}\end{bmatrix} o quociente da divisão de a por b, na divisão euclidiana).

Demonstração:

Sejam  q_1 = \begin{bmatrix} \frac{a}{b}\end{bmatrix} e q_2 = \begin{bmatrix} \frac{\begin{bmatrix} \frac{a}{b}\end{bmatrix}}{c}\end{bmatrix} . Logo, a = bq_1+ r_1, com r_1 \le b-1 e \begin{bmatrix} \frac{a}{b}\end{bmatrix} = q_1 = cq_2 + r_2, com r_2 \le c-1. Portanto, a = bq_1+r_1 = b(cq_2+r_2)+r_1 = bcq_2+br_2+r_1. Como br_2+r_1 \le b(c-1)+b-1 = bc-1, segue-se que q_2 é o quociente da divisão de a por bc, ou seja, q_2 = \begin{bmatrix} \frac{a}{bc}\end{bmatrix}.


Teoria dos números[editar | editar código-fonte]

Sabe-se que, à medida que avançamos na sequência dos números inteiros, os primos tornam-se cada vez mais raros. Isto levanta duas questões:

O conjunto dos números primos seria finito ou infinito?

SEGUNDO EUCLIDES[24]

Suponhamos que a sucessão p_1 = 2, p_2 = 3, ..., p_r dos r números primos seja finita. Tomemos k = p_1.p_2.p_3. ... . p_r + 1 e seja p um número primo que divide k. O número p não pode ser igual a nenhum dos números p_1, p_2, ..., p_r porque então mele dividiria a diferença k-p_1.p_2.p_3. ... . p_r = 1, o que é impossível, Assim p é um número primo que não pertence à sucessão e, por consequência, p_1, p_2, ..., p_r não pode formar o conjunto de todos os números primos.


SEGUNDO KUMMER (uma variante da demonstração de Euclides)[25]

Suponha que exista um número finito de úmeros primos p_1 < p_2 < p_3 < ... < p_n; seja w = p_1. p_2 . p_3 . ... . p_n > 2. O inteiro w-1, sendo o produto de fatores primos, teria então um fator primo p_i, que dividiria também w; então, p_i dividiria 1 = w-(m -1), o que é absurdo.


SEGUNDO HERMITE[26]

Para todo número natural n existe um número primo p > n. Para isto basta escolher um número p qualquer dividindo n! + 1(teorema fundamental da aritmética). Se tivermos (n! + 1)-1 então p < n divide n!, como p divide n! + 1, logo p dividiria 1, absurdo.


SEGUNDO GOLDBACH[27]

Suponha uma sucessão infinita a_1,a_2, a_3, ... de naturais primos entre si, dois a dois, nenhum deles tem fator primo em comum. Se p_1 é um fator primo de a_1, p_2 é um fator primo de a_2, ... , p_n é um fator primo de a_n, então p_1, p_2, p_3, ..., p_n são todos distintos. Os números de Fermat F_n = 2^{2^n} +1 (para n \ge 0) são, dois a dois, primos entre si. Por recorrência sobre m demonstra-se que F_n-2 =F_0.F_1.F_3 . ... . F_{m-1}, então, se n < m, F_n divide F_m-2, Se existisse um número primo p que dividisse F_n e F_m, dividiria F_m-2, portanto dividiria 2, então p = 2. O que é impossível porque F_m é ímpar.


Dado um número natural n, qual é a proporção de números primos entre os números menores que n?


  • A resposta à primeira questão é que o conjunto dos primos é infinito, um resultado conhecido na parte central dos Elementos de Euclides, que lida com as propriedades dos números. Na proposição 20, Euclides explica uma verdade simples porém fundamental sobre os números primos: existe um número infinito deles. Pode-se demonstrar, em notação moderna, da seguinte forma:
Supondo que o número de primos seja finito e sejam  p_1,\ p_2,\ p_3,\ ...,\ p_n os primos. Seja  P o número tal que
P = \prod_{i=1}^n p_i + 1, onde \prod denota o produtório.
Se P é um número primo, é necessariamente diferente dos primos  p_1,\ p_2,\ p_3,\ ...,\ p_n, pois sua divisão por qualquer um deles tem um resto de 1.
Por outro lado, se P é composto, existe um número primo  q tal que  q é divisor de  P .
Mas obviamente  q \ne\ p_1,\; p_2,\; ...,\; p_n. Logo existe um novo número primo.
Há um novo número primo, seja P primo ou composto; este processo pode ser repetido indefinidamente, logo há um número infinito de números primos.
Uma outra prova envolve considerar um número inteiro n > 1. Temos n + 1 que, necessariamente, é coprimo de n (números coprimos são os que não têm nenhum fator comum maior do que 1). Provamos isto imaginando que a divisão do menor pelo maior tem resultado 0 e resto  n e do maior pelo menor tem resultado 1 e resto 1. Assim, n (n + 1) tem, necessariamente, ao menos dois factores primos.
Tomemos o sucessor deste, que representamos como n (n + 1) + 1. Pelo mesmo raciocínio, ele é coprimo a n (n + 1). Ao multiplicar os dois números, temos [n (n + 1)] * [n + (n + 1) + 1]. Como um de seus fatores tem pelo menos dois factores primos diferentes e é coprimo ao outro, o resultado da multiplicação tem pelo menos três factores primos distintos. Este raciocínio também pode ser infinitamente estendido.
  • A resposta para a segunda pergunta acima é que essa proporção é aproximadamente \frac{n}{\ln (n)}, onde \ln é o logaritmo natural.
  • Para qualquer número inteiro k, existem k números inteiros consecutivos todos compostos.
  • O produto de qualquer sequência de k números inteiros consecutivos é divisível por k!
  • Se k não é primo, então k possui, necessariamente, um fator primo menor do que ou igual a \sqrt{k}.
  • Todo inteiro maior que 1 pode ser representado de maneira única como o produto de fatores primos

Grupos e sequências de números primos[editar | editar código-fonte]

Pierre de Fermat (1601-1665) descobriu que todo número primo da forma 4n + 1, tal como 5,13,17,29,37,41, etc., é a soma de dois quadrados. Por exemplo:

 5 = 1^2 + 2^2,
13 = 2^2 + 3^2,
17 = 1^2 + 4^2,
29 = 2^2 + 5^2,
37 = 1^2 + 6^2,
41 = 4^2 + 5^2.

Hoje são conhecidos dois grupos de números primos:

  • (4n+1) - que podem sempre ser escritos na forma (x^2+y^2); e
  • (4n-1) - nunca podem ser escritos na forma (x^2+y^2).

Tratando-se de números primos é perigoso fazer uma generalização apenas com base numa observação, não solidamente comprovada matematicamente. Vejamos o exemplo:

31, 331, 3.331, 33.331, 333.331, 3.333.331 e 33.333.331 são primos mas 333.333.331 não é, pois 333.333.331 = 17 x 19.607.843.

Um olhar mais atento na forma como se distribuem os números primos revela que não há uma regularidade nesta distribuição. Por exemplo existem longos buracos entre os números primos, o número 370.261 é seguido de cento e onze[28] números compostos e não existem[29] primos entre os números 20.831.323 e 20.831.533.

Essa irregularidade na distribuição dos números primos é uma das razões[carece de fontes?] de não existir uma fórmula matemática que produza todos os números primos[carece de fontes?].

Algumas fórmulas produzem muitos números primos, por exemplo x^2 - x + 41 fornece primos quando x=0,\ 1,\ 2,\ ..., \ 40[30] [31] . Veja que para x = 41, a fórmula resulta em  41^2 que não é primo.

Não existe uma fórmula que forneça primos para todos os valores primos de x, de fato em 1752 Goldbach provou que não há uma expressão polinomial em x com coeficientes inteiros que possa fornecer primos para todos os valores de x.

Não se sabe se há uma expressão polinomial ax^2+bc+c com a \ne 0 que represente infinitos números primos. Dirichlet usou métodos para provar que se a, 2b e c não têm fator primo em comum, a expressão polinomial a duas variáveis

ax^2 + 2bxy + cy^2

representa infinitos primos, quando x e y assumem valores positivos inteiros.

Fermat pensou que a fórmula 2^{2^n} + 1 forneceria números primos para n = 0,\ 1,\ 2,\ .... Este números são chamados de números de Fermat e são comumente denotados por F_n. Os cinco primeiros números são:

F_0 = 3,\; F_1 = 5,\; F_2 = 17,\; F_3 = 257\; e \;F_4 = 65.537,

sendo todos primos.

Aproximações para o n-ésimo primo[editar | editar código-fonte]

Como consequência do teorema do número primo , uma expressão assintótica para o n-ésimo primo p_n é:

p_n \sim n \ln n.

Uma aproximação melhor é:

{ p_n = n \ln n +  n \ln \ln n - n + \frac{n}{\ln n} \left(\ln \ln n - 2 \right) - \frac{n\ln\ln n}{2(\ln n)^2}\left(\ln\ln n-6\right) + O\left( \frac {n} {(\ln n)^2}\right).}[32]

O teorema de Rosser mostra que p_n é maior que n \ln n. É possível melhorar esta aproximação com os limites [33] [34] :

 n \ln n + n(\ln\ln n - 1) < p_n <  n \ln n + n \ln \ln n \quad\mbox{para } n \ge 6.

Maior número primo já calculado[editar | editar código-fonte]

Em Janeiro de 2013, foi divulgado o maior número primo já calculado. Tem 17.425.170 dígitos que, se fosse escrito por extenso, ocuparia 3,4 mil páginas impressas com cinco mil caracteres cada.

É o número 2^{57885161} - 1

Foi descoberto por Curtis Cooper, da Universidade Central do Missouri em Warrensburg, EUA, como parte do Great Internet Mersenne Prime Search (GIMPS), um projeto internacional de computação compartilhada desenhado para encontrar números primos de Mersene[35] .

Ver também[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1. Vianna, João José Luiz. Elementos de Arithmetica. 15 ed. Rio de Janeiro: Francisco Alves, 1914. p. 59.
  2. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011 (pag. 90)
  3. Euclides, Os Elementos, Livro IX, Proposição 20 [em linha]
  4. RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012. (pag. 2 e 3)
  5. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 83)
  6. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 84)
  7. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 85)
  8. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 88)
  9. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 92)
  10. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 102)
  11. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 105)
  12. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 107)
  13. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 89)
  14. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 92)
  15. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 102)
  16. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011. (pag 93)
  17. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 101)
  18. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011. (pag. 83)
  19. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 84)
  20. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 97)
  21. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 98)
  22. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 101)
  23. HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 104)
  24. RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.(pag 1)
  25. RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.(pag 3)
  26. RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.(pag 4)
  27. RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.(pag 4)
  28. Conforme cálculo feito pelo Wolfram Alpha.
  29. Conforme cálculo feito pelo Wolfram Alpha.
  30. Hua (2009), p. 176-177"
  31. Ver lista dos valores, calculada pelo Wolfram Alpha
  32. Ernest Cesàro. (1894). "Sur une formule empirique de M. Pervouchine". Comptes rendus hebdomadaires des séances de l'Académie des sciences 119: 848–849. (em francês)
  33. Eric Bach, Jeffrey Shallit. Algorithmic Number Theory. [S.l.]: MIT Press, 1996. p. 233. vol. 1. ISBN 0-262-02405-5
  34. Pierre Dusart. (1999). "The kth prime is greater than k(ln k + ln ln k-1) for k>=2". Mathematics of Computation 68: 411–415.
  35. World’s largest prime number discovered -- all 17 million digits.

Referências[editar | editar código-fonte]

  • Hua, L. K.. Additive Theory of Prime Numbers. [S.l.]: AMS Bookstore, 2009. vol. 13. ISBN 978-0-8218-4942-2
  • Marcus du Sautoy, Os mistérios dos números: Uma viagem pelos grandes enigmas da matemática (que até hoje ninguém foi capaz de resolver), Jorge Zahar Editor Ltda, 2013 ISBN 8-537-81099-1
  • Luogeng Hua, Additive theory of prime numbers, American Mathematical Soc. ISBN 0-821-89750-0 (em inglês)
  • Mary Jane Sterling, Álgebra I Para Leigos , Alta Books Editora, 2013 ISBN 8-576-08256-X
  • Edward S. Wall, Teoria dos Números para Professores do Ensino Fundamental, McGraw Hill Brasil, 2014 ISBN 8-580-55353-9
  • PAULO BOUHID, NÚMEROS CRUZADOS, biblioteca24horas ISBN 8-578-93055-X
  • LAURA LEMAY, ROGERS CADENHEAD, APRENDA EM 21 DIAS JAVA 2 - TRADUÇÃO DA 4a ED. Elsevier Brasil ISBN 8-535-21685-5
  • HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.
  • RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.
  • SANTOS, José Plínio de Oliveira. Introdução à teoria dos Números. 3ª ed. Rio de Janeiro: IMPA, 2012.
  • LOVÁSZ, L. PELIKÁN, J. e VESZTERGOMBI, K. Matemática Discreta. 1ª ed. Rio de Janeiro: SBM, 2010.
  • http://paginapessoal.utfpr.edu.br/rwprobst/formacao-academica/curriculo/primos.pdf


Ligações externas[editar | editar código-fonte]

Wikilivros
O wikilivro Teoria de números tem uma página intitulada Números primos
Portal A Wikipédia possui o
Portal da Matemática.
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.