Question

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

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 ≥ 3,

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_3)+(a_2\,a_1\,a_0).$

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

b) Utilizando este algotimo, calcule o resto da divisão de 1101001101001₂ por 7.

─────

Dica: Reescreva n na forma 8q + r.

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

Answer 1

Designemos de q a seguinte sequência de algarismos:
$q = a_k\:a_{k-1}\:...\:a_4\:a_3$

Desse modo:
$m = q + (a_2\:a_1\:a_0)$

Perceba que n tem 3 algarismos a mais que m, desconsiderando a soma $(a_2\:a_1\:a_0)$ de m . Desse modo, também desconsiderando a soma, n é $2^3 = 8$ vezes maior que m. Portanto, agora considerando a soma, n pode ser escrito como:
$n = 8q + (a_2\:a_1\:a_0)$

a)
$m \equiv r \pmod 7\\q + (a_2\:a_1\:a_0)\equiv r \pmod 7\\8(q + (a_2\:a_1\:a_0))\equiv 8r \pmod 7\\8q + 8(a_2\:a_1\:a_0)\equiv 8r \pmod 7\\8q + 7(a_2\:a_1\:a_0) + (a_2\:a_1\:a_0)\equiv 7r + r \pmod 7\\8q + (a_2\:a_1\:a_0)\equiv r \pmod 7\\n \equiv r \pmod 7$

b) Como a cada execução do algoritmo o resto se mantém, se pode deduzir o seguinte:

$1101001101001_2\\\equiv 1101001101_2 + 1_2\\\equiv (1101001_2 + 101_2) + 1_2\\\equiv ((1101_2 + 1_2) + 101_2) + 1_2\\\equiv (((1_2 + 101_2) + 1_2) + 101_2) + 1_2\\\equiv 1 + 5 + 1 + 5 + 1\\\equiv 13\\\equiv 7 + 6\\\equiv 6 \pmod 7$