Question

(Aritmética: Sistema de numeração na base 2 – base binária – um critério de divisibilidade por 3 e 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 algarismos, com k ≥ 4,

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_4)+(a_3\,a_2\,a_1\,a_0).$ Mostre que

a) Se $m\equiv r~~\mathrm{(mod~}3),$ então $n\equiv r~~\mathrm{(mod~}3).$

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

c) Utilizando este algotimo, calcule o resto da divisão de 1101001101001₂ por 3 e por 5.

─────

Dica: Reescreva n na forma 16q + r.

Obs.: O ₂ subscrito após o número indica que este está escrito na base 2.​

Answer 1

Designemos de "q" a sequência de caracteres formada por:
$q = a_k \: a_{k-1} \: ... \: a_5 \: a_4$

Vemos que m tem tantos algarismos quanto q, enquanto n tem 4 algarismos a mais que q. Como estes algarismos são da base binária, desconsiderando a soma de m, n é $2^4 = 16$ vezes maior que m. Como m pode ser escrito como $q + (a_3\:a_2\:a_1\:a_0)$, temos que $n = 16q + (a_3\:a_2\:a_1\:a_0)$.

$m = q + (a_3\:a_2\:a_1\:a_0)\\n = 16q + (a_3\:a_2\:a_1\:a_0)$

a)

$m \equiv r \pmod 3\\q + (a_3\:a_2\:a_1\:a_0)\equiv r \pmod 3\\16 (q + (a_3\:a_2\:a_1\:a_0))\equiv 16r \pmod 3\\16 q + 16(a_3\:a_2\:a_1\:a_0) \equiv 16r \pmod 3\\16q + 3 \cdot 5(a_3\:a_2\:a_1\:a_0) + (a_3\:a_2\:a_1\:a_0)\equiv 3 \cdot 5r + r\pmod 3\\16q + (a_3\:a_2\:a_1\:a_0) \equiv r \pmod 3\\n \equiv r \pmod 3$

b)

$m \equiv r \pmod 5\\q + (a_3\:a_2\:a_1\:a_0)\equiv r \pmod 5\\16 (q + (a_3\:a_2\:a_1\:a_0))\equiv 16r \pmod 5\\16 q + 16(a_3\:a_2\:a_1\:a_0) \equiv 16r \pmod 5\\16q + 5 \cdot 3(a_3\:a_2\:a_1\:a_0) + (a_3\:a_2\:a_1\:a_0)\equiv 5 \cdot 3r + r\pmod 5\\16q + (a_3\:a_2\:a_1\:a_0) \equiv r \pmod 5\\n \equiv r \pmod 5$

c)

Primeira execução do algoritmo (mod 3):

$n = 1101001101001_2\\n = 16(110100110_2) + 1001_2\\m = 110100110_2 + 1001_2\\m = 110101111_2$

$n \equiv m \pmod 3\\1101001101001_2 \equiv 110101111_2 \pmod 3$

Segunda execução:

$110101111_2 = 16(11010_2) + 1111_2$

$110101111_2 \equiv 11010_2 + 1111_2 \pmod 3\\110101111_2 \equiv 101001_2 \pmod 3$

Terceira execução:

$101001_2 = 16(10_2) + 1001_2$

$101001_2 \equiv 10_2 + 1001_2 \pmod 3\\101001_2 \equiv 1011_2 \pmod 3\\101001_2 \equiv 11 \pmod 3\\101001_2 \equiv 2 \pmod 3$

$1101001101001_2 \equiv 2 \pmod 3\\1101001101001_2 \equiv 10_2 \pmod 3$

O algoritmo para mod 5 se dá do mesmo modo como se deu com mod 3, exceto na simplificação próxima ao final:

$101001_2 \equiv 1011_2 \pmod 5\\101001_2 \equiv 11 \pmod 5\\101001_2 \equiv 1 \pmod 5$

$1101001101001_2 \equiv 1 \pmod 5\\1101001101001_2 \equiv 1_2 \pmod 5$