Olimpíadas ⇒ Princípio da Casa dos Pombos Tópico resolvido
Moderador: [ Moderadores TTB ]
-
goncalves3718
- Mensagens: 816
- Registrado em: Qui 26 Dez, 2019 15:26
- Última visita: 11-04-23
Set 2020
21
15:46
Princípio da Casa dos Pombos
Prove através do Princípio da Casa dos Pombos que existe uma potência de 3 [tex3][/tex3]
terminada nos dígitos [tex3]001[/tex3]
(na base decimal).
Set 2020
22
15:22
Re: Princípio da Casa dos Pombos
Para encontrar os últimos 3 dígitos, vemos o resto da divisão de um número por 1000
Os restos na divisão por 1000 formam um conjunto finito: 0,1,2,3,4,....,999
Mas as potências de 3 são infinitas
Sendo assim, devem existir duas potências de 3 com o mesmo resto na divisão por 1000:
[tex3]3^a \equiv 3^b \mod(1000) [/tex3]
[tex3]3^b \cdot (3^{a-b}- 1) \equiv 0 \mod(1000) [/tex3]
Só que [tex3]mdc(3^b, 1000) = 1 [/tex3] , sendo assim:
[tex3]3^{a-b}- 1 \equiv 0 \mod(1000) [/tex3]
[tex3]3^{a-b} \equiv 1 \mod(1000) [/tex3]
Os restos na divisão por 1000 formam um conjunto finito: 0,1,2,3,4,....,999
Mas as potências de 3 são infinitas
Sendo assim, devem existir duas potências de 3 com o mesmo resto na divisão por 1000:
[tex3]3^a \equiv 3^b \mod(1000) [/tex3]
[tex3]3^b \cdot (3^{a-b}- 1) \equiv 0 \mod(1000) [/tex3]
Só que [tex3]mdc(3^b, 1000) = 1 [/tex3] , sendo assim:
[tex3]3^{a-b}- 1 \equiv 0 \mod(1000) [/tex3]
[tex3]3^{a-b} \equiv 1 \mod(1000) [/tex3]
Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 0 Respostas
- 3232 Exibições
-
Última msg por JotaV
-
- 1 Respostas
- 771 Exibições
-
Última msg por MateusQqMD
-
- 1 Respostas
- 3854 Exibições
-
Última msg por deOliveira
-
- 1 Respostas
- 600 Exibições
-
Última msg por eivitordias
