Re: [obm-l] Fatorial de primos
Vamos tentar uma prova por absurdo, vamos supor (p-1)!=-1 (modp), mas que p não seja primo, então p deve ser igual a m.n , (p=m.n), com 1
RE: [obm-l] Fatorial de primos
Olá Douglas, Na verdade essa prova eu consegui, mas note que isso só prova que não existe p composto tal que (p-1)! = -1 (mod. p), mas não prova que para os primos isso vale (só prova que para os não-primos não vale). Seguindo a idéia Tiago do fiz assim:Basta provar o seguinte 1) Sendo p primo, sendo 1 x p-1 e 1 y p-1, x != y, temos que escolhendo 1 x sempre vai existir um y inverso de x mod p, ou seja, y tal que x.y = 1 mod p 2) y é único A segunda é fácil provar:Se existisse um outro número (digamos z) y tal que x.z = 1 (mod p), sendo z = y+m, temos x(y+m) = 1 (mod p ) - xm = 0 (mod p) - m = pk, Logo m = 0 ou m=p, absurdoLogo não existe z A primeira ainda não consegui provarAlguém me dá uma ajuda? []'sJoão Date: Mon, 20 Feb 2012 09:09:31 -0200 From: douglas.olive...@grupoolimpo.com.br To: obm-l@mat.puc-rio.br Subject: Re: [obm-l] Fatorial de primos Vamos tentar uma prova por absurdo, vamos supor (p-1)!=-1 (modp), mas que p não seja primo, então p deve ser igual a m.n , (p=m.n), com 1mp e 1np , como pI(p-1)!+1 , logo mI(p-1)!+1 pois mIp, e como mp, mI(p-1)!, conclui-se que m divide a diferença (p-1)!+1-(p-1)!=1, o que é absurdo, logo m deve ser primo!! On Sun, 19 Feb 2012 23:44:53 -0300, João Maldonado wrote: Prove que sendo p um primo, (p-1)! = -1 (mod. p) Como posso provar isso? []'s João
Re: [obm-l] Fatorial de primos
A primeira é consequência do teorema de Bézout: Se 0xp, então (x,p)=1 e logo existem y, z tais que xy+pz=1, logo xy==1 (mod p), logo y mod p é inverso de x. Lucas Colucci 2012/2/20 João Maldonado joao_maldona...@hotmail.com Olá Douglas, Na verdade essa prova eu consegui, mas note que isso só prova que não existe p composto tal que (p-1)! = -1 (mod. p), mas não prova que para os primos isso vale (só prova que para os não-primos não vale). Seguindo a idéia Tiago do fiz assim: Basta provar o seguinte 1) Sendo p primo, sendo 1 x p-1 e 1 y p-1, x != y, temos que escolhendo 1 x sempre vai existir um y inverso de x mod p, ou seja, y tal que x.y = 1 mod p 2) y é único A segunda é fácil provar: Se existisse um outro número (digamos z) y tal que x.z = 1 (mod p), sendo z = y+m, temos x(y+m) = 1 (mod p ) - xm = 0 (mod p) - m = pk, Logo m = 0 ou m=p, absurdo Logo não existe z A primeira ainda não consegui provar Alguém me dá uma ajuda? []'s João -- Date: Mon, 20 Feb 2012 09:09:31 -0200 From: douglas.olive...@grupoolimpo.com.br To: obm-l@mat.puc-rio.br Subject: Re: [obm-l] Fatorial de primos Vamos tentar uma prova por absurdo, vamos supor (p-1)!=-1 (modp), mas que p não seja primo, então p deve ser igual a m.n , (p=m.n), com 1mp e 1np , como pI(p-1)!+1 , logo mI(p-1)!+1 pois mIp, e como mp, mI(p-1)!, conclui-se que m divide a diferença (p-1)!+1-(p-1)!=1, o que é absurdo, logo m deve ser primo!! On Sun, 19 Feb 2012 23:44:53 -0300, João Maldonado wrote: Prove que sendo p um primo, (p-1)! = -1 (mod. p) Como posso provar isso? []'s João
Re: [obm-l] Fatorial de primos
2012/2/20 João Maldonado joao_maldona...@hotmail.com: Olá Douglas, Na verdade essa prova eu consegui, mas note que isso só prova que não existe p composto tal que (p-1)! = -1 (mod. p), mas não prova que para os primos isso vale (só prova que para os não-primos não vale). Seguindo a idéia Tiago do fiz assim: Basta provar o seguinte 1) Sendo p primo, sendo 1 x p-1 e 1 y p-1, x != y, temos que escolhendo 1 x sempre vai existir um y inverso de x mod p, ou seja, y tal que x.y = 1 mod p Vamos ver. Queremos que para todo a (que não seja múltiplo de p) exista um X tal que p seja divisor de aX-1 Vamos usar PCP. Testamos todos os valores de X de 0 até p-1 (testar acima de p é supérfluo: X=p+Y, a*(p+Y)-1 = ap+(aY-1), e reduzimos o problema). Se tivermos sorte, algum zera! E se der o azar? Bem, podemos calcular o resto de aX-1 por p. Os valores possíveis, dado a ausência de um zero, vão de 1 até p-1. Temos um cara a mais - existem X1 e X2 tais que aX1-1 e aX2-1 deixam o mesmo resto. Logo, p é divisor de aX1-1-aX2+1 =a(X1-X2). Como a não é múltiplo, p é divisor de X1-X2. E agora? Não eram os Xzes diferentes? Pois, por esse absurdo, sabemos que não vai dar azar de não zerar. 2) y é único A segunda é fácil provar: Se existisse um outro número (digamos z) y tal que x.z = 1 (mod p), sendo z = y+m, temos x(y+m) = 1 (mod p ) - xm = 0 (mod p) - m = pk, Logo m = 0 ou m=p, absurdo Logo não existe z A primeira ainda não consegui provar Alguém me dá uma ajuda? []'s João Date: Mon, 20 Feb 2012 09:09:31 -0200 From: douglas.olive...@grupoolimpo.com.br To: obm-l@mat.puc-rio.br Subject: Re: [obm-l] Fatorial de primos Vamos tentar uma prova por absurdo, vamos supor (p-1)!=-1 (modp), mas que p não seja primo, então p deve ser igual a m.n , (p=m.n), com 1mp e 1np , como pI(p-1)!+1 , logo mI(p-1)!+1 pois mIp, e como mp, mI(p-1)!, conclui-se que m divide a diferença (p-1)!+1-(p-1)!=1, o que é absurdo, logo m deve ser primo!! On Sun, 19 Feb 2012 23:44:53 -0300, João Maldonado wrote: Prove que sendo p um primo, (p-1)! = -1 (mod. p) Como posso provar isso? []'s João -- /**/ 神が祝福 Torres = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
Re: [obm-l] Fatorial de primos
Lembre-se que todo elemento não nulo mod p possui um inverso mod p. Use este fato para enxergar (p-1)! de maneira esperta. On Mon, Feb 20, 2012 at 12:44 AM, João Maldonado joao_maldona...@hotmail.com wrote: Prove que sendo p um primo, (p-1)! = -1 (mod. p) Como posso provar isso? []'s João -- Tiago J. Fonseca http://legauss.blogspot.com
