Re: [obm-l] 2 Problemas de Potenciação

[Bruno França dos Reis <bfreis@xxxxxxxxx>]

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 <jrvallim@yahoo.com.br> 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
=========================================================================