Olimpíadas ⇒ (OCM - 1994) Divisibilidade Tópico resolvido
Moderador: [ Moderadores TTB ]
Dez 2017
04
09:55
(OCM - 1994) Divisibilidade
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.
Dez 2017
04
12:09
Re: (OCM - 1994) Divisibilidade
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]
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.
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.
Última edição: alevini98 (Seg 04 Dez, 2017 16:23). Total de 1 vez.
Dez 2017
04
16:01
Re: (OCM - 1994) Divisibilidade
[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]
[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]
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg