Base Number Systems

Introduction to Base Number Systems#

A base is a natural number B whose powers (B multiplied by itself some number of times) are specially designated within a numerical system

The Base 10 Number System

• Also called the decimal system
• Represents numbers using ten digits; 0,1,2,3,4,5,6,7,8,9;
• Multiplies each digit by a power of 10 based on its position

$$1234 = (1\times 10^3) + (2 \times 10^2) + (3 \times 10^1) + (4\times 10^0).$$

Some numbers have two representations in base 10, i.e.

$$\begin{align*} x&=0.\overline{9} \\ 10x &= 9.\overline{9} \\ 10x &= 9 + 0.\overline{9} \\ 10x &= 9 + x \\ 9x &= 9 \\ x &= 1 \end{align*}$$

Here, $x$ represents both $0.\overline{9}$ and $1$.

Basically, base $b$ works exactly like the decimal system except that each position now scales by a power of $b$ instead of a power of $10$, and the only digits allowed are $0$ up to $b-1$. Negative numbers are handled by simply putting a negative sign at the front of the digit string, and we omit writing infinitely many trailing zeros past the radix point; we write $10$ rather than $10.000\dots$

The final condition in the definition bans digit strings that end in the digit $b-1$ repeating forever. This is exactly the base $b$ version of the $0.\overline{9}=1$ situation from above; without this condition, some numbers would have two different representations and the notation would be ambiguous.

Example. Show that $(0.\overline{(b-1)})_b = 1$ in every base $b \geq 2$.
Let $x = (0.\overline{(b-1)})_b$. Multiplying by $b$ shifts the radix point one place to the right, so

$$\begin{align*} bx &= ((b-1).\overline{(b-1)})_b \\ bx &= (b-1) + x \\ bx - x &= b-1 \\ (b-1)x &= b-1 \\ x &= 1. \end{align*}$$

Therefore, $(0.\overline{7})_8 = 1$, $(0.\overline{4})_5 = 1$, $(0.\overline{1})_2 = 1$, and so on; the $0.\overline{9}$ trick was never really about $10$ at all.

When writing numbers in different bases, we should always include the base as a subscript, except in base 10 where it is standard to omit it. In bases greater than $10$ we run out of ordinary digits, so any digit larger than $9$ is surrounded with brackets, e.g. $(9(15)(33))_{60}$. In some bases such as base 16 (hexadecimal), it is instead standard to use capital letters as the new digits.

Example. Convert $(DAB)_{16}$ to a decimal (base 10) number.
Here, each digit represents the following;
$A=10,B=11,C=12,D=13 \cdots F=15$, therefore,

$$\begin{align*} (DAB)_{16} &= (13\times16^2) + (10\times16^1) + (11 \times 16^0) \\ &= 3328+160+11 \\ &= 3499 \end{align*}$$

Example. Convert $(1234)_5$ to a decimal number.
Each digit gets multiplied by the power of $5$ determined by its position;

$$\begin{align*} (1234)_5 &= (1\times 5^3) + (2 \times 5^2) + (3 \times 5^1) + (4 \times 5^0) \\ &= 125 + 50 + 15 + 4 \\ &= 194. \end{align*}$$

Therefore, $(1234)_5 = 194$.

Example. Convert $(9(15)(33))_{60}$ to a decimal number.
Base 60 needs sixty different digits, so the digits $15$ and $33$ are written in brackets. The digit string here is $9, 15, 33$, and each digit is multiplied by a power of $60$;

$$\begin{align*} (9(15)(33))_{60} &= (9 \times 60^2) + (15 \times 60^1) + (33 \times 60^0) \\ &= 32400 + 900 + 33 \\ &= 33333. \end{align*}$$

Therefore, $(9(15)(33))_{60} = 33333$. Do not read $(9(15)(33))_{60}$ as the digit string $9,1,5,3,3$; each bracketed block is one single digit.

Example. Convert $(101.0101)_2$ to a decimal number.
Digits after the radix point are multiplied by negative powers of the base;

$$\begin{align*} (101.0101)_2 &= (1 \times 2^2) + (0 \times 2^1) + (1 \times 2^0) + (0 \times 2^{-1}) + (1 \times 2^{-2}) + (0 \times 2^{-3}) + (1 \times 2^{-4}) \\ &= 4 + 1 + \frac{1}{4} + \frac{1}{16} \\ &= 5 + \frac{5}{16} \\ &= \frac{85}{16}. \end{align*}$$

Therefore, $(101.0101)_2 = \frac{85}{16} = 5.3125$.

Converting Non-Decimal Numbers to Decimal#

Basically, every base representation falls into exactly one of three buckets: it either stops (terminating), eventually falls into a repeating cycle (periodic), or does neither (non-periodic). Which bucket a number lands in tells us something about the number itself:

Notice how the theorem says any base; rationality is a property of the number, not of the representation. So $\sqrt{2}$ and $\pi$ have non-periodic expansions in base 2, base 7, base 16 — every base. The reason this works is the conversion algorithm later in these notes: when converting a rational number, the remainder at each step can only take finitely many values, so eventually a remainder must repeat (basically the pigeonhole principle), which forces the digits into a cycle.

We can even predict which rationals terminate and which recur, before doing any actual converting:

Basically, a terminating representation is just a fraction of the form $\frac{m}{b^n}$, and $\frac{p}{q}$ can be rewritten in that form precisely when all of $q$'s prime factors already appear in $b$.

Example. Without converting, decide whether each of the following terminates or recurs: $\frac{3}{8}$ in base 6, $\frac{24}{35}$ in base 5, and $\frac{1}{5}$ in base 2.

• For $\frac{3}{8}$ in base 6: $q = 8 = 2^3$, whose only prime factor is $2$, and $2 \mid 6$; the representation terminates.
• For $\frac{24}{35}$ in base 5: $q = 35 = 5 \times 7$, and $7 \nmid 5$; the representation is periodic.
• For $\frac{1}{5}$ in base 2: $q = 5$, and $5 \nmid 2$; the representation is periodic.

Therefore whether a rational terminates depends on the base; $\frac{1}{5} = 0.2$ terminates in base 10 yet recurs forever in base 2. We will verify the first two of these with the conversion algorithm later.

Example. Convert $(0.\overline{123})_4$ to a decimal (base 10) number.
Suppose $x = (0.\overline{123})_4$, then,

$$\begin{align*} (4)x &= (1.\overline{231})_4,\text{ (as multiplying a decimal by its own base shifts it 1 to the left)}, \\ (4^2)x&=(12.\overline{312})_4 \\ (4^3)x &= (123.\overline{123})_4 \\ (4^3-1)x &= (123.\overline{123})_4 - x \\ (4^3-1)x &= (123)_4 \\ x &= \frac{(123)_4}{(4^3-1)_{10}} \\ x &= \frac{27}{63} \\ x &= \frac{3}{7}. \end{align*}$$

This method for periodic base representations can be generalised as follows:

• Let $x$ be the number in base $b$ representation and let $k$ be the period length.
• Find $b^k x$ by shifting the radix point $k$ places to the right.
• Calculate $b^k x - x$ to eliminate the repeating part.
• Factorise the left-hand side and divide to get $x = \frac{b^k x - x}{b^k - 1}$ in base $b$.
• Convert the numerator and denominator to decimal forms and simplify the fraction if necessary.

Example. Express $y=(0.12\overline{34})_6$ as a decimal fraction.
Here, $b=6$, $k=2$, so the answer would be

$$\frac{(12.34\overline{34})_6 - (0.12\overline{34})_6}{(6^2 - 1)_{10}}$$

In the numerator, the recurring part cancels out after the radix point to only leave $34-12$ which is $22$, meaning we get

$$\frac{(12.22)_6}{(6^2-1)_{10}}$$

or

$$y=\frac{151}{630}_{10}.$$

Doing this the normal way would be:
Suppose $x = (0.12\overline{34})_6$, then,

$$\begin{align*} 6^2 x&=(12.\overline{34})_6 \\ 6^2x - 1x&=(12.34\overline{34}-0.12\overline{34})_6 \\ (6^2-1)x&=12.22_6 \\ x &= \frac{12.22_6}{6^2-1} \\ x &= \frac{\frac{151}{18}}{6^2-1} \\ x &= \frac{\frac{151}{18}}{35} \\ x &= \frac{151}{630} \end{align*}$$

The Geometric Series Method#

Alternatively, we can convert a periodic representation to a decimal fraction using the formula for an infinite geometric series. Recall that for any real $r$ with $0 \leq |r| < 1$,

$$\boxed{\sum_{k=1}^{\infty} r^k = \frac{r}{1-r}.}$$

The idea is to treat each copy of the repeating block as one term of a geometric series, since every copy is $b^k$ times smaller than the copy before it, where $k$ is the period length. The derivation of this formula is first year stuff so I'm not writing it out.

Example. Write $(0.\overline{123})_4$ as a decimal fraction using the geometric series formula.
The repeating block is worth $(123)_4 = 1 \times 4^2 + 2 \times 4 + 3 = 27$, and the first copy of the block sits in the first three places after the radix point, so it is worth $\frac{27}{4^3}$; every later copy is $4^3 = 64$ times smaller than the one before it. Hence,

$$\begin{align*} (0.\overline{123})_4 &= \frac{27}{4^3} + \frac{27}{4^6} + \frac{27}{4^9} + \cdots \\ &= 27\sum_{k=1}^{\infty}\left( \frac{1}{64} \right)^k \\ &= 27 \times \frac{\frac{1}{64}}{1-\frac{1}{64}} \\ &= 27 \times \frac{1}{63} \\ &= \frac{3}{7}. \end{align*}$$

Therefore, $(0.\overline{123})_4 = \frac{3}{7}$, agreeing with the shifting method from before.

Example. Write $(0.12\overline{34})_6$ as a decimal fraction using the geometric series formula.
Split the number into its non-repeating head and its repeating tail. The head is

$$\begin{align*} (0.12)_6 &= \frac{1}{6} + \frac{2}{36} \\ &= \frac{8}{36} \\ &= \frac{2}{9}, \end{align*}$$

and the tail is made of copies of the block $(34)_6 = 3 \times 6 + 4 = 22$, where the first copy ends four places after the radix point (so it is worth $\frac{22}{6^4}$) and each later copy is $6^2 = 36$ times smaller;

$$\begin{align*} (0.00\overline{34})_6 &= \frac{22}{6^4} + \frac{22}{6^6} + \frac{22}{6^8} + \cdots \\ &= \frac{22}{6^2} \sum_{k=1}^{\infty} \left( \frac{1}{36} \right)^k \\ &= \frac{22}{36} \times \frac{\frac{1}{36}}{1 - \frac{1}{36}} \\ &= \frac{22}{36} \times \frac{1}{35} \\ &= \frac{11}{630}. \end{align*}$$

Adding the two parts together,

$$\begin{align*} (0.12\overline{34})_6 &= \frac{2}{9} + \frac{11}{630} \\ &= \frac{140}{630} + \frac{11}{630} \\ &= \frac{151}{630}, \end{align*}$$

which matches the shifting method. In general, use the shifting method when the digit subtraction $b^kx - x$ is easy to do, and the geometric series when you would rather work with plain fractions from the start.

Example. Convert the repeating binary number $(0.\overline{0011})_2$ to a fraction.
The period starts immediately after the radix point, so the shortcut $x = \frac{b^kx - x}{b^k - 1}$ applies directly with $b = 2$ and $k = 4$;

$$\begin{align*} x &= \frac{(0011)_2}{(2^4-1)_{10}} \\ &= \frac{3}{15} \\ &= \frac{1}{5}. \end{align*}$$

Therefore, $(0.\overline{0011})_2 = \frac{1}{5}$. Notice how $\frac{1}{5}$ terminates in base 10 but recurs in base 2, since $5 \nmid 2$, exactly as the terminating criterion predicted; this is basically why computers, which store numbers in binary, can never represent $0.2$ exactly.

A Base Conversion Algorithm#

The naive way to convert some $\alpha \in \mathbb{R}^+$ into base $b$ would be to find the largest power $b^k$ that does not exceed $\alpha$, take the largest multiple of $b^k$ that still fits (giving the leading digit), subtract it off, and repeat on whatever is left over. This works, but it has two problems:

• you need to know (or compute) all of the positive and negative powers of $b$ before you can even start; and
• if the expansion turns out to be periodic, you can never be sure when the periodic part begins and ends.

The following algorithm avoids both of these problems.

To convert a decimal number $\alpha \in \mathbb{R}^+$ to some other base $b$, we use two algorithms,

• one for the integer part $\lfloor \alpha \rfloor$; and
• one for the fractional part $\{\alpha\}$.

Integer Part: Use the division algorithm to find quotients $q_i$ and remainders $d_i$ when dividing by $b$ iteratively.

$$\begin{aligned} \lfloor \alpha \rfloor &= q_0 \times b + d_0 && \text{where } q_0, d_0 \in \mathbb{Z}, 0 \leq d_0 < b \\ q_0 &= q_1 \times b + d_1 && \text{where } q_1, d_1 \in \mathbb{Z}, 0 \leq d_1 < b \\ q_1 &= q_2 \times b + d_2 && \text{where } q_2, d_2 \in \mathbb{Z}, 0 \leq d_2 < b \\ &\;\;\vdots && \;\;\vdots \\ q_{n-2} &= q_{n-1} \times b + d_{n-1} && \text{where } q_{n-1}, d_{n-1} \in \mathbb{Z}, 0 \leq d_{n-1} < b \\ q_{n-1} &= 0 \times b + d_n && \text{where } d_n \in \mathbb{Z}, 0 \leq d_n < b \end{aligned}$$

The remainders from each step form the digits of the integer part of $\alpha$ in reverse. That is,

$$\lfloor \alpha \rfloor = (d_n d_{n-1} \dots d_2 d_1 d_0)_b.$$

Fractional part: Set $r_0 = \{\alpha\} = \alpha - \lfloor \alpha \rfloor$ and iteratively multiply $r_{i-1}$ by $b$, writing the result as a sum of its integer part $d_{-i}$ and its fractional part $r_i$:

$$\begin{aligned} b \times r_0 &= d_{-1} + r_1 && \text{where } d_{-1} = \lfloor b \times r_0 \rfloor \text{ and } r_1 = \{b \times r_0\}, \\ b \times r_1 &= d_{-2} + r_2 && \text{where } d_{-2} = \lfloor b \times r_1 \rfloor \text{ and } r_2 = \{b \times r_1\}, \\ &\;\;\vdots && \;\;\vdots \\ b \times r_{n-1} &= d_{-n} + r_n && \text{where } d_{-n} = \lfloor b \times r_{n-1} \rfloor \text{ and } r_n = \{b \times r_{n-1}\}, \end{aligned}$$

and if $\alpha$ is rational then the process will terminate at the $n$th step, when either:

• $r_n = 0$, so $\{\alpha\} = (0.d_{-1}d_{-2} \dots d_{-n})_b$; or
• $r_n = r_k$ for some $k < n$, in which case the expansion is periodic, and $\{\alpha\} = (0.d_{-1}d_{-2} \dots d_{-k}\overline{d_{-(k+1)} \dots d_{-n}})_b$.

Remember that the integer part digits come out in reverse order (last remainder first), whilst the fractional part digits come out in forwards order.

Example. Write $3579 \frac{3}{8}$ in base 6.

To convert $\alpha = 3579 \frac{3}{8}$ to base $b=6$, we split the number into its integer part $\lfloor \alpha \rfloor = 3579$ and its fractional part $\{\alpha\} = \frac{3}{8}$, and apply the two algorithms.

Integer Part: Use the division algorithm to find quotients $q_i$ and remainders $d_i$ when dividing by $6$ iteratively.

$$\begin{aligned} 3579 &= 596 \times 6 + 3 && \text{where } q_0=596, d_0 = 3 \\ 596 &= 99 \times 6 + 2 && \text{where } q_1=99, d_1 = 2 \\ 99 &= 16 \times 6 + 3 && \text{where } q_2=16, d_2 = 3 \\ 16 &= 2 \times 6 + 4 && \text{where } q_3=2, d_3 = 4 \\ 2 &= 0 \times 6 + 2 && \text{where } q_4=0, d_4 = 2 \end{aligned}$$

The remainders from each step form the digits of the integer part of $\alpha$ in reverse. That is,

$$\lfloor \alpha \rfloor = (24323)_6.$$

Fractional part: Set $r_0 = \{\alpha\} = \frac{3}{8}$ and iteratively multiply $r_{i-1}$ by $6$, writing the result as a sum of its integer part $d_{-i}$ and its fractional part $r_i$:

$$\begin{aligned} 6 \times \frac{3}{8} = \frac{9}{4} &= 2 + \frac{1}{4} && \text{where } d_{-1} = 2 \text{ and } r_1 = \frac{1}{4}, \\ 6 \times \frac{1}{4} = \frac{3}{2} &= 1 + \frac{1}{2} && \text{where } d_{-2} = 1 \text{ and } r_2 = \frac{1}{2}, \\ 6 \times \frac{1}{2} = 3 &= 3 + 0 && \text{where } d_{-3} = 3 \text{ and } r_3 = 0 \end{aligned}$$

Because $r_3 = 0$, the process terminates at the $3$rd step. So,

$$\{\alpha\} = (0.213)_6$$

Combining the integer and fractional parts gives the final unique representation:

$$3579 \frac{3}{8} = (24323.213)_6$$

Notice that $8 = 2^3$ and $2 \mid 6$, so the terminating criterion knew this fractional part would terminate before we ran a single step.

Example. Write $\frac{24}{35}$ in base 5.

Since $0 < \frac{24}{35} < 1$, there is no integer part to worry about; $\lfloor \alpha \rfloor = 0$. Also, $35 = 5 \times 7$ and $7 \nmid 5$, so the terminating criterion warns us in advance that the expansion will be periodic; the algorithm must end with a repeated remainder $r_n = r_k$ rather than with $r_n = 0$.

Fractional part: Set $r_0 = \{\alpha\} = \frac{24}{35}$ and iteratively multiply $r_{i-1}$ by $5$:

$$\begin{aligned} 5 \times \frac{24}{35} = \frac{24}{7} &= 3 + \frac{3}{7} && \text{where } d_{-1} = 3 \text{ and } r_1 = \frac{3}{7}, \\ 5 \times \frac{3}{7} = \frac{15}{7} &= 2 + \frac{1}{7} && \text{where } d_{-2} = 2 \text{ and } r_2 = \frac{1}{7}, \\ 5 \times \frac{1}{7} = \frac{5}{7} &= 0 + \frac{5}{7} && \text{where } d_{-3} = 0 \text{ and } r_3 = \frac{5}{7}, \\ 5 \times \frac{5}{7} = \frac{25}{7} &= 3 + \frac{4}{7} && \text{where } d_{-4} = 3 \text{ and } r_4 = \frac{4}{7}, \\ 5 \times \frac{4}{7} = \frac{20}{7} &= 2 + \frac{6}{7} && \text{where } d_{-5} = 2 \text{ and } r_5 = \frac{6}{7}, \\ 5 \times \frac{6}{7} = \frac{30}{7} &= 4 + \frac{2}{7} && \text{where } d_{-6} = 4 \text{ and } r_6 = \frac{2}{7}, \\ 5 \times \frac{2}{7} = \frac{10}{7} &= 1 + \frac{3}{7} && \text{where } d_{-7} = 1 \text{ and } r_7 = \frac{3}{7}. \end{aligned}$$

Here $r_7 = \frac{3}{7} = r_1$, so the process terminates at the $7$th step with $n = 7$ and $k = 1$; every digit strictly after $d_{-1}$ repeats indefinitely. Therefore,

$$\frac{24}{35} = (0.3\overline{203241})_5.$$

Notice how after the first step every remainder is a fraction with denominator $7$; there are only six possible non-zero values $\frac{1}{7}, \frac{2}{7}, \dots, \frac{6}{7}$, so the algorithm was always going to repeat within at most six further steps. This pigeonhole argument is exactly why rational numbers always have terminating or periodic expansions.

Example. Write $3499$ in base 16.

This is the integer part algorithm again, except now the remainders can be larger than $9$, so we translate them into hexadecimal digits at the end ($A = 10, B = 11, \dots, F = 15$).

$$\begin{aligned} 3499 &= 218 \times 16 + 11 && \text{where } q_0 = 218, d_0 = 11 = B \\ 218 &= 13 \times 16 + 10 && \text{where } q_1 = 13, d_1 = 10 = A \\ 13 &= 0 \times 16 + 13 && \text{where } q_2 = 0, d_2 = 13 = D \end{aligned}$$

Reading the remainders in reverse gives

$$3499 = (DAB)_{16},$$

which is exactly the number we converted in the other direction at the start of these notes; the two conversion processes undo each other. Each remainder is one single digit; a remainder of $13$ is the digit $D$, not the two digits $1$ and $3$.

Converting Between Non-Decimal Bases#

When converting a number between two bases that share a common root, meaning both bases are powers of the same integer $b$ (e.g., base $b^m$ and base $b^n$), we can bypass the standard base 10 conversion algorithms. Instead, we use base $b$ as an intermediate system.

This property allows us to translate numbers by "expanding" digits into blocks or "grouping" blocks into single digits.

To convert from a larger base $b^m$ to a smaller base $b$, expand each individual digit of the base $b^m$ number into its $m$-digit representation in base $b$. Padding with leading zeros is required to ensure every intermediate block has exactly $m$ digits.

To convert from a smaller base $b$ to a larger base $b^m$, group the base $b$ digits into blocks of length $m$.

• For the integer part $\lfloor \alpha \rfloor$, start at the radix point and group moving strictly to the left. Pad the leftmost block with leading zeros if necessary.
• For the fractional part $\{\alpha\}$, start at the radix point and group moving strictly to the right.

If a fractional part $\{\alpha\}$ is periodic in base $b$ with a period length of $k$, and we are grouping into blocks of length $m$ to convert to base $b^m$, the period may not immediately align with the block size.

To find the new periodic representation, the base $b$ sequence must be written out until the period length $k$ and the block size $m$ perfectly synchronize. This synchronization occurs at the least common multiple (LCM) of $k$ and $m$.

The new period length in base $b^m$ will be $\frac{\text{lcm}(k, m)}{m}$.

Example. Convert $(34.\overline{52})_8$ to base $2$.

Here, we are moving from base $8$ ($2^3$) to base $2$, so $b=2$ and $m=3$. We expand each base 8 digit into exactly 3 base 2 digits.

Integer part:

$$\begin{aligned} 3_8 &= 011_2 \\ 4_8 &= 100_2 \end{aligned}$$

Fractional part:

$$\begin{aligned} 5_8 &= 101_2 \\ 2_8 &= 010_2 \end{aligned}$$

Stringing these blocks together in order yields the base 2 representation. Leading zeros on the integer part can be omitted:

$$(34.\overline{52})_8 = (11100.\overline{101010})_2$$

Example. Convert $(10111.01\overline{10})_2$ to base $16$.
Here, we are moving from base $2$ to base $16$ ($2^4$), so $b=2$ and $m=4$. We group the digits into blocks of 4. Standard base 16 notation applies ($A=10, B=11, \dots, F=15$).

Integer part (start at radix, move left):

$$10111_2 \implies \underbrace{0001}_{1} \;\; \underbrace{0111}_{7}$$

Therefore, $\lfloor \alpha \rfloor = (17)_{16}$.

Fractional part (start at radix, move right):
The fraction is $0.01\overline{10}_2$, meaning the block $10$ repeats infinitely: $0.01101010\dots_2$. We group these into blocks of 4 moving right:

$$\underbrace{0110}_{6} \;\; \underbrace{1010}_{10 \,(A)} \;\; \underbrace{1010}_{10 \,(A)} \dots$$

Because the block $1010$ repeats indefinitely, the new period is simply $A$.

Therefore, $\{\alpha\} = (0.6\overline{A})_{16}$.

Combining both parts:

$$(10111.01\overline{10})_2 = (17.6\overline{A})_{16}$$

(Check: both sides equal $23\tfrac{5}{12}$; note we avoid a repeating $1$ on its own, since a tail of infinitely repeating $b-1$ digits is forbidden by Definition 2.1.)

Example. Write $(121.2)_3$ in base 9.

Here $9 = 3^2$, so $b = 3$ and $m = 2$; we group the base 3 digits into blocks of $2$.

Integer part (start at radix, move left): the string $121$ has odd length, so the leftmost block gets padded with a leading zero,

$$121_3 \implies \underbrace{01}_{1} \;\; \underbrace{21}_{7}$$

since $(01)_3 = 1$ and $(21)_3 = 2 \times 3 + 1 = 7$. Therefore, $\lfloor \alpha \rfloor = (17)_9$.

Fractional part (start at radix, move right): the string $2$ is too short for a full block, so it gets padded with a trailing zero (trailing zeros past the radix point change nothing),

$$2_3 \implies \underbrace{20}_{6}$$

since $(20)_3 = 2 \times 3 + 0 = 6$. Therefore, $\{\alpha\} = (0.6)_9$.

Combining both parts gives

$$(121.2)_3 = (17.6)_9.$$

As a sanity check, both sides are equal to $16\frac{2}{3}$ in decimal. Pad the integer part with leading zeros on the left, but pad the fractional part with trailing zeros on the right; padding the wrong side changes the number.

Converting Between Two Composite Bases ($b^m \to b^n$)#

To convert between two bases that share a root but are not direct powers of each other (e.g., base $16$ and base $8$, which both share root $2$), apply the Expansion algorithm followed by the Grouping algorithm.

Example. Convert $((11)(10).\overline{(11)})_{16}$ to base $8$.

Here, we convert from base $16$ ($2^4$) to the intermediate base $2$, and then group into base $8$ ($2^3$).

Step 1: Expand base 16 to base 2 ($m=4$).

$$\begin{aligned} (11)_{16} &= 1011_2 \\ (10)_{16} &= 1010_2 \\ (11)_{16} &= 1011_2 \end{aligned}$$

The intermediate representation is $(10111010.\overline{1011})_2$.

Step 2: Group base 2 to base 8 ($m=3$).
Integer part (start at radix, move left):

$$10111010_2 \implies \underbrace{010}_{2} \;\; \underbrace{111}_{7} \;\; \underbrace{010}_{2}$$

Thus, $\lfloor \alpha \rfloor = (272)_8$.

Fractional part (start at radix, move right):
The period $k=4$ (1011) and the block size $m=3$. The lowest common multiple of $4$ and $3$ is $12$, meaning we must write out $12$ bits of the repeating sequence before it perfectly aligns with our blocks of $3$.

$$0.101110111011\dots_2$$

Grouping by 3 moving right:

$$\underbrace{101}_{5} \;\; \underbrace{110}_{6} \;\; \underbrace{111}_{7} \;\; \underbrace{011}_{3}$$

After these $12$ bits, the grouped sequence of base $8$ digits will repeat identically.
Thus, $\{\alpha\} = (0.\overline{5673})_8$.
Combining both parts gives the final unique representation:

$$((11)(10).\overline{(11)})_{16} = (272.\overline{5673})_8$$

Divisibility Tricks from Base-$b$ Digits#

A nice payoff of understanding base representations is that the familiar base 10 divisibility tests (last digit for $2$ and $5$, digit sums for $3$ and $9$) all generalise, letting us read divisibility facts straight off the digits without converting anything.

Suppose $N = (d_n d_{n-1} \dots d_1 d_0)_b$ is a positive integer. Notice that for any $i \in \mathbb{Z}^+$,

$$b^i - 1 = (b-1)(b^{i-1} + b^{i-2} + \cdots + b + 1),$$

so $b-1$ divides $b^i - 1$ for every positive $i$. Subtracting the digit sum from $N$,

$$\begin{align*} N - (d_n + d_{n-1} + \cdots + d_0) &= \sum_{i=0}^{n} d_i b^i - \sum_{i=0}^{n} d_i \\ &= \sum_{i=1}^{n} d_i(b^i - 1), \end{align*}$$

which is a sum of multiples of $b-1$ and is hence itself divisible by $b-1$ (basically Lemma 1.3 from Topic 1 applied repeatedly). Therefore,

$$\boxed{(d_n d_{n-1} \dots d_0)_b \text{ and its digit sum } d_n + d_{n-1} + \cdots + d_0 \text{ differ by a multiple of } b-1.}$$

So $b-1$ divides $N$ if and only if it divides the digit sum, and the same holds for any divisor of $b-1$. In base 10 this is the digit sum test for $3$ and $9$ (i.e. casting out nines); in base 5 it becomes a digit sum test for $2$ and $4$.

Similarly, every divisor $c$ of $b$ divides $b^i$ for all $i \geq 1$, so $c$ divides all of $N$ except possibly the last digit; that is, $c \mid N$ if and only if $c \mid d_0$. In base 10 this is the last digit test for $2$, $5$ and $10$; in base 2 it says a binary integer is even exactly when it ends in $0$ (e.g. $(10111)_2 = 23$ is odd on sight).

Example. Without converting to decimal, decide whether $(1313)_5$ is even, and whether it is divisible by $4$. Then verify by converting.
Since the base $5$ is odd, the last digit tells us nothing about parity; but $2$ and $4$ both divide $b - 1 = 4$, so the digit sum test handles both at once. The digit sum is

$$1 + 3 + 1 + 3 = 8,$$

and since $2 \mid 8$ and $4 \mid 8$, the number is divisible by both $2$ and $4$. Verifying,

$$\begin{align*} (1313)_5 &= (1 \times 5^3) + (3 \times 5^2) + (1 \times 5^1) + (3 \times 5^0) \\ &= 125 + 75 + 5 + 3 \\ &= 208 \\ &= 4 \times 52. \end{align*}$$

Therefore, $(1313)_5$ is divisible by $4$ (and hence even), exactly as the digit sum promised. In base $b$, use the last digit to test divisors of $b$ and the digit sum to test divisors of $b-1$; testing parity by the last digit only works when the base is even.

There is also an alternating digit sum test for divisors of $b+1$ (generalising the base 10 test for $11$), which comes from the fact that $b+1$ always divides $b^i - (-1)^i$; deriving it is a good exercise.