14
$\begingroup$

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)?

$\endgroup$
  • 2
    $\begingroup$ The sum of digits method is based on the fact that $3$ divides $10-1$. So on base $5$ you could apply this method in order to check divisibility by $2$ or by $4$, but not by $3$. $\endgroup$ – barak manos Jun 6 '16 at 18:57
  • $\begingroup$ @barakmanos Hrm. But isn't there some other way? $\endgroup$ – Akiiino Jun 6 '16 at 18:57
  • $\begingroup$ Dunno. For divisibility by $6$ on base $5$, you could use the same method used for divisibility by $11$ on base $10$. That should cover half of the cases. Not sure about the other half though... $\endgroup$ – barak manos Jun 6 '16 at 18:58
30
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ Another way of saying the same, since $5\equiv -1 \pmod{3}$: If we have a number (backwards) $a_0+a_1\cdot 5+a_2\cdot 5^2+a_3\cdot 5^3+\dots +a_n\cdot 5^n$ then that is congruent to $a_0+a_1\cdot (-1)+a_2\cdot (-1)^2+a_3\cdot (-1)^3+\dots +a_n\cdot (-1)^n = a_0-a_1+a_2-a_3+\dots +(-1)^na_n$, so you check divisibility by three by regarding the alternating sum of digits. $\endgroup$ – Jeppe Stig Nielsen Jun 6 '16 at 21:20
  • 2
    $\begingroup$ And while were at it: The “last $n$ digits” method works for divisors of $b^n$. $\endgroup$ – Hermann Döppes Jun 6 '16 at 22:01
8
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Equivalently, add the digits but negate the even-indexed ones, because $5\equiv -1\pmod{3}$. $\endgroup$ – jwodder Jun 6 '16 at 21:54
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$s 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.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.