E essa função que vc mencionou, não seria a função fi de Euler, ou seja números primos entre si que são menores que n. Matematicamente, fi: N -> N ; fi(n) = {k pertencente a K; 0<= n < k ; mdc (k,n) =1 A dedução do problema é a seguinte: Usando a definição de fatoração canonical temos que Pn =p1^a1 * ... * pn^an. Defina Nn = Pn + 1, supondo que pn+1 seja o menor fator de Nn. Temos que pn+1 não assumi nenhum valor de p1, p2, ..., pn. Então temos {Pk}k>0, o que prova que quando pi(x) tende ao infinito com x tendendo ao infinito existem infinitos números primos. O pi(x) que estou mencionando é pi(x) > log2log2 (x) sendo o 2 a base. Não entendi essa teoria direito. -----Mensagem original----- De: Bruno Leite <[EMAIL PROTECTED]> Para: [EMAIL PROTECTED] <[EMAIL PROTECTED]> Data: Domingo, 6 de Fevereiro de 2000 21:14 Assunto: pi(x) e primos da forma 4k+1 >>Outro Problema, Alguém conhece a função pi(x)? Quer me explicar? >>Tem um exercício, porém não entendi direito. >> >>O exercício pede para Provar que há infinitos número primos congruentes a 1 >>mod 4. >> >> >> >>Muito Obrigado! >> >>Marcos Eike Tinen dos Santos >> >Caro Marcos, > >A função pi(x) que eu conheço (e torço para que estejamos falando da mesma >função!) >é definida assim: > >pi(x)= número de primos menores que x. (ou será que é menor OU IGUAL? - >alguém da lista pode confirmar)) > >Uma prova de que existem infinitos primos da forma 4k+1 é a seguinte: > >Suponha que existam n primos dessa forma:p1, p2, ..., pn. > >Considere o número X=(p1.p2. ... .pn)^2 + 1. Ele é maior que qualquer primo >da forma 4k+1 e portanto por hipótese é composto. > >Notando que ele não é uma potência de 2(pois é congruente a 2 no módulo 4) >então algum primo ímpar q o divide: X=0(mod q) > >Suponha que q é da forma 4k+3. Então X=0(mod q) -> (p1.p2. ... .pn)^2 = -1 >(mod q) > >Elevando tudo a 0,5(p-1), temos (p1.p2. ... .pn)^(p-1) = -1^(0,5(p-1)) (mod >q) > >Como p=4k+3 por hipótese, > >(p1.p2. ... .pn)^(p-1) = -1^(0,5(4k+2)) (mod q) > >(p1.p2. ... .pn)^(p-1) = -1^(2k+1) (mod q) > >No entanto o lado esquerdo dessa igualdade vale 1 (pelo pequeno teorema de >Fermat) >enquanto o direito vale -1. Isso é, >1=-1(mod q) o que implica em q=2 ou q=1, um absurdo pois q é primo ímpar. > >Assim, q é da forma 4k+1 e portanto q pertence ao conjumto (supostamente >finito) {p1, p2, ..., pn.}. Assim, q=px (x é um índice de p, não está >multiplicando p), com 1<=x<=n > >Temos X=0(mod q) -> (p1.p2. ... .pn)^2 + 1=0(mod px) -> 1=0(mod px) ABSURDO. > >Portanto existem infinitos primos da forma 4k+1!!! > >Bruno Leite
Re: pi(x) e primos da forma 4k+1
Marcos Eike Tinen dos Santos @ ITA @ Sun, 6 Feb 2000 17:41:13 -0800