(Aritmética: Um critério de divisibilidade por 37 – sistema de numeração decimal – base 10)
Seja [tex]n=d_k\,d_{k-1}\,\ldots\,d_2\,d_1\,d_0[/tex] um número natural não-nulo formado por k+1 algarismos, com k ≥ 3,
sendo [tex]d_k\ne 0[/tex] e [tex]d_i\in\{0,\,1,\,\ldots,\,9\}[/tex] para todo [tex]i\in\{0,\,1,\,\ldots,\,k-1\}.[/tex]
Considere [tex]m=(d_k\,d_{k-1}\,\ldots\,d_3)+(d_2\,d_1\,d_0).[/tex]
a) Mostre que se [tex]m\equiv r~~\mathrm{(mod~}37),[/tex] então [tex]n\equiv r~~\mathrm{(mod~}37),[/tex]
b) Utilizando este algoritmo, calcule o resto da divisão de 237223478 por 37.
─────
Dica: Reescreva n na forma 1000q + r.
Lista de comentários
Verified answer
Seja q o número dado pelos primeiros (k-2) algarismos de n (ou seja, descartando os últimos 3):
[tex]q = d_k\:d_{k-1}\:...\:d_4\:d_3[/tex]
Então:
[tex]m = q + (d_2\:d_1\:d_0)[/tex]
Como q, por definição, é 3 algarismos menor que n, temos que n é [tex]10^3 = 1000[/tex] vezes maior que q. Desse modo:
[tex]n = 1000q + (d_2\:d_1\:d_0)[/tex]
a)
[tex]m \equiv r \pmod {37}\\q + (d_2\:d_1\:d_0) \equiv r \pmod {37}\\1000(q + (d_2\:d_1\:d_0)) \equiv 1000r \pmod {37}\\1000q + 1000(d_2\:d_1\:d_0) \equiv 1000r \pmod {37}\\1000q + 37 \cdot 27(d_2\:d_1\:d_0) + (d_2\:d_1\:d_0) \equiv 37 \cdot 27r + r \pmod {37}\\1000q + (d_2\:d_1\:d_0) \equiv r \pmod {37}\\n \equiv r \pmod {37}[/tex]
b) Como, neste algoritmo, o resto se mantém durante as execuções, podemos reescrever cada termo da primeira execução como outras execuções, consecutivamente, mantendo o resto original. Demonstração prática:
[tex]237223478\\\equiv 237223 + 478\\\equiv 237 + 223 + 478\\\equiv (37 \cdot 6 + 15) + (37 \cdot 6 + 1) + (37 \cdot 12 + 34)\\\equiv 15 + 1 + 34\\\equiv 50\\\equiv 37 + 13\\\equiv 13 \pmod {37}[/tex]