Binary and $m$-ary notation

Each natural number is most commonly written in decimal form (or base $10$),

$$a=a_k10^k+...a_1 10+a_0,$$

where $0\leq a_i\leq 9$ are the digits. (Without loss of generality we may assume that the leading digit $a_k$ is non-zero.) This representation is unique. (In spite of the fact that the decimal representation of a real number is not unique - $1.0=.9999....$.) Similarly, each natural number can be written (uniqely) in a binary expansion (or base $2$),

$$a=a_k2^k+...+a_1 2+a_0,$$

where $0\leq a_i\leq 1$ are the bits. The binary representation of $a$ is written as $a\sim a_k...a_1a_0$. Clearly, $a$ is even if and only if $a_0=0$. To find the binary expansion of a natural number, perform the following steps.

(1)

Find the ``leading bit'' $a_k$ by determining the largest power of $2$ less than or equal to $a$. Call this power $k$ and let $a_k=1$.

(2)

Subtract this power from $a$ and replace $a$ by this difference.

(3)

If the result is non-zero, go to step 1; otherwise, stop.

This determines all the non-zero bits in the binary representation of $a$. The other bits are 0.

Example 1.3.1   Find the binary representation of $130$. The largest power of $2$ less than or equal to $130$ is $128=2^7$, so $a_7=1$. The largest power of $2$ less than or equal to $2=130-128$ is $2=2^1$, so $a_1=1$. The other bits are zero: $a_6=a_5=a_4=a_3=a_2=a_0=0$, so

$$130=128+2\sim 10000010.$$

More generally, let us fix an integer $m>1$. Each natural number can be written in an $m$-ary expansion

$$a=a_km^k+...+a_1 m+a_0,$$

where $0\leq a_i\leq m-1$ are the $m$-ary digits. Again, the $m$-ary representation of $a$ is written as $a\sim a_k...a_1a_0$. Clearly, $m\vert a$ if and only if $a_0=0$. To find the $m$-ary expansion of a natural number, perform the following steps.

(1)

Find $a_k$ by determining the largest power of $m$ less than or equal to $a$. Call this power $k$.

(2)

Find the largest positive integer multiple of this power which is less than or equal to $a$. This multiple will be the $k$-th digit $a_k$.

(3)

Subtract $a_km^k$ from $a$ and replace $a$ by this difference.

(4)

If the result is non-zero, go to step 1; otherwise, stop.

Example 1.3.2   Find the $3$-ary representation of $211$. The largest power of $3$ less than or equal to $211$ is $81=3^4$, and $211>2\cdot 81=162$ so $a_4=2$. The largest power of $3$ less than or equal to $49=211-162$ is $27=3^3$, and $49<2\cdot 27$ so $a_3=1$. The largest power of $3$ less than or equal to $22=49-27$ is $9=3^2$, and $22>2\cdot 9$ so $a_2=2$. The largest power of $3$ less than or equal to $4=22-18$ is $3=3^1$, and $4<2\cdot 3$ so $a_1=1$. The last ``bit'' is 1: $a_4=2,a_3=1,a_2=2,a_1=1,a_0=1$, so

$$211=2\cdot 3^4+1\cdot 3^3+2\cdot 3^2+1\cdot 3+1\sim 21211.$$

Example 1.3.3   Convert $100101$ from binary to $5$-ary. In decimal (or ``$10$-ary''), $100101$ is

$$1\cdot 2^5+0\cdot 2^4+0\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=32+4+1=37.$$

In $5$-ary,

$$37=1\cdot 5^2+2\cdot 5^1+2\cdot 5^0\sim 122.$$