(Aritmética: Sistema de numeração na base 2 – base binária – um critério de divisibilidade por 3 e por 5)
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 ≥ 4,
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_4)+(a_3\,a_2\,a_1\,a_0).[/tex] Mostre que
a) Se [tex]m\equiv r~~\mathrm{(mod~}3),[/tex] então [tex]n\equiv r~~\mathrm{(mod~}3).[/tex]
b) Se [tex]m\equiv r~~\mathrm{(mod~}5),[/tex] então [tex]n\equiv r~~\mathrm{(mod~}5).[/tex]
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.
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 ≥ 4,
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_4)+(a_3\,a_2\,a_1\,a_0).[/tex] Mostre que
a) Se [tex]m\equiv r~~\mathrm{(mod~}3),[/tex] então [tex]n\equiv r~~\mathrm{(mod~}3).[/tex]
b) Se [tex]m\equiv r~~\mathrm{(mod~}5),[/tex] então [tex]n\equiv r~~\mathrm{(mod~}5).[/tex]
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.
More Questions From This User See All
Lista de comentários
Verified answer
Designemos de "q" a sequência de caracteres formada por:
[tex]q = a_k \: a_{k-1} \: ... \: a_5 \: a_4[/tex]
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 é [tex]2^4 = 16[/tex] vezes maior que m. Como m pode ser escrito como [tex]q + (a_3\:a_2\:a_1\:a_0)[/tex], temos que [tex]n = 16q + (a_3\:a_2\:a_1\:a_0)[/tex].
[tex]m = q + (a_3\:a_2\:a_1\:a_0)\\n = 16q + (a_3\:a_2\:a_1\:a_0)[/tex]
a)
[tex]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[/tex]
b)
[tex]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[/tex]
c)
Primeira execução do algoritmo (mod 3):
[tex]n = 1101001101001_2\\n = 16(110100110_2) + 1001_2\\m = 110100110_2 + 1001_2\\m = 110101111_2[/tex]
[tex]n \equiv m \pmod 3\\1101001101001_2 \equiv 110101111_2 \pmod 3[/tex]
Segunda execução:
[tex]110101111_2 = 16(11010_2) + 1111_2[/tex]
[tex]110101111_2 \equiv 11010_2 + 1111_2 \pmod 3\\110101111_2 \equiv 101001_2 \pmod 3[/tex]
Terceira execução:
[tex]101001_2 = 16(10_2) + 1001_2[/tex]
[tex]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[/tex]
[tex]1101001101001_2 \equiv 2 \pmod 3\\1101001101001_2 \equiv 10_2 \pmod 3[/tex]
O algoritmo para mod 5 se dá do mesmo modo como se deu com mod 3, exceto na simplificação próxima ao final:
[tex]101001_2 \equiv 1011_2 \pmod 5\\101001_2 \equiv 11 \pmod 5\\101001_2 \equiv 1 \pmod 5[/tex]
[tex]1101001101001_2 \equiv 1 \pmod 5\\1101001101001_2 \equiv 1_2 \pmod 5[/tex]
m = q + r
n = 32q + r
?