1) (10k+4)^n mod 10 = 4^n mod 10 4^1 mod 10 = 4 4^2 mod 10 = 6 4^3 mod 10 = 4 ... 4^(2k + 1) mod 10 = 4 4^(2k) mod 10 = 6
.:. 2004^2004 mod 10 = (2000 + 4)^2004 mod 10 = 4^2004 mod 10 = 6 2) (1000k + 3)^n mod 1000 = 3^n mod 1000 .:. 2003^n = 3^n mod 1000 -- 3^2 = 9 = 10-1 3^2a = (10-1)^a pelo bin�mio de newton temos: (10-1)^a = sum(i=0..a; Ca,i * 10^i * (-1)^(a-i)) = (-1)^a + Ca,1 * 10 * (-1)^(a-1) + Ca,2 * 100 * (-1)^(a-2) + Ca,3 * 1000 * (-1)^(a-3) + ... + 10^a a partir desse ultimo termo que representei, todos os outros possuem o fator 1000, portanto s�o congruentes a 0 mod 1000. Temos ent�o que: (10-1)^a = (-1)^a + 10a * (-1)^(a-1) + 100a(a-1)/2 * (-1)^(a-2) (mod 1000) Se a=2b, temos: (10-1)^a = 3^2a = 3^4b = (-1)^(2b) + 10*2b*(-1)^(2b-1) + 100* 2b(2b-1) /2 * (-1)^(2b-2) (mod 1000) => 3^4b = 1 - 20b +100b(2b-1) (mod 1000) Vamos verificar quando 3^4b � congruente a 1 mod 1000. Para isso, precisamos que -20b+100b(2b-1) seja congruente a 0. Podemos ent�o fazer: 100b(2b-1) - 20b = 200b^2 - 120b = 1000k => 5b^2 - 3b = 25k. Temos que 5b^2 -3b ser� m�ltiplo de 25 quando ambos os termos da soma o forem. Ent�o, se tomarmos b = 25, satisfazendo essa condi��o, temos: 3^100 = 1 (mod 1000) Fazendo 2002^2001 = 100t + r, temos: 3^(2002^2001) = 3^(100t + r) = 3^r * 3^100t = 3^r * (3^100)^t = 3^r * 1^t = 3^r (mod 1000) Vamos achar r: r = 2002^2001 = 2^2001 = 4*2^1999 (mod 100 = 4*25) => r/4 = 2^1999 (mod 25). Para simplificar essa conta, temos que achar alguma potencia de 2 que seja congruente a 1 ou -1 mod 25. Temos o 1024, por exemplo: 2^10 = 1024 = 24 = -1 (mod 25) => 2^1999 = 2^9 * (2^10)^199 = 512 * (-1)^199 = 12 * -1 = -12 = 13 Ent�o r/4 = 13 => r=52. Portanto temos que 2003^(2002^2001) = 3^52 (mod 1000) Mas 3^4b = 1 - 20b + 100b(2b-1) (mod 1000), como demonstrado acima. Ent�o: 3^(4*13) = 1 - 20*13 + 100*13*(26-1) = 1 - 260 + 2500*13 = 1-260+32500 = 32241 = 241 (mod 1000) Portanto, os tr�s �ltimos algarismos de 2003^(2002^2001) s�o 241!!! Gostei dessa! Abra�o bruno On Sat, 27 Nov 2004 20:18:23 -0300 (ART), Jo�ffffffffffffffffe3o Ricardo <[EMAIL PROTECTED]> wrote: > > Ol�!!! > Meu nome � Jo�o Ricardo, sou professor do Ensino M�dio e acabo de me > inscrever nesta lista. > Gostaria de aproveitar a oportunidade para propor 2 problemas que considero > interessantes; o primeiro deles, elaborei para os meus alunos, j� o segundo > (que n�o consegui encontrar resposta certa), foi um problema da CMO 2003 - > Olimp�ada Canadense de Matem�tica. > Aqui v�o eles: > > 1) Qual o �ltimo d�gito de 2004^2004? > > 2) Quais os tr�s �ltimos d�gitos de 2003^(2002^2001)? > > Tentei resolver o segundo da mesma maneira que resolvi o primeiro, e n�o > consegui encontrar o resultado correto. > > Abra�os!!! > Jo�o Ricardo -- Bruno Fran�a dos Reis email: bfreis - gmail.com gpg-key: http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key icq: 12626000 e^(pi*i)+1=0 ========================================================================= 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 =========================================================================
