[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Re: Orientação para resolução
Alem disso,em geral se mdc(a,n)=1 entao a^phi(n)=1 (mod n).Como
phi(5^2)=4.5=20,2^20=1(mod 5^2) e logo 2^1000=(2^20)^50=1(mod 25).
Como obviamente 2^1000=0(mod 4),2^1000(mod 100) e' a unica classe
que e' 1 mod 25 e 0 mod 4,que e' 76.
Abracos,
Gugu
P.S.:Provem que existem algarismos a_0,a_1,a_2,... tais que, para todo n, o
numero x_n=a_(n-1)...a_1a_0 (base 10) = Soma(i=0 ate' n-1)(a_i.10^i) e' 1
mod 5^n e 0 mod 2^n,e que a sequencia dos a_n assim obtida e' unica e
nao-periodica (isso apareceu,sem o ultimo item, na Cone-Sul 1993 de
Petropolis).Temos naturalmente x_2=76,i.e.,a_0=6 e a_1=7.Na verdade,a
propriedade que aparecia na prova e' que x_n^2-x_n e' divisivel por 10^n,
ou seja,x_n coincide com os n ultimos digitos de seu quadrado(provem).
>
>Uma maneira mais genérica de fazer esse cálculo seria utilizando "divisão
>e conquista" em que a potência é sempre dividida por dois. Assim:
>
>(Sempre mod 100)
>
>2^1000 = (2^500)^2
>2^500 = (2^250)^2
>2^250 = (2^125)^2
>2^125 = 2.(2^62)^2
>2^62 = (2^31)^2
>2^31 = 2.(2^15)^2
>2^15 = 2.(2^7)^2
>2^7 = 2.(2^3)^2
>2^3 = 8
>
>Agora é só substituir de trás pra frente.
>As contas de quadrado mod 100 ficam fáceis se fizer assim:
>x = 10a + b
>x^2 = 100a^2 + 20ab + b^2
>x^2 = 20ab + b^2 (mod 100)
>
>e 20ab (mod 100) = ((ab mod 10).2 mod 10).10
>
>Processando...
>2^7 = 2.64 = 28
>2^15 = 2.84 = 68
>2^31 = 2.24 = 48
>2^62 = 48^2 = 04
>2^125 = 2.16 = 32
>2^250 = 32^2 = 24
>2^500 = 24^2 = 76
>2^1000 = 76^2 = 76
>
>Normalmente isso não dá muitas contas.
>É aproximadamente floor(log(n base 2)) operações de quadrado onde n é o
>expoente.
>
>Até mais
>
>Vinicius Fortuna
>
>
>On Mon, 21 Jan 2002 ghaeser@zipmail.com.br wrote:
>
>> >Quais são os últimos dois algarismos de 2^1000 ??
>>
>>
>> Não sei resolver esse tipo de questão, mas como encontrei a resposta certa
>> resolvi mandar a mensagem !!
>>
>> Será que alguém poderia postar uma maneira mais fácil de obter essa resposta
>> ??
>>
>>
>> obs : as igualdades são todas mod 100
>>
>> 2^10 = 24
>> (2^10)^100 = 24^100 = (2^3*3)^100 =
>>
>> (2^10)^30*3^100 = 24^30*3^100 = (2^3*3)^30*3^100 =
>>
>> (2^10)^9*3^130 = 24^9*3^130 = (2^3*3)^9*3^130 =
>>
>> 2^27*3^139 = 2^30/8*3^139 = 24^3/8*3^139 = 12^3*3^139 =
>>
>> 4^3*3^142 = 64*3^142
>>
>> analisando as potencias de 3 mod 100:
>>
>> 3^1=3
>> 3^2=9
>> 3^3=27
>> 3^4=81
>> 3^5=43
>> 3^6=29
>> 3^7=87
>> 3^8=61
>> 3^9=83
>> 3^10=49
>>
>>
>>
>> 3^142*64=49^14*64*9
>>
>>
>> analisando as potencias de 49 mod 100:
>>
>> 49^1=49
>> 49^2=01
>> 49^3=49
>> 49^4=01
>> ..
>> 49^14=01 mod 100
>>
>> assim, temos que : 49^14*64*9 = 64*9 = 76 mod 100
>>
>> Portanto os últimos dois algarismos de 2^1000 é 76
>> conferindo :
>>
>> 2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
>>
>>
>>
>> "Mathematicus nascitur, non fit"
>> Matemáticos não são feitos, eles nascem
>>
>>
>> ------------------------------------------
>> Use o melhor sistema de busca da Internet
>> Radar UOL - http://www.radaruol.com.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>
>> =========================================================================
>>
>
>--
>[ Vinicius José Fortuna ]
>[ vinicius.fortuna@ic.unicamp.br ]
>[ Visite www.viniciusf.cjb.net ]
>
>
>=========================================================================
>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>
=========================================================================