Re: [obm-l] congruencias

[Cesar Ryudi Kawakami <cesarkawakami@xxxxxxxxxx>]

Droga, escrevi a mensagem com pressa.

Pensando melhor eu escrevi muita porcaria...

Fazendo algumas contas:

2 congruente a 2 mod 13
2^2 congruente a 4 mod 13
(2^2)^5 congruente a 4^5 mod 13 (4^5 = 1024, dá pra fazer na mao, e depois 
divide por 13) => congruente a 10 mod 13
(2^10)^7 congruente a 10^7 mod 13 (divide na mao 10^7 por 13, acha:) 
congruente a 10 mod 13.

logo 2^70 congruente a 10 mod 13.

Agora:

3 congruente a 3 mod 13;
3^2 = 9 congruente a 3^2 = 9 mod 13
(3^2)^5 congruente a 9^5 = 59049,  congruente a 3 mod 13
(3^10)^7 congruente a 3^7 = 2187, congruente a 3 mod 13.

logo 3^70 congruente a 3 mod 13.

Somando, temos que 2^70 + 3^70 congruente a 13 mod 13, logo 2^70 + 3^70 
congruente a 0 mod 13, e 13 divide 2^70 + 3^70.

É mais rápido pelo pequeno teorema de fermat, onde 2^13 congruente a 2 mod 
13 e 3^13 congruente a 3 mod 13...

At 15:46 11/3/2004, you wrote:

>-----Mensagem Original-----
>De: "Cesar Ryudi Kawakami" <cesarkawakami@uol.com.br>
>Para: <obm-l@mat.puc-rio.br>
>Enviada em: quinta-feira, 11 de março de 2004 14:41
>Assunto: Re: [obm-l] congruencias
>
>
>Uma solucao sem cálculos seria esta:
>
>13 divide 2^70 + 3^70 implica que:
>
>2^70 + 3^70 = 0 (mod 13) , onde = denota congruencia.
>
>logo
>
>2^70 = -3^70 (mod 13)
>
>como a^k = b^k (mod m) => a = b (mod m),  ISTO É FALSO
>
>ver o artigo do Yuri Gomes, temos:
>
>2 = -3 (mod 13) ISTO É FALSO
>
>
>13 divide -3 - (-2) = -1, verdade. ISTO É FALSO
>
>
>Logo 13 divide 2^70 + 3^70.
>
>At 13:42 10/3/2004, you wrote:
> >Bem, e se voces usassem sorobans?
> >
> >Claudio Buffara <claudio.buffara@terra.com.br> wrote:
> >Calculadora? Que calculadora?
> >
> >on 10.03.04 00:43, Faelccmm@aol.com at Faelccmm@aol.com wrote:
> >
> >CLARAMENTE para quem: Para voce ou para a sua calculadora ?
>:-))))))))))))))
> >
> >
> >
> >
> >Em uma mensagem de 9/3/2004 16:39:15 Hora padrão leste da Am. Sul,
> >peterdirichlet2002@yahoo.com.br escreveu:
> >
> >
> >
> >Realmente, ,mais humilhante nao podia ser...
> >
> >Claudio Buffara <claudio.buffara@terra.com.br> wrote:
> >on 09.03.04 01:14, Faelccmm@aol.com at Faelccmm@aol.com wrote:
> >
> >Ola pessoal,
> >
> >
> >Prove que 2^70 + 3^70 eh divisivel por 13.
> >
> >Esse eh facil.
> >
> >Basta ver que 2^70 + 3^70 = 2503155504994422192936289397389273, o qual eh
> >claramente divisivel por 13. O quociente eh
>192550423461109399456637645953021.
> >
> >[]'s,
> >Claudio.
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> ><http://br.rd.yahoo.com//mail_br/tagline/?http://br.yahoo.com/info/mail.htm
>l>Yahoo!
> >Mail - O melhor e-mail do Brasil. Abra sua conta agora!
>
>
>=========================================================================
>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
>=========================================================================
>
>=========================================================================
>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
>=========================================================================


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