Olimpíadas ⇒ TEORIA DOS NUMEROS(resto da divisao por 13)

[rean]

Se [tex3]\underbrace{n=1000......00001}[/tex3] e tal que [tex3]n^3[/tex3] possui 2005 algarismos então o resto da divisão de n por 13 é.
.............[tex3]k....zeros[/tex3]

a)12 b)11 c)10 d)9 e)8

[Cássio]

Note que [tex3]n = 1\underbrace{000...00}_{k \ zeros}1 = 10^{k+1}+1.[/tex3]

Logo, [tex3]n^3 = (10^{k+1}+1)^3 = 10^{3k+3}+3\cdot10^{2k+2}+3\cdot10^{k+1}+1.[/tex3]

É fácil perceber que [tex3]10^{3k+3}+3\cdot10^{2k+2}+3\cdot10^{k+1}+1[/tex3] tem [tex3]3k+3+1[/tex3] algarismos. Pois [tex3]10^{3k+3}[/tex3] é o 1 seguido de [tex3]3k+3[/tex3] zeros e podemos afirmar que [tex3]3\cdot10^{2k+2}+3\cdot10^{k+1}+1[/tex3] não influenciará na quantidade de algarismos.

Daí que [tex3]n^3[/tex3] tem [tex3]2005[/tex3] algarismos, ou seja, [tex3]3k+3+1 = 2005\Longrightarrow \ k=667.[/tex3]

Portanto, [tex3]n = 10^{668}+1.[/tex3]

Como [tex3]10^{12}\equiv 1 \pmod{13}\Longrightarrow \ (10^{12})^{55}\equiv 1 \pmod{13}\Longrightarrow[/tex3]

[tex3]10^{660}\equiv 1 \pmod{13}\Longrightarrow10^{668}\equiv 10^4\cdot 10^4\equiv 3\cdot 3 \equiv 9\pmod{13}\Longrightarrow[/tex3]

[tex3]n = 10^{668}+1\equiv 10\pmod{13}.[/tex3]

Assim, o resto da divisão de [tex3]n[/tex3] por [tex3]13[/tex3] é [tex3]10.[/tex3]