Question

(Aritmética: Um critério de divisibilidade por 37 – sistema de numeração decimal – base 10)

Seja $n=d_k\,d_{k-1}\,\ldots\,d_2\,d_1\,d_0$ um número natural não-nulo formado por k+1 algarismos, com k ≥ 3,

sendo $d_k\ne 0$ e $d_i\in\{0,\,1,\,\ldots,\,9\}$ para todo $i\in\{0,\,1,\,\ldots,\,k-1\}.$

Considere $m=(d_k\,d_{k-1}\,\ldots\,d_3)+(d_2\,d_1\,d_0).$

a) Mostre que se $m\equiv r~~\mathrm{(mod~}37),$ então $n\equiv r~~\mathrm{(mod~}37),$

b) Utilizando este algoritmo, calcule o resto da divisão de 237223478 por 37.

─────

Dica: Reescreva n na forma 1000q + r.​

Answer 1

Seja q o número dado pelos primeiros (k-2) algarismos de n (ou seja, descartando os últimos 3):
$q = d_k\:d_{k-1}\:...\:d_4\:d_3$

Então:
$m = q + (d_2\:d_1\:d_0)$

Como q, por definição, é 3 algarismos menor que n, temos que n é $10^3 = 1000$ vezes maior que q. Desse modo:
$n = 1000q + (d_2\:d_1\:d_0)$

a)

$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}$

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:

$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}$