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{array}{rl}x& =0.\overline{9}\\ 10x& =9.\overline{9}\\ 10x& =9+0.\overline{9}\\ 10x& =9+x\\ 9x& =9\\ x& =1\end{array}$$

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\ge 2$.
Let $x=(0.\overline{(b-1)}{)}_b$. Multiplying by $b$ shifts the radix point one place to the right, so

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

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{array}{rl}(DAB{)}_{16}& =(13\times 16^2)+(10\times 16^1)+(11\times 16^0)\\ & =3328+160+11\\ & =3499\end{array}$$

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

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

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{array}{rl}(9(15)(33){)}_{60}& =(9\times 60^2)+(15\times 60^1)+(33\times 60^0)\\ & =32400+900+33\\ & =33333.\end{array}$$

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{array}{rl}(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{array}$$

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{array}{rl}(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{array}$$

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{array}{rl}{6}^{2}x& =(12.\overline{34}{)}_6\\ 6^{2}x-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{array}$$

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\le |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{array}{rl}(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{array}$$

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{array}{rl}(0.12{)}_6& =\frac{1}{6}+\frac{2}{36}\\ & =\frac{8}{36}\\ & =\frac{2}{9},\end{array}$$

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{array}{rl}(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{array}$$

Adding the two parts together,

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

which matches the shifting method. In general, use the shifting method when the digit subtraction $b^{k}x-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^{k}x-x}{b^k-1}$ applies directly with $b=2$ and $k=4$;

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

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{array}{rlrl}\lfloor \alpha \rfloor & =q_0\times b+d_0& & \text{where }{q}_0,d_0\in \mathbb{Z},0\le d_0<b\\ q_0& =q_1\times b+d_1& & \text{where }{q}_1,d_1\in \mathbb{Z},0\le d_1<b\\ q_1& =q_2\times b+d_2& & \text{where }{q}_2,d_2\in \mathbb{Z},0\le d_2<b\\ & ⋮& & ⋮\\ q_{n-2}& =q_{n-1}\times b+d_{n-1}& & \text{where }{q}_{n-1},d_{n-1}\in \mathbb{Z},0\le d_{n-1}<b\\ q_{n-1}& =0\times b+d_n& & \text{where }{d}_n\in \mathbb{Z},0\le d_n<b\end{array}$$

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{array}{rlrl}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\},\\ & ⋮& & ⋮\\ 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{array}$$

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{array}{rlrl}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{array}$$

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{array}{rlrl}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{array}$$

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{array}{rlrl}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{array}$$

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{array}{rlrl}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{array}$$

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{array}{rl}{3}_8& =011_2\\ 4_8& =100_2\end{array}$$

Fractional part:

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

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⟹\underset{1}{\underbrace{0001}}\underset{7}{\underbrace{0111}}$$

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:

$$\underset{6}{\underbrace{0110}}\underset{10(A)}{\underbrace{1010}}\underset{10(A)}{\underbrace{1010}}\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\frac{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⟹\underset{1}{\underbrace{01}}\underset{7}{\underbrace{21}}$$

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⟹\underset{6}{\underbrace{20}}$$

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{array}{rl}(11{)}_{16}& =1011_2\\ (10{)}_{16}& =1010_2\\ (11{)}_{16}& =1011_2\end{array}$$

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⟹\underset{2}{\underbrace{010}}\underset{7}{\underbrace{111}}\underset{2}{\underbrace{010}}$$

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:

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

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{array}{rl}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{array}$$

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\ge 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{array}{rl}(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{array}$$

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.