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

[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]

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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

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

[Ittalo25]

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

Pelo pequeno teorema de Fermat:

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

Também:

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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

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

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

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