How can I tell if a number in base 5 is divisible by 3?

Question

I know of the sum of digits divisible by 3 method, but it seems to not be working for base 5.

How can I check if number in base 5 is divisible by 3 without converting it to base 10 (or 3, for that matter)?

Answer 1

Divisibility rules generally rely on the remainders of the weights of digits having a certain regularity. The standard method for divisibility by $3$ in the decimal system works because the weights of all digits have remainder $1$ modulo $3$. The same is true for $9$. For $11$, things are only slightly more complicated: Since odd digits have remainder $1$ and even digits have remainder $-1$, you need to take the alternating sum of digits to test for divisibility by $11$.

In base $5$, we have the same situation for $3$ as we have for $11$ in base $10$: The remainder of the weights of odd digits is $1$ and that of even digits is $-1$. Thus you can check for divisibility by $3$ by taking the alternating sum of the digits.

More generally, in base $b$ the sum of digits works for the divisors of $b-1$ and the alternating sum of digits works for the divisors of $b+1$.

Answer 2

The $n=(d_m \cdots d_0)_5$ then $n$ is divisible by $3$ iff $d_0-d_1+d_2-d_3+\cdots$ is divisible by $3$.

This follows from $5^k \equiv 1 \bmod 3$ if $k$ is even and $5^k \equiv -1 \bmod 3$ if $k$ is odd.

Answer 3

Add the digits, but multiply the even digits by 2.

This works because $5 \equiv 2 \mod 3$, $5^2 \equiv 1 \mod 3$, etc.

Answer 4

Hint $ $ Radix notation has Polynomial form $\,n = d_0\! + d_1 5 + d_2 5^2\! +\cdots + d_k 5^k\! = P(5)\,$ so

${\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\, $ by applying the Polynomial Congruence Rule, i.e. $\,a\equiv b\,\Rightarrow\,P(a)\equiv P(b)$.

Remark $\ $ This is essentially the same rule for casting $11$ in decimal notation, i.e. compute the alternating sum of the digits modulo the radix. Clearly the same method works whenever the radix $\equiv -1$ modulo the divisor.

Similar ideas tackle higher degree cases, e.g. casting out $91 = 10^2\!-10+1$ works like this:

$$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}$$

Hence $\ 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. for $\, x=10\ $ the modulus is $\,x^2-x+1 = 91\,$ so we have

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

And indeed $\ 6543210 = \color{#0a0}{37} + 91 \cdot 71903.$