Given a number in base 9, so the number $n=a_t9^t+a_{t-1}p^{t-1}+\ldots+a_0$; then how to devise rule for divisibility by 2?

I hope there is no easy way without conversion of the number to base 10.

Have got help here, based on which I am stating the approach based on conversion to base 10 from base 9. In base $b+1$ where integer $b\ge1$ as: $$b+1\equiv1\pmod b\implies(b+1)^r\equiv1^r\equiv1 \pmod b$$ $$\sum_{r=0}^t(b+1)^ra_r\equiv \sum_{r=0}^ta_r\pmod b$$ So, $\sum_{r=0}^t(10)^ra_r\equiv \sum_{r=0}^ta_r\pmod 9$

So, does it imply that because of the equivalence, the same rule exists for divisibility by 2, i.e. the sum of digits is divisible by 2?

If yes, then what about divisibility by 3 in base 9?


All these divisibility rules are simply instances of a general rule for checking whether a number in base $b$ is divisible by $n$. In fact, it's a general rule for determining the remainder left when a base $b$ number is divided by $n$, but divisibility follows as an obvious corollary, since a number is divisible by $n$ only when dividing it by $n$ leaves no remainder.

When stated in terms of modular arithmetic, the rule is almost trivial. Specifically, if $r$ is the remainder left when the base $b$ number $a = a_k b^k + a_{k-1} b^{k-1} + \dots + a_2 k^2 + a_1 k + a_0$ is divided by $n$, then

$$a = a_k b^k + a_{k-1} b^{k-1} + \dots + a_2 k^2 + a_1 k + a_0 \equiv r \pmod n.$$

A fundamental property of modular arithmetic is that the value of a polynomial expression (or, more generally, any expression involving only additions and multiplications) modulo $n$ does not change if we replace any term or factor in the expression with a value congruent to it modulo $n$.

In particular, to easily calculate $r$ using the congruence above, we can replace the powers of $b$ by their values reduced modulo $n$. (It does not particularly matter which representatives we choose for the congruence classes, although in practice it's often easiest to choose the ones closest to zero.)

It is well known that the sequence $(1, b, b^2, b^3, \dots)$ reduced modulo $n$ will always eventually settle into a cycle, simply because it's the orbit of the iterated function $x \mapsto bx$ on the finite set of integers modulo $n$. Thus, we can evaluate the polynomial modulo $n$ by:

  1. grouping together all the terms $a_i b^i$ for which the coefficients $b^i$ are congruent modulo $n$;
  2. adding up the $a_i$ factors for those terms, (optionally) reducing the sum modulo $n$, and multiplying the result by $b^i$ reduced modulo $n$; and
  3. finally adding up the values of each group of terms together and reducing it modulo $n$.

As a worked example, let's calculate the remainder of $a = 314\,159\,265\,358\,979\,323$ (in base $b = 10$) modulo $n = 7$.

We know (or can easily determine) that

$$\begin{aligned} 10^0 &\equiv 1, \\ 10^1 &\equiv 3, \\ 10^2 &\equiv 3 \cdot 3 = 9 \equiv 2, \\ 10^3 &\equiv 3 \cdot 2 = 6 \equiv -1, \\ 10^4 &\equiv 3 \cdot -1 = -3, \\ 10^5 &\equiv 3 \cdot -3 = -9 \equiv -2, \\ 10^6 &\equiv 3 \cdot -2 = -6 \equiv 1 \equiv 10^0, \end{aligned} \pmod 7$$

and so on, i.e. that the powers of 10 modulo 7 cycle with a period of 6 starting from the first term:

$$(10^0, 10^1, 10^2, 10^3, 10^4, 10^5, 10^6, 10^7, 10^8, 10^9, \dots) \equiv (1, 3, 2, -1, -3, -2, 1, 3, 2, \dots).$$

Thus, we can take every sixth base 10 digit of $n$ (starting from the end), sum them together, multiply them by the corresponding reduced power of 10, and repeat for the next digits:

$$\begin{aligned} 314\,159\,265\,358\,979\,323 &\equiv (3+8+9) \cdot 1 \\&+ (2+5+5) \cdot 3 \\&+ (3+3+1) \cdot 2 \\ &+ (9+5+4) \cdot (-1) \\&+ (7+6+1) \cdot (-3) \\&+ (9+2+3) \cdot (-2) \\ &\equiv 6 \cdot 1 + 5 \cdot 3 + 0 \cdot 2 - 4 \cdot 1 - 0 \cdot 3 - 0 \cdot 2 \\ &\equiv 6 + 1 + 0 - 4 - 0 - 0\\ &\equiv 3. \end{aligned} \pmod 7$$

Note that, when doing the sums and multiplications above, I've immediately reduced all the intermediate values modulo 7: this keeps the numbers small, and thus simplifies the later steps.

I could've also e.g. grouped the sums with complementary coefficients (1 and -1, 3 and -3, 2 and -2) together to (possibly) simplify the calculation, but the general technique shown above works for any base $b$ and modulus $n$, whether or not the powers of $b$ modulo $n$ happen to come in such complementary pairs or not. Of course, in some cases (e.g. when $b \equiv \pm 1 \pmod n$) the coefficients end up being particularly simple and easy to work with.

One thing the example above does not demonstrate is what happens when the base $b$ and the modulus $n$ share a common factor: in this case the powers of $b$ modulo $n$ will not start to cycle immediately, but only after going through one or more extra values that are not part of the cycle. For example, if I'd chosen $n = 6$ instead of $n = 7$ above, then the sequence of powers of 10 modulo $n$ would've been:

$$(10^0, 10^1, 10^2, 10^3, 10^4, \dots) \equiv (1, -2, -2, -2, -2, \dots) \mod 6$$

instead, with the first term not belonging to the (one-element) cycle, and thus the calculation would look like:

$$\begin{aligned} 314\,159\,265\,358\,979\,323 &\equiv 3 \cdot 1 \\&+ (2+3+9+7+9+8+5+3+5+6 \\&\quad\ \ \ \, +2+9+5+1+4+1+3) \cdot (-2) \\ &\equiv 3 - 4 \cdot 2 \\ &\equiv 1. \end{aligned} \pmod 6$$

In particular, if you're really lucky (i.e. if $b$ happens to share all the prime divisors of $n$) then the sequence of powers of $b$ modulo $n$ will at some point hit zero and stay there, allowing you to completely ignore all but the first few base $b$ digits of the number when testing for its divisibility by $n$.

  • $\begingroup$ Words aren't enough to thank you. It is a really superb answer. I am slightly confused over the fact that was not able to locate such detail or even lesser anywhere. So is it only the self work one has to put in, as above; or some source is available to guide. $\endgroup$ – jitender Feb 20 '18 at 13:22
  • $\begingroup$ Also, till now have not completed reading it, but have nearly finished much more than half, so would post any queries after some time, if they arise at all. $\endgroup$ – jitender Feb 20 '18 at 13:24
  • 1
    $\begingroup$ @jitender: I'm sure there are other sources describing this method of divisibility testing; it's definitely not novel, although the specific way I explained it may possibly have some trace of originality. Here's a similar explanation from Math Forum that I found via Google. I would've also pointed you to the Wikipedia article on divisibility rules, but in its current form it mostly just lists a bunch of specific rules without clearly describing the general method of constructing them. $\endgroup$ – Ilmari Karonen Feb 20 '18 at 14:01

Your reasoning on the equivalence is correct; checking divisibility by 2 in base 9 is akin to checking for divisibility by 9 in base 10. Expanded: $$n=a_t9^t+ a_{t-1}9^{t-1}+\dots+a_0\equiv a_t1^t+ a_{t-1}1^{t-1}+\dots+a_0\equiv a_t+a_{t-1}+\dots+a_0\bmod2$$ so an integer in base 9 is divisible by 2 iff its sum of digits is, and thus iff an even number of its digits are odd (1, 3, 5, 7).

As for checking divisibility by 3 in base 9, that's trivial. Since 3 divides 9, an integer in base 9 is divisible by 3 iff its last digit is 0, 3 or 6.

  • $\begingroup$ Haven’t seen you for a while. Welcome back! $\endgroup$ – Lubin Feb 20 '18 at 3:23
  • $\begingroup$ @Lubin What do you mean, "haven't seen me for a while"? I just smashed the stack again! $\endgroup$ – Parcly Taxel Feb 20 '18 at 3:25
  • $\begingroup$ There is a difference here that from base $10$: for base $10$, the last digit only matters for checking divisibility by $2$, while for divisibility by $3$ the sum of digits matter. But, in your answer, there is a reverse criteria for the two - i.e., only checking last digit for divisibility by $3$, while checking the sum of digits (as stated that - sum of odd digits is even) for checking divisibility by $2$. Based on your answer, cannot explain the opposite reasons employed for the two ($2,3$) for different bases ($9,10$). $\endgroup$ – jitender Feb 20 '18 at 3:27
  • 1
    $\begingroup$ @jitender: You only need to check the last digit if the divisor divides exactly into the base. So 2 divides 10 so you only need to check the last digit and 3 divides 9 so you only need to check the last digit. As for the summing - this works when your divisor is one less than the base. So 9 is one less than 10 so sum of digits being divisible by 9 works (and three because anything divisible by 9 is divisible by 3). Likewise 8 is one less than nine so if the sum of the digits (in base 9) is divisible by 8 then the number is divisible by 8 (and thus also divisible by 2). $\endgroup$ – Chris Feb 20 '18 at 9:19

Quick method for determining parity of a nonary number: if the number of odd digits is even, your number is even. Otherwise, odd.

But do you know the elementary-school method called “Casting Out Nines”, which depends on decimal notation? There’s an equivalent method of Casting out Eights, in nonary notation. Working in nonary notation, take the sum of the digits repeatedly, and the final result will be the congruence of your original number modulo $8$. If this is even, your original number was even.

  • $\begingroup$ I request that in terms of the logic used in the OP, the two methods of 'Casting out eights' & 'Casting out Nines' be explained. $\endgroup$ – jitender Feb 20 '18 at 3:36
  • 1
    $\begingroup$ @jitender, here goes: $10\equiv1\pmod9$, and therefore $10^n\equiv1\pmod9$. Therefore, $\sum a_n10^n\equiv\sum a_n\pmod9$. To check an addition, subtraction, or multiplication of whole numbers: for each of the inputs, calculate the congruence modulo $9$ by the method of repeated summation of digits, and do the same for the result. One should get the sum (difference, product) of the congruences of the inputs is equal to the congruence of the result. If not, you’ve certainly made a mistake. $\endgroup$ – Lubin Feb 20 '18 at 14:01

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.