[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Provar congruencia
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 claudio@praticacorretora.com.br
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" <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>
> =========================================================================
>
=========================================================================
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>
=========================================================================