Test for divisibility by 2 for a number written in base 9

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?

Answer

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