Olimpíadas(OCM - 1994) Divisibilidade Tópico resolvido

Aqui devem ser postados problemas Olímpicos. Informe a olimpíada e o ano no título do tópico. Exemplo: (OBM - 2008).

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
Winston
sênior
Mensagens: 28
Registrado em: Qui 30 Nov, 2017 11:32
Última visita: 23-02-21
Dez 2017 04 09:55

(OCM - 1994) Divisibilidade

Mensagem não lida por Winston »

Seja A = 777...77 um número onde o dígito 7 aparece 1001 vezes. Determinar o quociente e o resto da divisão de A por 1001.




alevini98
3 - Destaque
Mensagens: 422
Registrado em: Sex 21 Jul, 2017 16:23
Última visita: 12-07-20
Dez 2017 04 12:09

Re: (OCM - 1994) Divisibilidade

Mensagem não lida por alevini98 »

Representando as maiores casas de 777...77, repare que, dividindo por 7007, já que é um múltiplo de 1001, iremos multiplicando esse número por [tex3]10^n[/tex3] até chegar num valor bem próximo de 777...77.

As maiores casas ficariam,

70070000....000

Preenchendo novamente, mas uma casa a menos, ficaria,

770770000...000

De novo,

77777700000...000

Perceba que conseguimos preencher completamente 6 casas com o número 7. Caso fôssemos fazer o mesmo novamente ficaria:

777777777777000...000

Agora, dividindo 1001 por 6 para ver até onde conseguimos completar esse ciclo comseguiremos um resto 5.

Sabendo disso, as casas finais do número que estávamos montando ficaria da seguinte forma:

77777...777700000

Inserindo 7007, nosso múltiplo de 1001,

777...7770070

Mais uma vez,

777...7777077

Sabendo que 777...7777070 é múltiplo de 1001, iremos subtraí-lo de 777...77,

[tex3]777...777777-777...7777077=700[/tex3]

[tex3]\boxed{R=700}[/tex3]

Me atrapalhei na última casa, ao invés de um sete coloquei um zero. :oops:

Última edição: alevini98 (Seg 04 Dez, 2017 16:23). Total de 1 vez.



Avatar do usuário
Ittalo25
5 - Mestre
Mensagens: 2349
Registrado em: Seg 18 Nov, 2013 22:11
Última visita: 27-03-24
Dez 2017 04 16:01

Re: (OCM - 1994) Divisibilidade

Mensagem não lida por Ittalo25 »

[tex3]A = 7 \cdot \frac{(10^{1001}-1)}{9}[/tex3]

[tex3]1001 = 10^3+1[/tex3]

Então a ideia é achar alguma fatoração envolvendo esses 2 números. Sabendo que [tex3]\frac{10^{999}+1}{10^3+1}[/tex3] é inteiro:

[tex3]100 \cdot \frac{(10^{999}+1)}{10^3+1} - \frac{101}{10^3+1} = \frac{10^{1001}-1 }{10^3+1}[/tex3]

[tex3]100 \cdot \frac{(10^{999}+1)}{10^3+1} - \frac{1001-900}{10^3+1} = \frac{10^{1001}-1 }{10^3+1}[/tex3]

[tex3]100 \cdot \frac{(10^{999}+1)}{10^3+1} -1 + \frac{900}{10^3+1} = \frac{10^{1001}-1 }{10^3+1}[/tex3]

[tex3]\frac{10^{1001}-901}{10^3+1} + \frac{900}{10^3+1} = \frac{10^{1001}-1 }{10^3+1}[/tex3]

[tex3]\frac{10^{1001}-901}{9(10^3+1)} + \frac{100}{10^3+1} = \frac{10^{1001}-1 }{9(10^3+1)}[/tex3]

[tex3]\frac{7 \cdot (10^{1001}-901)}{9(10^3+1)} + \frac{700}{10^3+1} = \frac{7\cdot (10^{1001}-1) }{9(10^3+1)}[/tex3]

Agora é preciso ver se [tex3]\frac{7 \cdot (10^{1001}-901)}{9\cdot 1001} = \frac{10^{1001}-901}{9\cdot 11 \cdot 13} [/tex3] é inteiro

[tex3]\begin{cases}
901 \equiv 4 \mod(13) \\
901 \equiv 10 \mod(11)
\end{cases}[/tex3]

Pelo pequeno teorema de Fermat:

[tex3]10^{12} \equiv 1 \mod(13)[/tex3]
[tex3]10^{996} \equiv 1 \mod(13)[/tex3]
[tex3]10^{1001} \equiv 10^5 \mod(13)[/tex3]
[tex3]10^{1001} \equiv 4 \mod(13)[/tex3]

Pelo pequeno teorema de Fermat:

[tex3]10^{10} \equiv 1 \mod(11)[/tex3]
[tex3]10^{1000} \equiv 1 \mod(11)[/tex3]
[tex3]10^{1001} \equiv 10 \mod(11)[/tex3]

Também:

[tex3]10^{1001} - 901 \equiv 1^{1001} - 900 - 1 \equiv 0 \mod(9) [/tex3]

Portanto:

Quociente: [tex3]\boxed {\frac{7 \cdot (10^{1001}-901)}{9(10^3+1)}} [/tex3]

Resto: [tex3]\boxed {700} [/tex3]



Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg
  • Nova mensagem (OCM) Equações e funções logarítmicas
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    844 Exibições
    Última msg por undefinied3
  • Nova mensagem (OCM) Geometria Espacial: Poliedros
    por Deleted User 23699 » » em Olimpíadas
    0 Respostas
    678 Exibições
    Última msg por Deleted User 23699
  • Nova mensagem (OCM) Geometria Espacial: Pirâmides
    por Deleted User 23699 » » em Olimpíadas
    0 Respostas
    687 Exibições
    Última msg por Deleted User 23699
  • Nova mensagem (OCM) Geometria Espacial: Cones
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    933 Exibições
    Última msg por παθμ
  • Nova mensagem (OCM) Geometria Espacial: Esferas
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    916 Exibições
    Última msg por joaopcarv

Voltar para “Olimpíadas”