FAMAT em Revista - Número 12 - Abril de 2009 91 Distribuição dos Números Primos Rafael Afonso Barbosa1, Antônio Carlos Nogueira2 1 2 Bolsista do PET-Matemática da Universidade Federal de Uberlândia Docente da Faculdade de Matemática da Universidade Federal de Uberlândia Introdução Historicamente, um problema que tem recebido uma atenção considerável por parte dos matemáticos é a distribuição dos números primos. Algumas questões relacionadas são: 1) Quantos números primos existem? 2) Existe algum polinômio com coeficientes inteiros que possua em seu conjunto imagem somente números primos? 3) Existem primos em progressão aritmética? 4) Quantos primos existem menores que certo inteiro? Neste trabalho apresentaremos soluções para cada uma destas questões, podendo assim compreender melhor como os números primos estão distribuídos no conjunto dos números inteiros. 1 Números primos Começaremos discutindo algumas questões básicas como, por exemplo, a quantidade de números primos, teorema fundamental da aritmética, dentre outras. Definição 1.1: Um número p ∈ Ν se diz primo se: i) p ≠ 0 e p ≠ 1. ii) Os únicos divisores de p são 1 e p . Teorema 1.1: Todo inteiro n > 1 pode ser expresso como produto de primos. Dem: i) ii) iii) Se n é primo, então n = n , que é produto de primos. Se n é composto, então n = n1 × n2 , onde 1 < n1 < n e 1 < n2 < n . Se n1 e n2 são, então n é produto de primos caso contrário, proceda como no passo (ii) e assim sucessivamente, um número finito de passos. α p = p1 1 × p 2 α2 α × ... × p r r Teorema 1.2: (Teorema Fundamental da aritmética) A fatoração de qualquer inteiro n > 1 em primos é única, a menos da ordem dos fatores. Dem: Suponha por contradição que exista um inteiro 1 < n1 < n com duas fatorações distintas. Dividindo pelos primos comuns as duas representações teríamos uma igualdade da forma: n = p1 × p 2 × ... × p r = q1 × q 2 × ... × q s 92 FAMAT em Revista - Número 12 - Abril de 2009 Onde os pi `s e q i `s são primos não necessariamente distintos, mas com nenhum primo dede lado direito da igualdade ocorrendo do lado esquerdo. Daí, p1 | q1 × q2 × ... × qs . Logo, p1 | qi para algum i = 1,2,..., s . O que é um absurdo, pois p1 ≠ q i , i = 1,2,..., s , ou seja, mdc(qi , p1 ) = 1, ∀i ∈ {1,2,..., s} . Teorema 1.3: Existem infinitos números primos. Demonstração de Euclides: Suponhamos por contradição que exista um número finito de primos p1 , p 2 ,..., p r . Façamos n = p1 × p 2 × ... × p r + 1 e seja p um primo que divide n . Esse número p não pode ser igual a nenhum dos números p1 , p 2 ,..., p r porque então ele dividiria n − p1 × p 2 × ... × p r = 1 , o que é impossível. Assim p é um primo distinto de p1 , p 2 ,..., p r e, por conseqüência, p1 , p 2 ,..., p r não podem formar o conjunto de todos os números primos. Demonstração de kummer: Suponhamos que exista um número finito de primos p1 < p 2 < ... < p n . Seja N = p1 × p 2 × ... × p n > 2 , pelo teorema fundamental da aritmética temos que o inteiro N − 1 teria um fator primo p i que dividiria também N . Então p i dividiria N − ( N − 1) = 1 , o que é absurdo. Demonstração de Hermite: Basta mostrar que para todo número natural n existe um número primo p > n . Tome então N = n!+1 , pelo teorema fundamental da aritmética temos que existe um número primo p qualquer dividindo N . Se N − 1 então p < n divide n! , então como p divide N e divide n! teríamos que p dividiria n!−N = 1 , o que é absurdo. Logo, N − 1 . Demonstração de Goldbach: Daremos aqui somente a idéia utilizada por Goldbach em sua demonstração. Basta achar uma sucessão infinita a1 , a 2 , a 3 ,... de números naturais, primos entre si, dois a dois, isto é, sem fator primo comum. Se p1 é um fator primo de a1 , p 2 um fator primo de a 2 ,..., p n um fator primo de a n ,..., então p1 , p 2 , p 3 ,..., p n ,... são todos distintos. Uma seqüência infinita de números naturais, primos entre si dois a dois, descoberta pro Goldbach e, independentemente a mesma demonstração foi descoberta por Hurwitz em 1891 é a seguinte. n Os números de Fermat Fn = 2 2 + 1 (para n ≥ 0 ) são, dois a dois, primos entre si. Por recorrência sobre m demonstra-se que Fn − 2 = F0 × F1 × ... × Fm−1 ; então, se n < m , Fn divide Fm − 2 . Se existisse um primo p que dividisse simultaneamente Fn e Fm , dividiria Fm − 2 e, portanto dividiria 2 , então p = 2 , o que é impossível porque Fm é ímpar. FAMAT em Revista - Número 12 - Abril de 2009 93 Demonstração de Euler: Se p é um número primo qualquer, então 1 / p < 1 . Daí, a soma da série geométrica de razão 1 / p e primeiro termo 1 é dada por: ∞ 1 ∑p k =0 k = 1 1 p 1− Igualmente, se q é outro número primo, então: ∞ 1 ∑q k k =0 = 1 1− 1 q Multiplicando membro a membro as duas igualdades acima, obtemos: 1+ 1 1 1 1 1 + + 2+ + 2 + ... = p q p pq q 1 1− 1 p × 1 1− 1 q O primeiro membro é a soma dos inversos de todos os inteiros naturais da forma p h q k (com h ≥ 0 , k ≥ 0 ), cada um sendo contando uma e uma só vez, porque a expressão de cada número natural, como produto de primos é única. Supõe-se que p1 , p 2 , p 3 ,..., p r formam a totalidade dos números primos. Para cada i = 1,2,3,..., r , tem-se: ∞ 1 ∑p k =0 k i = 1 1− 1 pi Multiplicando, membro a membro, essas r igualdades, obtêm-se: r ∞ ∏ (∑ i =1 k =0 r 1 1 ) = ∏ k 1 pi i =1 1− pi E o primeiro membro, uma vez efetuadas às operações, é a soma dos inversos de todos os números naturais, cada um contado uma só vez, como resulta do teorema fundamental. ∞ 1 É sabido que a série ∑ é divergente e, como seus termos são positivos, a ordem de n =1 n soma dos termos é irrelevante; O primeiro membro da igualdade será então infinito, enquanto que o segundo membro será finito. Isto é absurdo. Demonstração de Saidak: Toma-se uma seqüência crescente de números N 1 ,...N K ,... de tal modo que cada termo N K tenha pelo menos K fatores primos. Dessa forma, conclui-se que existem infinitos números primos. 94 FAMAT em Revista - Número 12 - Abril de 2009 A seqüência inicia com N > 0 , como N 1 e N 1 + 1 não tem divisores primos em comum, o produto N 2 = N 1 ( N 1 + 1) possui ao menos 2 divisores. Do mesmo modo, N 2 e N 2 + 1 não tem fatores em comum, logo N 3 = N 2 ( N 2 + 1) possui ao menos 3 fatores primos. O processo pode continuar indefinidamente, definindo-se sempre N K = N K −1 ( N K −1 + 1) e cada N K terá no mínimo K fatores primos. A seguir vamos apresentar uma nova demonstração para a existência de infinitos números primos. n Teorema 1.4: Considere a seqüência de números naturais da forma Rn = 2 p − 1 , p é primo impar. Sempre temos que Rn +1 = Rn × k e mdc( Rn , k ) = 1 , ∀n ∈ N . Dem: Observe que 2 p n +1 n n n n n − 1 = (2 p ) p − 1) = (2 p − 1)((2 p ) p −1 + (2 p ) p − 2 + ... + 2 p + 1) . n n n n Suponha que mdc(2 p − 1, (2 p ) p −1 + (2 p ) p −2 + ... + 2 p + 1) = d , daí vem que n n 2 p − 1 = dx ⇒ 2 p = dx + 1 substituindo na expressão acima temos: n n n (2 p ) p −1 + (2 p ) p −2 + ... + 2 p + 1 = (dx + 1) p −1 + (dx + 1) p −2 + ... + dx + 1 + 1 Como cada uma das potencias podem ser escritas da forma dm + 1 , temos que dm1 + 1 + dm 2 + 1 + ... + dm p − 2 + 1 + 1 + dx + 1 + 1 , fazendo M = m1 + m2 + ... + m p − 2 e observando que o 1 aparece p − 2 vezes, segue que: n n n n n n n n n (2 p ) p −1 + (2 p ) p − 2 + ... + 2 p + 1 = dm1 + 1 + dm2 + 1 + ... + dm p − 2 + 1 + dx + 1 + 1 (2 p ) p −1 + (2 p ) p − 2 + ... + 2 p + 1 = dM + p − 2 + dx + 1 + 1 (2 p ) p −1 + (2 p ) p − 2 + ... + 2 p + 1 = d ( M + x) + p n n n Logo, como d divide (2 p ) p −1 + (2 p ) p − 2 + ... + 2 p + 1 temos que d | p ⇒ d = p ou d = 1 . Observe que: p ≡ 1(mod p − 1) p 2 ≡ p × p ≡ 1(mod p − 1) p 3 ≡ p 2 × p ≡ 1(mod p − 1) Daí vem que p n ≡ 1(mod p − 1) , ∀n ∈ N , ou seja, p n = t ( p − 1) + 1, ∀n ∈ N . Logo: n 2 p − 1 = 2 ( p −1)t +1 − 1 = (2 p −1 ) t × 2 − 1 Pelo teorema de Euler que diz se mdc(a, m) = 1 ⇒ a ϕ ( m ) ≡ 1(mod m), ∀a, m ∈ Z . Temos 2 p −1 ≡ 1(mod p ) . Segue que: n 2 p − 1 = 2 ( p −1)t +1 − 1 = (2 p −1 ) t × 2 − 1 ≡ 1 × 2 − 1 ≡ 1(mod p) n n n n Logo, p não divide 2 p − 1 , então d = mdc(2 p − 1, (2 p ) p −1 + ... + 2 p + 1) = 1 . FAMAT em Revista - Número 12 - Abril de 2009 95 Como cada número da seqüência é o anterior vezes pelo menos mais um numero primo que não aparece na decomposição do mesmo, podemos afirmar que existem infinitos números primos. 1.1 Primos em certas progressões aritméticas Vamos agora fazer algumas observações interessantes relacionadas às varias maneiras que os números primos podem ser escritos usando o algoritmo de divisão de Euclides. Sabemos pelo algoritmo da divisão que todo inteiro pode ser escrito da seguinte maneira: 4n, 4n + 1 , 4n + 2 , 4n + 3 Tendo em vista que 4n e 4n + 2 são sempre pares. Então todos inteiros primos estão em duas progressões: * 4n + 1 1, 5, 9, 13, 17, 21,... * 4n + 3 3, 7, 15, 19,... É claro que estas progressões contem os números primos. Uma questão que surge então é quantos primos existem em tais progressões. Vamos então fazer uma demonstração usando o argumento parecido com o de Euclides para a infinitude dos números primos. Lema 1.1.1: O produto de dois ou mais inteiros da forma 4n + 1 é da mesma forma. Dem: Tome k = 4n + 1 e k ' = 4m + 1 , tendo em vista que é suficiente considerar o produto de apenas dois inteiros. Multiplicando-os temos: k × k ' = (4n + 1) × (4m + 1) = 16nm + 4n + 4m + 1 = 4(4nm + n + m) + 1 O que conclui a demonstração. Teorema 1.1.1: Existem infinitos números primos da forma 4n + 3 . Dem: Suponha pro contradição que existem finitos números primos da forma 4n + 3 , são eles p1 , p 2 , p 3 ,..., p r . Considere N tal que: N = 4 p1 p 2 p3 ... p r − 1 = 4( p1 p 2 p 3 ... p r − 1) + 3 Sendo N = r1 r2 r3 ...rt sua fatorização em primos. Como n é impar temos que rk ≠ 2, ∀k , então cada rk é da forma 4n + 1 ou 4n + 3 . Pelo lema temos que o produto dos inteiros da forma 4n + 1 é da mesma forma, como N é da forma 4n + 3 temos que algum ri = 4n + 3 , mas ri não pode ser igual a algum p1 , p 2 , p 3 ,..., p r , pois se fosse teríamos que ri | 1 . O que é absurdo. Daí, temos que existem infinitos números primos da forma 4n + 3 . A existência da infinidade de números primos da forma 4n + 1 também é verdadeira, mas em sua demonstração é necessário desenvolver alguns mecanismos matemáticos. 96 FAMAT em Revista - Número 12 - Abril de 2009 Teorema 1.1.2: Existem infinitos primos da forma 6n + 5 . Dem: Sabemos que todos os primos maiores que exceto 2 e 3 são da forma 6n + 5 ou 6n + 1 , observe que o produto de números da forma 6n + 1 são da mesma forma. Cosindere um número q da forma q = 6 p1 p 2 p 3 ... p r − 1 = 6( p1 p 2 p 3 ... p r − 1) + 5 Em que p1 , p 2 , p 3 ,..., p r sejam todos os primos da forma 6n + 5 . Como q é da forma 6n + 5 algum dos q i ' s também será. Mas se isto acontecesse teríamos que tal q i dividiria 1. O que é absurdo. Então existem infinitos números primos da forma 6n + 5 . Teorema 1.1.3: Se a e b são primos entre si, então todo primo impar divisor de a 2 + b 2 é da forma 4n + 1 . Não faremos a demonstração do teorema acima, mas o tomaremos como verdadeiro para demonstrar a infinitude de primos da forma 8n + 5 . Teorema 1.1.4: Existem infinitos primos da forma 8n + 5 . Dem: Considere q, tal que: q = 3 2 × 5 2 × 7 2 × ... p 2 + 2 2 é a soma de dois quadrados que não tem fator em comum. O quadrado de um número impar 2m + 1 é 4m(m + 1) + 1 . Observe que m pode ser par ou ímpar, vamos analisar ambas as situações: * m = 2r 4(2r )(2r + 1) + 1 = 8r (2r + 1) + 1 = 8n + 1 * m = 2r + 1 4(2r + 1)(2r + 2) + 1 = 4(4r 2 + 4r + 2r + 2) + 1 = 8(2r 2 + 3r + 1) + 1 = 8n + 1 Temos então que o quadrado de um número impar é sempre da forma 8n + 1 . Daí, segue que q é da forma 8n + 5 . Pelo teorema 5 todos os primos impares que dividem q são da forma 4n + 1 , entretanto eles também são da forma 8n + 1 ou 8n + 5 , já que 8n + 3 e 8n + 7 não podem ser escritos da forma 4n + 1 , e como o produto de dois números 8n + 1 é da forma temos que existe pelos menos um fator de q da forma 8n + 5 . Se tal fator fosse menor que p teríamos que ele dividiria 2 2 , o que é absurdo, pois ele é ímpar. Logo, existem infinitos primos da forma 8n + 5 . Teorema 1.1.5: (Dirichlet) Se a e b são inteiros positivos primos entre si, então a progressão aritmética a, a + b, a + 2b, a + 3b,... Contém infinitos números primos. Não faremos a demonstração devido a dificuldade apresentada em seu desenvolvimento. FAMAT em Revista - Número 12 - Abril de 2009 97 Teorema 1.2.6: Não existe uma progressão aritmética formada apenas por números primos. Dem: Seja a progressão a, a + b, a + 2b, a + 3b,... , suponha a + nb = p onde p é primo. Se colocarmos n k = n + kp, k = 1,2,3,... , temos: a + nk b = a + (n + kp )b = a + nb + kpb = p + kpb Então temos que a + n k b é divisível por p. Discutiremos agora um famoso problema sobre os números primos. Por séculos os matemáticos tentam encontrar uma fórmula que fornecesse somente primos, por exemplo: f (n) = n 2 + n + 41 Este polinômio assume valores primos para n variando de 0 ate 39. Observe a tabela: n n f (n) f (n) 0 41 14 251 1 43 15 281 2 47 16 313 3 53 17 347 4 61 18 383 5 71 19 421 6 83 20 461 7 97 21 503 8 113 22 547 9 131 23 593 10 151 24 641 11 173 25 691 12 197 26 743 13 223 27 797 No entanto, isto não é verdade para os casos n = 40 e n = 41: n 28 29 30 31 32 33 34 35 36 37 38 39 f (n) 853 911 971 1033 1057 1063 1231 1301 1373 1447 1523 1601 f (40) = 40 × 41 + 41 = 412 e f (41) = 41 × 42 + 41 = 41 × 43 Mas para n = 42 temos que f (42) = 1747 é um número primo. Vamos provar que não é possível encontrar um polinômio com coeficientes inteiros que tivesse como conjunto imagem somente números primos. Tome f (n) = a k n k + a k −1 n k −1 + ... + a 2 n 2 + an + a 0 com todos os coeficientes inteiros e a k ≠ 0 . Fixado o valor de n, n = n0 , f (n0 ) = p é um número primo. Agora, para algum inteiro t, consideremos a expressão f (n0 + tp ) : f (n0 + tp ) = a k (n0 + tp ) k + a k −1 (n0 + tp ) k −1 + ... + a 2 (n0 + tp ) 2 + a (n0 + tp ) + a 0 k k −1 2 f (n0 + tp) = (a k n0 + a k −1 n0 + ... + a 2 n0 + an0 + a0 ) + pQ(t ) f (n0 + tp ) = f (n0 ) + pQ(t ) f (n0 + tp ) = p + pQ(t ) = p (1 + Q(t )) 98 FAMAT em Revista - Número 12 - Abril de 2009 Onde Q(t) é um polinômio em t com coeficientes inteiros. Nós consideramos que p | f (n0 + tp ) , consequentemente, como todos os valores de f (n) são números primos f (n0 + tp ) = p para qualquer inteiro t. Como se trata de um polinômio de grau k ele não pode assumir o mesmo valor mais de k vezes, nós encontramos então uma contradição. Teorema 1.1.7: Teorema dos números primos O teorema dos números primos é um importante resultado sobre a distribuição dos números primos. Este resultado foi primeiramente demonstrado independentemente por dois matemáticos franceses Jacques Hadamard e Charles Jean De La Valle-Poussin através do estudo da função zeta de Riemann. Seja π (n) a função de contagem dos números primos, que retorna o numero de primos entre 1 e n. Então vale o limite: lim n →∞ π (n) n / ln n pn n →∞ n ln n = 1 ≈ lim N π (n) π ( n) 10 100 1000 10.000 100.000 1.000.000 10.000.000 100.000.000 1.000.000.000 10.000.000.000 100.000.000.000 4 25 168 1229 9.592 78.498 664.579 5.761.455 50.847.534 455.052.511 4.118.054.813 n / ln n 0,921 1,151 1,161 1,132 1,104 1,084 1,071 1,061 1,054 1,048 1,043 Tabela de π (n) e 2 π ( n) n / ln n Números Perfeitos Vamos estudar agora outro tipo de número especial são os chamados números perfeitos. Definição 2.1: Um inteiro positivo n é chamado de número perfeito se n for igual à soma de seus divisores positivos, excluindo o próprio n. A soma dos divisores positivos de um inteiro n, cada um deles menores que n, é dada por φ(n)-n. Deste modo, a condição “n é perfeito” é equivalente a dizer φ(n)-n= n. Por exemplo: φ(6) =1+2+3+6=12 φ(28) =1+2+4+7+14+28=2.28 Então 6 e 28 são números perfeitos. FAMAT em Revista - Número 12 - Abril de 2009 99 Teorema 2.1: Se 2 k − 1 é primo k ≥ 1 , então n = 2 k −1 × (2 k − 1) é perfeito e todo numero perfeito par é desta forma. Dem: Tome 2 k − 1 = p , primo, e considere n = p × (2 k −1 ) temos mdc(2 k −1 , p ) = 1, sabemos que: ϕ (n) = ϕ ( p × 2 k −1 ) = ϕ (2 k −1 ) × ϕ ( p) ϕ (n) = (2 k − 1) × ( p + 1) ϕ (n) = (2 k − 1) × (2 k ) = 2n Tornando n um número perfeito. Vamos provar agora que todo número perfeito par é desta forma. Tome n = 2 k −1 × m , onde m é um número inteiro impar e k ≥ 2 . Temos que mdc(2 k −1 , m) = 1, daí ϕ (n) = ϕ (m × 2 k −1 ) = ϕ (2 k −1 ) × ϕ (m) = (2 k − 1) × ϕ (m) Sabemos que para um número perfeito temos ϕ (n) = 2n = 2 k × m , consideraremos então: m × 2 k = 2 k − 1 × ϕ ( m) Temos então que 2 k − 1 | 2 k × m , mas 2 k − 1 e 2 k são relativamente primos, então (2 k − 1) | m ; Daí m = (2 k − 1) × M . Substituindo este valo na equação anterior temos ϕ (m) = 2 k × M . Como m e M são divisores de m M < m , nós temos: 2 k × M = ϕ ( m) ≥ m + M = 2 k × M Fazendo ϕ (m) = m + M a implicação é uma igualdade se m tiver somente dois divisores positivos, M e m. Considerando m primo tem-se que M = 1; em outras palavras, m = (2 k − 1) × M = 2 k − 1 é um numero primo, o que completa a prova. Então o problema de encontrar números perfeitos se reduz a procurar primos da forma 2 −1 . k Lema 2.1: Se a k − 1 é primo (a > 0, k ≥ 2) , então a = 2 e k é primo também. Dem: Podemos escrever a k − 1 = (a − 1)(a k −1 + a k − 2 + ... + a + 1) Onde, na presente situação: a k −1 + a k − 2 + ... + a + 1 ≥ a + 1 > 1 Mas da hipótese a k − 1 é primo, o outro fator na decomposição tem que ser 1; isto é, a − 1 = 1 então a = 2 . Se k fosse um número composto, teríamos k = r × s , com 1 < r e 1 < s . Deste modo a k − 1 = (a r ) s − 1 = (a r − 1)((a r ) s −1 + (a r ) s − 2 + ... + a r + 1) E cada fator da direita é mairo que 1. Mas isto viola a primaridade de a k − 1 , então temos k gerando uma contradição. Logo k é primo. Para p = 2, 3, 5, 7, os valores 3, 31, 127 de 2 p − 1 são primos, então temos: 2 × (2 2 − 1) = 6 100 FAMAT em Revista - Número 12 - Abril de 2009 2 2 × (2 3 − 1) = 28 2 4 × (2 5 − 1) = 496 2 6 × (2 7 − 1) = 8128 , são todos números perfeitos. Teorema 2.2: Todo numero perfeito ar n, termina com 6 ou 8, ou seja, n ≡ 6(mod10) ou n ≡ 8(mod 10) . Dem: Seja n um número perfeito par, n pode ser escrito como n = 2 k −1 × (2 k − 1) , onde 2 k − 1 é primo. De acordo com o lema nterior, o expoente k é primo. Se k = 2, então n = 6 o que está deacordocom o teorema. Vamos provar para k > 2, dividiremos o prova em duas partes. Sabemos que pode ser 4m + 1 ou 4m + 3 . Se k = 4m + 1 , então n = 2 4 m (2 4 m +1 − 1) = 2 8 m +1 − 2 4 m = 2 × 16 2 m − 16 m Como 16 t ≡ 6(mod 10), para todo inteiro positivo t. Usando congruência temos: n ≡ 2 × 6 − 6 ≡ 6(mod 10) Agora, se k = 4m + 3 : n = 2 4 m + 2 (2 4 m +3 − 1) = 2 8m +1 − 2 4 m = 2 × 16 2 m +1 − 4 × 16 m Como 16 t ≡ 6(mod 10) temos: n ≡ 2 × 6 − 4 × 6 ≡ −12 ≡ 8(mod 10) Conseqüentemente todo numero perfeito partermina em 6 ou 8. Conclusão Neste trabalho obtivemos importantes informações sobre o problema da distribuição dos números primos, podendo assim compreender um pouco melhor o mistério e o fascínio causado nos matemáticos pelos chamados números primos. Bibliografia [1] Hardy, G.H.; Wright, E.M. An Introduction To The Theory Of Numbers. 5° ed. Oxford Science Publications, 1979. [2] Burton, D.M. Elementary Number Theory. 5° ed. Mc-Graw-Hill Higher Education, 2002. [3] Hygino H. Domingues, São paulo, ed. Atual, 1991. [4] Ribenboim P., Associação Instituto Nacional de Matemática Pura e Aplicada, Rio de Janeiro, 2001.