Caros Carlos e Duda: Acho que matei a aula de tabuada do pre-primario. De qualquer forma, o exemplo pode ser salvo...
se p = 3 e q = 5, entao (p-1)*(q-1) = 8 (e nao 12....) tomando x = 6 e y = 8, teremos mdc(x,p*q) = 3 e y mod (p-1)*(q-1) = 0 x^y = 6^8 = 1.679.616 = 111.974*15 + 6 == 6 (mod 15) e x^0 = 1 == 1 (mod 15) --------- Por outro lado, um resultado parecido que vale para um inteiro x qualquer eh o seguinte (p e q sao primos distintos): x^(p*q) + x == x^p + x^q (mod p*q) Alem disso, tambem vale: x^(p+q) + x^2 == x^(p+1) + x^(q+1) (mod p*q) Isso sem falar que: p^(q-1) + q^(p-1) == 1 (mod p*q) Um abraco, Claudio. on 26.03.03 17:04, Cláudio (Prática) at [EMAIL PROTECTED] wrote: > 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]> > ========================================================================= > ========================================================================= 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]> =========================================================================