Reglas de divisibilidad en el sistema binario

Question

Así, durante el estudio de las congruencias y la divisibilidad me encontré con las reglas de divisibilidad habituales para el sistema decimal. Sin embargo, como ejercicio recibí las siguientes afirmaciones que tengo que demostrar en el sistema binario, es decir, ahora un número natural $n$ se representa como $n = \sum_{k=0}^{2m} b_k2^k, b_i \in \mathbb{N}, m \in \mathbb{N}$ . Con ellos me cuesta bastante, ya que parece que aún no he comprendido del todo el concepto de aritmética modular.

El ejercicio consiste en demostrar que

i) $3 | n \Leftrightarrow 3|\sum_{k=0}^{2m} b_k(-1)^k \Leftrightarrow 3|\sum_{k=0}^{m} b_{2k} + 2b_{2k+1}$

ii) $5|n \Leftrightarrow 5|\sum_{k=0}^{m} (b_{2k} + 2b_{2k+1})(-1)^k$

Además, tengo que encontrar una regla para la divisivilidad por 7. Como no sé cómo hacer para demostrar lo anterior, estoy aún más perdido encontrando una regla.

Answer 1

Pista. Tenga en cuenta que $2\equiv -1\pmod{3}$ y $4\equiv -1\pmod{5}$ . Por lo tanto $$n = \sum_{k=0}^{2m} b_k2^k\equiv \sum_{k=0}^{2m} b_k(-1)^k \pmod{3}$$ y $$n = \sum_{k=0}^{2m+1} b_k2^k=\sum_{k=0}^{m} b_{2k}2^{2k}+\sum_{k=0}^{m} b_{2k+1}2^{2k+1}\equiv \sum_{k=0}^{m} b_{2k}(-1)^{k} +\sum_{k=0}^{m} b_{2k+1}2\cdot(-1)^{k} \pmod{5}.$$ ¿Puedes seguir desde aquí?

Answer 2

Observa que ambas sumas descomponen el número en pares de dígitos binarios: estás sumando (o alternativamente sumando y restando) las cantidades $b_{2k}+2b_{2k+1}$ . Veamos un ejemplo concreto $1101001011$ .

$$\begin{array}{rcc} k:&4&3&2&1&0\\ b_{2k+1}b_{2k}:&11&01&00&10&11\\ b_{2k}+2b_{2k+1}:&3&1&0&2&3 \end{array}$$

La prueba propuesta de divisibilidad por $3$ luego suma los números de la fila inferior para obtener $9$ que es divisible por $3$ y de hecho $1101001011_{\text{two}}=843=3\cdot281$ es divisible por $3$ .

De hecho, la fila inferior es sólo la base cuatro representación de $n$ :

$$\sum_{k=0}^{2m}b_k2^k=\sum_{k=0}^m(b_{2k}+2b_{2k+1})2^{2k}=\sum_{k=0}^m(b_{2k}+2b_{2k+1})4^k\;,$$

y cada $b_{2k}+2b_{2k+1}$ es $0,1,2$ o $3$ . Si se piensa en términos de la representación de base cuatro, esta prueba es igual que la prueba habitual de divisibilidad por $9$ de un número escrito en notación decimal ordinaria, y funciona por la misma razón: $3$ es $1$ menos que la base, al igual que $9$ es $1$ menos que nuestra base habitual de $4$ .

El resultado general es que si se escribe un número entero positivo en base $b$ ese número entero es divisible por $b-1$ si y sólo si la suma de sus dígitos es divisible por $b-1$ y, de forma más general, el número entero y la suma de sus dígitos son congruentes modulo $b-1$ .

Para verlo, veamos $n=\sum_{k=0}^md_kb^k$ donde cada $d_k\in\{0,1,\ldots,b-1\}$ . Claramente $b\equiv 1\pmod{b-1}$ Así que $b^k\equiv 1^k\pmod{b-1}$ y, por supuesto $1^k=1$ Así que

$$n=\sum_{k=0}^md_kb^k\equiv\sum_{k=0}^md_k\pmod{b-1}\;.$$

La prueba de divisibilidad por $5$ es similar, salvo que toma la suma alterna de los cuatro dígitos de base. Si conoce la prueba de divisibilidad por $11$ en nuestro sistema decimal ordinario, reconocerá esto como análogo, y de nuevo funciona de forma más general: un número entero escrito en base $b$ es congruente mod $b+1$ a la suma alternada de sus dígitos, y en particular es divisible por $b+1$ si y sólo si la suma alterna de sus dígitos es. De nuevo, el cálculo es sencillo: utilizamos el hecho de que $b\equiv-1\pmod{b+1}$ de modo que

$$\sum_{k=0}^md_kb^k\equiv\sum_{k=0}^md_k(-1)^k\pmod{b+1}\;.$$

En el presente caso $b$ es realmente $4$ aunque en realidad estemos trabajando con números escritos en binario: como se ha señalado anteriormente, utilizando los términos $b_{2k}+2b_{2k+1}$ es en efecto sólo convertir el número a base cuatro.

Para la parte final de la pregunta querrás una base diferente de $4$ pero seguirá siendo uno tal que la representación en esa base sea muy, muy fácilmente derivable de la representación binaria.

Answer 3

Sea $$n=\sum_{k\geq0} b_k2^k$$ con $b_k\in\{0,1\}$ . En $$2^k=(-1)^k\quad({\rm mod}\ 3),\qquad2^{2j}=(-1)^j\quad({\rm mod}\ 5),\qquad 2^{3j}=1\quad({\rm mod}\ 7)$$ se deduce que $$\eqalign{n&=\sum_{k\geq0}(-1)^kb_k\qquad({\rm mod}\ 3)\ ,\cr n&=\sum_{j\geq0}(b_{2j}+2b_{2j+1})(-1)^j\qquad({\rm mod}\ 5)\ ,\cr n&=\sum_{j\geq0}(b_{3j}+2b_{3j+1}+4b_{3j+2})\qquad({\rm mod}\ 7)\ .\cr}$$

Answer 4

Sugerencia $ $ Es inmediato descomponiendo $\,b(x) = \sum _k b_k x^k \,$ en incluso y impar piezas

$$\begin{align} b(x) &= b_0(x^2)+ x\, b_1(x^2)\\ \\ \Rightarrow\ \ {\rm mod}\ 3\!:\ b(2) &\equiv\ b_0(\color{#c00}1)\,+\,2\,b_1(\color{#c00}1)\quad\ \ \ {\rm by}\ \ \color{#c00}{2^2\,\equiv\, 1} \\ \\ \Rightarrow\ \ {\rm mod}\ 5\!:\ b(2)&\equiv b_0(\color{#0a0}{-1})+2\,b_1(\color{#0a0}{-1})\ \ {\rm by}\ \ \ \color{#0a0}{2^2\equiv -1} \end{align}$$

---

Observación $\ $ Resultados análogos se mantienen mod $\,d^2\pm1\,$ en radix $d\ $ utilizando $\,\color{#c00}{d^2\equiv \mp 1},\,$ por ejemplo, la consabida expulsión $\,99\,$ o $101$ en notación decimal. El uso de la aritmética modular facilita aún más la magia modular, como por ejemplo expulsión de noventa y uno utilizando $\ 91 = 10^2\!-10+1,\,$ Por ejemplo

$${\rm mod}\ 91\!:\,\ 6543210\, \equiv\, 0\! -\!2\! \!-3\! +\!5\!+\!6 + (1\! +\!2\! -\!4\! -\!5) 10\, \equiv\, 6\!-\!60\, \equiv\, {37}$$

Answer 5

Aunque la pregunta sobre 3 y 5 se refiere a números binarios, en realidad se trata de números en base 4. Cada dígito en base 4 está formado por 2 dígitos binarios. Por ejemplo, 19 es 10011 en binario. Para obtenerlo en base 4, añade un 0 delante para hacer un número par de dígitos binarios, luego agrupa los dígitos binarios en pares 01,00,11, lo que da 103 en base 4. Creo que la persona que planteó la pregunta ha metido la pata: el índice superior $2m$ debe ser $2m - 1$ para hacer un número par de dígitos binarios, y el índice superior $m$ debe ser $m-1$ . Las fórmulas de la pregunta se deducen porque las reglas de divisibilidad por 3 y 5 en base 4 son análogas a las reglas de divisibilidad por 9 y 11 en base 10. Para la divisibilidad por 7, supongo que se espera que dividas los dígitos binarios en grupos de tres y trabajes en base 8.