Prove que existe uma potência de 3 terminada nos dígitos 001 (na base decimal).
Passo 1
Beleza, o enunciado pede pra provar que existe alguma potência de 3 cujos três últimos dígitos sejam 001 em base decimal.
Conteúdo: teoria dos números – mais especificamente congruências, teorema de Euler e Teorema Chinês dos Restos (CRT).
O que a gente vai usar:
Conteúdo: teoria dos números – mais especificamente congruências, teorema de Euler e Teorema Chinês dos Restos (CRT).
O que a gente vai usar:
- noção de congruência (mod).
- função totiente de Euler, φ(n).
- teorema de Euler: se gcd(a,n)=1, então
- Teorema Chinês dos Restos para colar congruências mod 8 e mod 125 e obter mod 1000.
Passo 2
Calcular φ(1000). Primeiro fatoramos 1000 = 2³·5³.
Então
Então
Pelo teorema de Euler, como gcd(3,1000)=1, temos
Isto já mostra que 3^400 termina em 001. Mas dá para achar um expoente menor.
Passo 3
Vamos olhar separadamente mod 8 e mod 125:
- Módulo 8: φ(8)=4, então Euler diz
Daí qualquer expoente múltiplo de 4 também dá 1 mod 8. Em particular, 100 é múltiplo de 4, logo
- Módulo 125: φ(125)=100, então
Passo 4
Aplicando o Teorema Chinês dos Restos às congruências
vemos que há solução única módulo 1000 e ela é 1. Ou seja,
Resposta
Uma escolha concreta que funciona é
pois seus três últimos dígitos são 001. Logo existe sim uma potência de 3 terminada em 001.