Caros Carlos e Duda: A demonstração do Duda está correta desde que suponhamos que mdc(x,p*q) = 1, pois apenas nesse caso podemos aplicar o teorema de Euler para mod p*q.
Por exemplo, tome p = 3, q = 5, x = 6 e y = 12. Nesse caso, p*q = 15 e (p-1)*(q-1) = 12 ==> mdc(x,p*q) = 3 e y mod (p-1)*(q-1) = 0 Mas: x^y = 6^12 = 2.176.782.336 = 145.118.822*15 + 6 == 6 (mod 15) e x^0 = 1 == 1 (mod 15). Assim, acho que falta colocar no enunciado que mdc(x,p*q) = 1. Um abraço, Claudio. ----- Original Message ----- From: "Eduardo Casagrande Stabel" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Wednesday, March 26, 2003 3:10 PM Subject: Re: [obm-l] Provar congruencia > Oi Maçaranduba. > > A sua pergunta não é trivial, mas se você estudar aquele livro on-line que > te indiquei na última mensagem, aprenderá a resolver essa questão e verá que > ela é uma mera aplicação de um dos teoremas do livro. Mesmo que a sua > pergunta fosse trivial, teria importância. De perguntas triviais em > perguntas triviais, se chega a resolver as perguntas que dizemos não serem > triviais. E as coisas triviais, simples são as que contém a essência das > coisas, e geralmente são as mais difíceis de serem reparadas : não só em > matemática, como em tudo na vida. > > Definimos a função de Euler phy como > phy(n) = quantidade de naturais m não-maiores que n (1 <= m <= n) primos com > n, isto é, mdc(m,n)=1. > > Você pode provar, sem grandes dificuldades, que se p é um número primo então > phy(p^a) = p^a - p^(a-1). > > A função de Euler é multiplicativa, no sentido de que se mdc(p,q)=1 então > phy(p*q)=phy(p)*phy(q). Agora você tem uma fórmula para calcular qualquer > phy(n) se souber a fatoração prima de n. No seu caso em particular, phy(p*q) > = (p - 1)*(q - 1). > > Considere n fixo, e sejam a_1, a_2, ..., a_phy(n) todos os inversíveis no > módulo n (um a é inversível se existe b tal que a*b == 1 (mod n)). Seja a um > inversível qualquer. Você pode demonstrar que a*a_1, a*a_2, ..., a*a_phy(n) > são também todos os inversíveis no módulo n, portanto: > > a_1 * a_2 * ... * a_phy(n) == > a*a_1 * a*a_2 * ... * a*a_phy(n) == > a^(phy(n)) * a_1 * a_2 * ... * a_phy(n) (mod n) > => > 1 == a^(phy(n)) (mod n) > > Podemos fazer o último corte pois a_1 * a_2 * ... * a_phy(n) é um > inversível, e podemos multiplicar pelo seu inverso dos dois lados. O último > resultado é conhecido como teorema de Euler. De posse desse teorema, você > conseguirá demonstrar seu resultado escrevendo > > y = m * phy(n) + r, onde divide-se y por phy(n) com resto r > > Agora temos > > x^y == > x^(m * phy(n) + r) == > (x^m)^(phy(n)) * x^r == > x^r (mod n) > > usando o teorema de Euler, na última passagem. > > Abraço, > Duda. > > From: "Carlos Maçaranduba" <[EMAIL PROTECTED]> > > Ei pessoal talvez esse não seja tão trivial: > > > > Seja a^b("a" elevado a "b") , a==b(mod n)("a" é > > congruente a "b" modulo n) e "j mod c" o resto da > > divisão de "j" por "c". > > > > Seja x,y,p,q e n inteiros ,"n=p*q" e "p" e "q" são > > primos. > > > > Prove que: > > (x^y)==(x^( y mod[p-1]*[q-1] ) )(mod n) > > > > > > > > > > _______________________________________________________________________ > > Yahoo! Mail > > O melhor e-mail gratuito da internet: 6MB de espaço, antivírus, acesso > POP3, filtro contra spam. > > http://br.mail.yahoo.com/ > > ========================================================================= > > Instruções para entrar na lista, sair da lista e usar a lista em > > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > > O administrador desta lista é <[EMAIL PROTECTED]> > > ========================================================================= > > > > > > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > O administrador desta lista é <[EMAIL PROTECTED]> > ========================================================================= ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =========================================================================