Re: [obm-l] Provar congruencia

["Eduardo Casagrande Stabel" <dudasta@xxxxxxxxxxxx>]

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>
=========================================================================