0
$\begingroup$

This question already has an answer here:

How could we make the same division rules for other number systems, like in our decimal system: a number is divisible with 2 if it's last digit is 0,2,4,6,8, by 3 if the sum of digits is divisible with 3, and so on.

Can we do the same rules for g-based number systems too, where g is not 10, and greater than 1?

$\endgroup$

marked as duplicate by Daniel Fischer Jun 1 '15 at 12:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ See math.stackexchange.com/questions/328562/… $\endgroup$ – lab bhattacharjee Feb 25 '15 at 17:01
  • $\begingroup$ This you linked is an other question, I wanted to ask about division rules for other systems than decimal. :) $\endgroup$ – Atvin Feb 25 '15 at 17:03
  • $\begingroup$ If you understand my answer there, you should be able to generalize $\endgroup$ – lab bhattacharjee Feb 25 '15 at 17:04
  • 1
    $\begingroup$ You have the analogous last-digit tests for divisibility by divisors of $g$, and the analogous digit-sum tests for divisors of $g-1$. And the alternating digit-sum tests for divisors of $g+1$. $\endgroup$ – Daniel Fischer Feb 25 '15 at 17:05
  • $\begingroup$ Oh ok, thanks for your help! $\endgroup$ – Atvin Feb 25 '15 at 17:05
1
$\begingroup$

While there are motley divisibility tests derivable from $\,c\mid 10 a + b\iff c\mid ja+kb\,$ for small $\,j,k\,$ it is usually simpler and quicker to just use modular arithmetic (which, unlike said tests, has the benefit of computing the remainder, so may be used to check arithmetic, as in casting out nines).

This universal method amounts to evaluating a radix polynomial in nested Horner form, using modular arithmetic. For example, consider evaluating a $4$ digit radix $10$ number modulo $7$.

$$\begin{align} \rm\ d_3\ d_2\ d_1\ d_0 \rightarrow\ &\rm ((d_3\cdot 10 + d_2)\cdot 10 + d_1)\ 10 + d_0\\ \equiv\ &\rm (\color{#c00}{(d_3\cdot\ 3\ + d_2)}\cdot\ 3\ + d_1)\ \ 3\ + d_0\!\!\pmod{7}\end{align}\qquad$$

because $\rm\ 10\equiv 3\,\ (mod\,\ 7)\:.\:$ Thus we can compute the remainder $\rm\ (mod\ 7)\ $ by repeatedly replacing the two leading digits $\rm \,d_k\,d_{k-1}\,$ by $\rm \ \color{#c00}{(d_k\cdot 3 + d_{k-1})}\ {\rm mod}\ 7.\,$ For example

$\rm\qquad\qquad\qquad\qquad\phantom{\equiv} \color{#C00}{4\ 3}\ 2\ 1\ 1$

$\rm\qquad\qquad\qquad\qquad\equiv\phantom{4} \color{green}{1\ 2}\ 1\ 1\quad $ by $\rm\quad \color{#C00}4\cdot 3 + \color{#C00}3\ \equiv\ \color{green}1 $

$\rm\qquad\qquad\qquad\qquad\equiv\phantom{4\ 3} \color{royalblue}{5\ 1}\ 1\quad $ by $\rm\quad \color{green}1\cdot 3 + \color{green}2\ \equiv\ \color{royalblue}5 $

$\rm\qquad\qquad\qquad\qquad\equiv\phantom{4\ 3\ 5} \color{#b0f}{2\ 1}\quad $ by $\rm\quad \color{royalblue}5\cdot 3 + \color{royalblue}1\ \equiv\ \color{#b0f}2 $

$\rm\qquad\qquad\qquad\qquad\equiv\phantom{4\ 3\ 5\ 2} 0\quad $ by $\rm\quad \color{#b0f}2\cdot 3 + \color{#b0f}1\ \equiv\ 0 $

Hence $\rm\ 43211\equiv 0\:\ (mod\ 7)\:,\:$ indeed $\rm\ 43211 = 7\cdot 6173\:.\:$ Generally the modular arithmetic is simpler if one uses a balanced system of representatives, e.g. $\rm\: \pm\{0,1,2,3\}\ \:(mod\ 7)\:.$ Notice that for modulus $11$ or $9\:$ the above method reduces to the well-known divisibility tests by $11$ or $9\:$ (a.k.a. "casting out nines" for modulus $9$).

$\endgroup$

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