Base Representation

Suppose that \( m , k \in \mathbb{N}_{1} \) and \( \left ( a_{k} , a_{k - 1} , \ldots , a_{1} \right ) \in \left \lbrace 0 , 1 , 2 , \ldots , m - 1 \right \rbrace^{k} \). Then we define \( n := \sum_{i = 0}^{k - 1} a_{i} m^{i} \) and we say that the string \( a_{k } a_{k - 1} \ldots a_{1} \) is the representation of \( n \) in the base \( m \) and define
\[
\operatorname{ base\_repr } \left( n, m \right) := a _ { k } a _ { k - 1 } \ldots a _ 1
\]

Every Number has a Base \( b \) Representation

Let \( b \in \mathbb{ N } _ 2 \) and \( n \in \mathbb{ N } _ 0 \) then there exists a \( k \in \mathbb{ N } _ 1 \) and \( a _ 1, \ldots , a _ k \in \left[ 0, \ldots , b - 1 \right] \) such that
\[
n = \left( a _ k \ldots a _ 1 \right) _ b
\]

Let \( b \in \mathbb{ N } _ 2 \) and we continue with induction. In the base case when \( n = 0 \) then the representation \( \left( 0 \right) _ b \) works. Now let \( j \in \mathbb{ N } _ 0 \) and and let \( i \in \left[ 0, \ldots, j \right] \) and assume that it holds for \( i \), now we'll show it holds true for \( j + 1 \).

What we will try to do is extract the largest \( b ^ m \) we can from \( j + 1 \) and then use the induction hypothesis. So let \( J := \left\{ m \in \mathbb{ N } _ 1: b ^ m \le j + 1 \right\} \), this set has a maximum element because \( j + 1 \) is an upper bound, it is because we know that \( 1 \le j + 1 \le 2 ^ { j + 1 } \le b ^ { j + 1 } \) therefore \( j + 1 \) is indeed an upper bound to \( J \), let \( l \) be the max element of \( J \) and then by the quotient remainder theorem we have some \( q, r \in \mathbb{ Z } \) such that \[ j + 1 = q b ^ l + r \text{ with } 0 \le r \lt b ^ l \] since \( r \lt b ^ l \le j + 1 \) then the induction hypothesis holds on \( r \) so that \( r \) has a base \( b \) representation so that \[ r = \sum _ { i = 0 } ^ { p } c _ i b ^ i \] where \( p \lt l \), because if \( p \ge l \) then that makes \( r = \sum _ { i = 0 } ^ { p } x _ i b ^ i \ge b ^ l \) which is a contradiction since we know that \( r \lt b ^ l \) this means that the representation is exactly \[ \left( q c _ p \ldots c _ 0 \right) _ b \]

Every Base \( b \) Representation is Unique

For any \( b \in \mathbb{ N } _ 2 \) and \( n \in \mathbb{ N } _ 0 \) there is exactly one base \( b \) representation of \( n \)

Let \( b \in \mathbb{ N } _ 2 \) and perform induction on \( n \). So for \( n = 0 \) we know that the representation \( \left( 0 \right) _ b \) and for any other representation where \( a \neq 0 \) then \( \left( a \right) _ b \neq 0 \) there is exactly one representation as needed.

Now suppose that \( n \in \mathbb{ N } _ 0 \) and that for any \( k \in \left[ 0, \ldots n \right] \) has a unique base \( b \) representation, let's prove that \( n + 1 \) has a unique base \( b \) representation, for the sake of contradiction suppose that it has two different representations, which implies that \[ \sum _ { i = 0 } ^ { m } a _ i b ^ i = n + 1 = \sum _ { i = 0 } ^ { k } c _ i b ^ i \] firstly we claim that \( m = k \) for if that were not the case then without loss of generality \( m \lt k \) and note the following \[ \begin{align} \sum _ { i = 0 } ^ { m } a _ i b ^ i &\le \sum _ { i = 0 } ^ { m } \left( b - 1 \right) b _ i \\ &\le \left( b - 1 \right) \sum _ { i = 0 } ^ { m } b _ i \\ &\le \left( b - 1 \right) \frac{b ^ { m + 1 } - 1 }{b - 1} \\ &= b ^ { m + 1 } - 1 \lt b ^ { m + 1 } \end{align} \] Note that since \( m \lt k \) we know that \( m + 1 \le k \) then we know that \[ b ^ { m + 1 } \le b ^ k \le \sum _ { i = 0 } ^ { k } c _ i b ^ i \] which is a contradiction because chaining the last few inequalities we obtain \[ n + 1 = \sum _ { i = 0 } ^ { m } a _ i b ^ i \lt \sum _ { i = 0 } ^ { k } c _ i b _ i = n + 1 \] thus we deduce that \( m = k \).

Now we additionally claim that \( a _ m = c _ k \) for if that were not the case then without loss of generality we assume that \( a _ m \lt c _ k \) and therefore \[ \left( n + 1 \right) - a _ m b ^ m = \sum _ { i = 0 } ^ { m } a _ i b ^ i - a _ m b ^ m = \sum _ { i = 0 } ^ { m - 1 } a _ i b ^ i \] but also \[ \begin{align} \left( n + 1 \right) - a _ m b ^ m &= \sum _ { i = 0 } ^ { k } c _ i b ^ i - a _ m b ^ m \\ &= c _ k b ^ k + \cdots + \left( c _ m - a _ m \right) b ^ m + \cdots + c _ 0 b ^ 0 \end{align} \] and since \( c _ m - a _ m \gt 0 \) this is valid base \( b \) representation of \( \left( n + 1 \right) - a _ m b ^ m \), but clearly they differ as \( a _ k \neq 0 \) and so the length of the two representations are different. This a contradiction because by our induction hypothesis they must have the same base \( b \) representation, therefore our assumption that \( n + 1 \) has two different base \( b \) representations is false and therefore by strong induction the original statement is true.

Decimal Representation

The decimal representation of a number \( n \) is the representation of \( n \) in the base \( 10 \)

binary representation

The binary representation of a number \( n \) is the represetnation of \( n \) in the base \( 2 \)

Binary Natural Numbers

We define the following:
\[
\mathbb{ B } := \operatorname{ base\_repr } \left( \mathbb{ N } _ 0, 2 \right)
\]

Number of Digits Required in a Base 2 Representation

Given any \( n \in \mathbb{ N } _ 0\) prove that the number of digits in it's base 2 representation is given by
\[
\left\lfloor \log _ 2 \left( n \right) \right\rfloor + 1
\]

Let \( n \in \mathbb{N} \), suppose \( n \) requires \( d \) digits in it's base 2 representation, we'd like to show that \(d = \lfloor \log_2(n) \rfloor+1\).

At most we have \(n = 1 \ldots 1\), that is \( d \) 1's in a row. But we know that is

\[ \sum_{i=0}^{d-1} 2^i = 2^d - 1 \]At a minimum the first digit is a 1 and the rest are zeros (since the powers start at 0 right to left, this is \( 2^{d - 1} \)).

We now have the following bound on \( n \).

\[ 2^{d-1 } \le n \le 2^d - 1 \]Taking log base 2 on on the above inequality yields: (Call this inequality $\beta$)

\[ d - 1 \le \log_2 (n) \le \log_2(2^d -1 ) \]*Note*: Taking the log respects the inequalities because $\log_2(\cdot)$ is a strictly increasing function (check it's derivative)

We will attempt to take the floor of \( \beta \). Since \( d-1 \) is an integer \( \lfloor d-1 \rfloor = d-1 \), as for \( \log_2(2^d-1) \), we must look a little closer.

Since \( 2^{d-1} \le 2^d - 1 < 2^d \) and , we know that

\[ d-1 = \log_2(2^{d-1}) \le \log_2(2^d - 1) < log_2(2^d) = d \]Therefore \(\lfloor \log_2(2^d - 1) \rfloor = d-1 \) and so the result of taking the floor of \(\beta \) yields

\[ d - 1 \le \lfloor \log_2 (n) \rfloor \le \lfloor \log_2(2^d -1 ) \rfloor = d-1 \]In other words

\[ d - 1 \le \lfloor \log_2 (n) \rfloor \le d-1 \]So

\[ d - 1 = \lfloor \log_2 (n) \rfloor \Leftrightarrow d = \lfloor \log_2 (n) \rfloor + 1 \]Base Plus Minus One To a Power is Congruent to Plus Minus One

For any \( b \in \mathbb{ N } _ 2 \) and for any \( n \in \mathbb{ N } _ 1 \) and let \( x \) be the character we use to represent \( b - 1 \) then
\[
\left( 10 ^ n \right) _ b = \left( x \ldots x \right) + 1
\]

Division by 9 Rule

Suppose that \( n = \left( a _ k \ldots a _ 0 \right) \) then \( 9 | n \) if and only if
\[
9 | \sum_{i = 0}^{k - 1} a_{i}
\]

We know that \( 10 ^ n \equiv 1 ^ n \left( \operatorname{ mod } 10 \right) \) and therefore
\[
\begin{align}
n &= \sum _ { i = 0 } ^ { k } a _ i 10 ^ i \\
&\equiv \sum _ { i = 0 } ^ {k } a _ i \left( \operatorname{ mod } 9 \right)
\end{align}
\]