Re: [obm-l] Provar congruencia

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

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" <dudasta@terra.com.br>
To: <obm-l@mat.puc-rio.br>
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" <soh_lamento@yahoo.com.br>
> > 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 é <nicolau@mat.puc-rio.br>
> >
=========================================================================
> >
> >
>
> =========================================================================
> 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 é <nicolau@mat.puc-rio.br>
> =========================================================================

=========================================================================
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 é <nicolau@mat.puc-rio.br>
=========================================================================