¿Cómo puedo saber si un número en base 5 es divisible por 3?

Question

Conozco el sum of digits divisible by 3 método, pero parece no estar funcionando para base 5.

¿Cómo puedo verificar si el número en base 5 es divisible por 3 sin convertirlo a la base 10 (o 3, para el caso)?

Answer 1

Reglas de divisibilidad por lo general se basan en el resto de los pesos de los dígitos de tener una cierta regularidad. El método estándar para la divisibilidad por $3$ en el sistema decimal funciona porque los pesos de todos los dígitos hayan resto $1$ modulo $3$. Lo mismo es cierto para $9$. Para $11$, las cosas son sólo un poco más complicado: Desde impar de dígitos resto $1$, e incluso dígitos resto $-1$, usted necesita tomar la alternancia de suma de dígitos para la prueba de divisibilidad por $11$.

En base a $5$, tenemos la misma situación para $3$ como para $11$ base $10$: El resto de los pesos de los dígitos impares es $1$ y la de los dígitos es $-1$. Por lo que puede comprobar la divisibilidad por $3$ tomando la alternancia de suma de los dígitos.

De manera más general, en base a $b$ la suma de los dígitos de las obras de los divisores de a $b-1$ y en la alternancia de la suma de los dígitos de las obras de los divisores de a $b+1$.

Answer 2

Añadir los dígitos, pero las cifras incluso se multiplican por 2.

Esto funciona porque $5 \equiv 2 \mod 3$, $5^2 \equiv 1 \mod 3$, etc..

Answer 3

$n=(d_m \cdots d_0)_5$ $n$ Es divisible por $3$ % iff $d_0-d_1+d_2-d_3+\cdots$es divisible por $3$.

Esto sigue de $5^k \equiv 1 \bmod 3$ si es $k$ y $5^k \equiv -1 \bmod 3$ si $k$ es impar.

Answer 4

Sugerencia $ $ Radix notación Polinómica forma$\,n = d_0\! + d_1 5 + d_2 5^2\! +\cdots + d_k 5^k\! = P(5)\,$, por lo que

${\rm mod}\ 3\!:\ \color{#c00}5\equiv \color{#c00}{-1}\,\Rightarrow\ n = P(\color{#c00}5) \equiv P(\color{#c00}{-1}) \equiv d_0 - d_1 + d_2 - \cdots + (-1)^k d_k\, $ aplicando el Polinomio de la Congruencia de la Regla, es decir,$\,a\equiv b\,\Rightarrow\,P(a)\equiv P(b)$.

Comentario $\ $ Esta es esencialmente la misma regla para la fundición $11$s en notación decimal, es decir, calcular la alternancia de suma de los dígitos del modulo el radix. Claramente el mismo método funciona siempre que el radix $\equiv -1$ módulo del divisor.

Ideas similares abordar grado más alto de los casos, por ejemplo, expulsar $91 = 10^2\!-10+1$ trabaja como esto:

$$x^2 \equiv x-1\ \Rightarrow\ x^3 \equiv -1,\,\ x^4 \equiv -x,\,\ x^5 \equiv 1-x,\,\ x^6 = 1 \pmod{x^2 - x + 1}$$

Por lo tanto $\ d := d_0 + d_1 x + d_2 x^2 + d_3 x^3 + d_4 x^4 + d_5 x^5 + d_6 x^6$

$\qquad\quad\ \equiv d_0-d_2-d_3+d_5+d_6 + (d_1+d_2-d_4-d_5)\, x\,\ \pmod{x^2 - x + 1}$

E. g. para $\, x=10\ $ el módulo es $\,x^2-x+1 = 91\,$, por lo que tenemos

$$ d=6543210 \equiv 0\! -\!2\! \!-3\! +\!5\!+\!6 + (1\! +\!2\! -\!4\! -\!5) 10 \equiv 6-60 \equiv \color{#0a0}{37}\! \pmod{\!91}$$

Y, de hecho, $\ 6543210 = \color{#0a0}{37} + 91 \cdot 71903.$

Answer 5

Voy a tomar la carretera baja aquí y responder a la pregunta exacta que se le preguntó: usted puede decir si un número en base 5 es divisible por 3 sin convertirlo a la base 10 (o 3) dividir por 3 y examinando el resto. Decir lo obvio por lo completo, el número es divisible por 3 iff el resto es cero.

Esto es equivalente a calcular el último dígito de su base representación 3.