(Aritmética: Sistema de numeração na base 2 – base binária – um critério de divisibilidade 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 dígitos (também chamados bits), com k ≥ 1,
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_1)+3\cdot a_0.[/tex] Mostre que
a) Se [tex]m[/tex] é múltiplo de 5, então [tex]n[/tex] é múltiplo de 5.
b) Se [tex]m\equiv r~~\mathrm{(mod~}5),[/tex] então [tex]n\equiv 2r~~\mathrm{(mod~}5).[/tex]
─────
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).
Designemos o número dado pela seguinte sequência de caracteres de "q": [tex]q = a_k\: a_{k-1}\: ... \:a_1[/tex]
Portanto: [tex]n = 2q + a_0[/tex] Já que, ao duplicar q, estamos essencialmente colocando um [tex]a'_{0} = 0[/tex] no final. Logo, somamos a [tex]a_0[/tex], para dar um valor a esta unidade binária recém adicionada.
Lista de comentários
Verified answer
Designemos o número dado pela seguinte sequência de caracteres de "q":
[tex]q = a_k\: a_{k-1}\: ... \:a_1[/tex]
Portanto:
[tex]n = 2q + a_0[/tex]
Já que, ao duplicar q, estamos essencialmente colocando um [tex]a'_{0} = 0[/tex] no final. Logo, somamos a [tex]a_0[/tex], para dar um valor a esta unidade binária recém adicionada.
Com esse mesmo critério:
[tex]m = q + 3a_0[/tex]
a)
[tex]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[/tex]
b)
[tex]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\\[/tex]