(Aritmética: Sistema de numeração na base 2 – base binária – um critério de divisibilidade por 7)
Seja [tex]n=a_k\,a_{k-1}\,\ldots\,a_1\,a_0[/tex] um número natural não-nulo escrito na base 2, formado por k+1 algarismos, com k ≥ 3,
sendo [tex]a_k=1[/tex] e [tex]a_i\in\{0,\,1\},[/tex] para todo [tex]i\in\{0,\,1,\,\ldots,\,k-1\}.[/tex]
Considere [tex]m=(a_k\,a_{k-1}\, \ldots\,a_3)+(a_2\,a_1\,a_0).[/tex]
a) Mostre que se [tex]m\equiv r~~\mathrm{(mod~}7),[/tex] então [tex]n\equiv r~~\mathrm{(mod~}7).[/tex]
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.
Seja [tex]n=a_k\,a_{k-1}\,\ldots\,a_1\,a_0[/tex] um número natural não-nulo escrito na base 2, formado por k+1 algarismos, com k ≥ 3,
sendo [tex]a_k=1[/tex] e [tex]a_i\in\{0,\,1\},[/tex] para todo [tex]i\in\{0,\,1,\,\ldots,\,k-1\}.[/tex]
Considere [tex]m=(a_k\,a_{k-1}\, \ldots\,a_3)+(a_2\,a_1\,a_0).[/tex]
a) Mostre que se [tex]m\equiv r~~\mathrm{(mod~}7),[/tex] então [tex]n\equiv r~~\mathrm{(mod~}7).[/tex]
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.
More Questions From This User See All
Lista de comentários
Verified answer
Designemos de q a seguinte sequência de algarismos:
[tex]q = a_k\:a_{k-1}\:...\:a_4\:a_3[/tex]
Desse modo:
[tex]m = q + (a_2\:a_1\:a_0)[/tex]
Perceba que n tem 3 algarismos a mais que m, desconsiderando a soma [tex](a_2\:a_1\:a_0)[/tex] de m . Desse modo, também desconsiderando a soma, n é [tex]2^3 = 8[/tex] vezes maior que m. Portanto, agora considerando a soma, n pode ser escrito como:
[tex]n = 8q + (a_2\:a_1\:a_0)[/tex]
a)
[tex]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[/tex]
b) Como a cada execução do algoritmo o resto se mantém, se pode deduzir o seguinte:
[tex]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[/tex]