Question

(Aritmética: Sistema de numeração na base 2 – base binária – outro critério de divisibilidade por 5)

Seja $n=a_k\,a_{k-1}\,\ldots\,a_1\,a_0$ um número natural não-nulo escrito na base 2, formado por k+1 dígitos (também chamados bits), com k ≥ 2,

sendo $a_k=1$ e $a_i\in\{0,\,1\},$ para todo $i\in\{0,\,1,\,\ldots,\,k-1\}.$

Considere $m=(a_k\,a_{k-1}\,\ldots\,a_2)-(a_1\,a_0).$ Mostre que

a) Se $m$ é múltiplo de 5, então $n$ é múltiplo de 5.

b) Se $m\equiv r~~\mathrm{(mod~}5),$ então $n\equiv 4r\equiv - r~~\mathrm{(mod~}5).$

─────

Dica: Reescreva n na forma 4q + r.

Obs.: No enunciado desta tarefa, considere os naturais 2, 4 e 5 como escritos no sistema de numeração decimal (base 10).​​

Answer 1

Sendo q a sequência de algarismos a seguir:
$q = a_k\:a_{k-1}\:...\:a_3\:a_2$

Como n tem 2 algarismos a mais que m, logo a parte q de n é $2^2 = 4$ vezes maior que a parte q de m. Com isso já definido e somente ajustando o restante do número ($a_1$ e $a_0$), se pode afirmar que:

$m = q - (a_1\: a_0)\\n = 4q + (a_1\: a_0)$

a)

$m \equiv 0 \pmod 5\\q - (a_1\: a_0) \equiv 0 \pmod 5\\4(q - (a_1\: a_0))\equiv 4 \cdot 0 \pmod 5\\4q - 4(a_1\: a_0) \equiv 0 \pmod 5\\4q - 4(a_1\: a_0) + 5(a_1\: a_0)\equiv 0 \pmod 5\\4q + (a_1\: a_0)\equiv 0 \pmod 5\\n \equiv 0 \pmod 5$

b)

$m \equiv r \pmod 5\\q - (a_1\:a_0) \equiv r \pmod 5\\4(q - (a_1\:a_0)) \equiv 4r \pmod 5\\4q - 4(a_1\:a_0) \equiv 4r \pmod 5\\4q - 4(a_1\:a_0) + 5(a_1\:a_0) \equiv 4r -5r \pmod 5\\4q + (a_1\:a_0) \equiv -r \pmod 5\\n \equiv -r \pmod 5$