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 [EMAIL PROTECTED] 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 é <[EMAIL PROTECTED]> >> ========================================================================= >> > >-- >[ Vinicius José Fortuna ] >[ [EMAIL PROTECTED] ] >[ 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 é <[EMAIL PROTECTED]> >========================================================================= ========================================================================= 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 é <[EMAIL PROTECTED]> =========================================================================