Guia de problemas matemáticos/Teoria dos números/Divisibilidade por 16

O problema

Justapondo-se os números naturais conforme a representação abaixo, onde o sinal * indica o último algarismo, forma-se um número de 1002 algarismos. Então calcule o resto da divisão desse número por 16.

$N=123456789101112131415161718192021....*$

Uma solução

Para resolver esse problema, precisamos conhecer uma pequena regra de divisibilidade:

"Um número é divisível por $2^n$ quando seus n últimos algarismos forem iguais a 0, ou divisíveis por $2^n$.

Em outras palavras, a divisão de um número qualquer por $2^n$ depende dos n últimos algarismos desse número.

Então, para solucionarmos nosso problema, precisamos conhecer os 4 últimos algarimos do número formado (pois 16 = $2^4$). Como o processo de formação desse número é relativamente simples, não será complicado descobrir os 4 últimos algarismos desse número.

Pelo que o enunciado já nos informou, podemos obter os últimos algarismos do número formado da seguinte maneira:

De 1 a 9, teremos 9 números de 1 algarismo, portanto 9 algarismos. De 10 a 99 teremos 90 números de 2 algarismos, portanto 180 algarismos. Somando os algarismos, obtemos 189. Se o número formado terá 1002 algarismos, temos que restam 813 algarismos (1002 - 189). Percebamos, então, que todos esses 813 algarismos serão ocupados por números naturais de três algarismos. Assim sendo, ainda restam 271 números (813 : 3) de três algarismos para serem justapostos. Vamos então elaborar um pequeno esquema, que nos fornecerá os últimos algarismos do número formado:

$100\to 200\Rightarrow 101n\acute{u}meros$

$201\to 300\Rightarrow 100n\acute{u}meros$

$301\to 370\Rightarrow 70n\acute{u}meros$

Logo, o número formado será:

$N=123456789101112...368369370$

Pelo critério de divisibilidade por 16 mencionado inicialmente, o resto da divisão desse número por 16 será igual ao resto da divisão de 9370 por 16. Portanto:

$N\equiv 9370(mod16)$

Como 9370 : 16 deixa resto 10, o resto da divisão de N por 16 nos dará resto 10.

E o problema termina.

Caso você tenha uma outra solução, sinta-se livre para editar o artigo, apenas utilize a aba "Discussão" para discutir as soluções antes de alterar o tópico. Sinta-se livre também para comentar, criticar ou sugerir qualquer coisa.

Agradecimentos

• A Ângelo Alberto de Castro Almeida, que me enviou esse e outros vários problemas do CACN, juntamente com suas soluções, colaborando para o desenvolvimento do Guia.