Question

(Aritmética: Sistema de numeração na base 2 – base binária – um 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 ≥ 1,

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_1)+3\cdot 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 2r~~\mathrm{(mod~}5).$

─────

Dica: Reescreva n na forma 2q + r.

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

Answer 1

Designemos o número dado pela seguinte sequência de caracteres de "q":
$q = a_k\: a_{k-1}\: ... \:a_1$

Portanto:
$n = 2q + a_0$
Já que, ao duplicar q, estamos essencialmente colocando um $a'_{0} = 0$ no final. Logo, somamos a $a_0$, para dar um valor a esta unidade binária recém adicionada.

Com esse mesmo critério:
$m = q + 3a_0$

a)
$m \equiv 0 \pmod 5\\q + 3a_0\equiv 0 \pmod 5\\2(q + 3a_0)\equiv 2 \cdot 0 \pmod 5\\2q + 6a_0\equiv 0 \pmod 5\\2q + 5a_0 + a_0 \equiv 0 \pmod 5\\2q + a_0 \equiv 0\pmod 5\\n \equiv 0 \pmod 5$

b)

$m \equiv r \pmod 5\\q + 3a_0 \equiv r \pmod 5\\2(q + 3a_0)\equiv 2r \pmod 5\\2q + 6 a_0 \equiv 2r \pmod 5\\2q + 5 a_0 + a_0 \equiv 2r \pmod 5\\2q + a_0 \equiv 2r \pmod 5\\n \equiv 2r \pmod 5$