Skip to main content

Chapter 8 Some Base Results

We successively apply the division algorithm, first dividing \(n\) by \(b\) to obtain

\begin{equation*} n = bq_0 + a_0, \hspace{5mm} (0\leq a_0 \leq b-1). \end{equation*}

If \(q_0\) is zero, we are done and \(n = a_0.\) Otherwise continue this process, ending if every \(q_i = 0,\) to give a sequence of equalities,

\begin{align*} q_0 \amp= bq_1 + a_1\\ q_1 \amp= bq_2 + a_2\\ \amp\vdots\\ q_{m-2} \amp= bq_{m-1} + a_{m-1}\\ q_{m-1} \amp= b\cdot 0 + a_m, \end{align*}

where for each \(i, 0\leq a_i\leq b-1,\) and the quotient \(0\) is eventually obtained since

\begin{equation*} n\gt q_0\gt q_1\gt \cdots \geq 0. \end{equation*}

Substituting the equations back starting with the first and going to the last gives such a representation.

For uniqueness, suppose that we have two representations

\begin{align*} n \amp= a_mb^m + a_{m-1}b^{m-1} +\cdots + a_1b + a_0\\ \amp= c_mb^m + c_{m-1}b^{m-1} +\cdots + c_1b + c_0, \end{align*}

where \(0\leq a_i, c_i\leq b-1\) and if where if needed we have padded the higher indices of one of the expansions with zeros. Now subtracting the expansions from each other, we have

\begin{equation*} (a_m-c_m)b^m + (a_{m-1}-c_{m-1})b^{m-1} +\cdots + (a_1-c_1)b + (a_0-c_0)=0. \end{equation*}

If the two expansions are different, then there is a minimal integer \(j \hspace{2mm} (0\leq j\leq m)\) such that \(a_j-c_j\neq 0.\) Thus

\begin{equation*} b^j((a_m-c_m)b^{m-j} + (a_{m-1}-c_{m-1})b^{m-j-1} +\cdots + (a_j-c_j))=0, \end{equation*}

so that

\begin{equation*} (a_m-c_m)b^{m-j} + (a_{m-1}-c_{m-1})b^{m-j-1} +\cdots + (a_{j+1}-c_{j+1})b=-(a_j-c_j), \end{equation*}

and \(b\vert (a_j-c_j).\) But this is possible only if \(a_j = c_j,\) a contradiction, so the expansion is unique.

We write the base-\(b\) expansion of an integer \(n\) (as in the above theorem) as

\begin{equation*} n = (a_ma_{m-1}\cdots a_1a_0)_b = a_mb^m+a_{m-1}b^{m-1}+\cdots +a_1b+a_0. \end{equation*}

Let \(c_1:= \lfloor b\xi\rfloor,\) so that \(0\leq c_1\leq b-1\) and set

\begin{equation*} \xi_1 := b\xi-c_1 = \{b\xi\}, \end{equation*}

so \(\xi_1\in [0, 1)\) and

\begin{equation*} \xi = \frac{c_1}{b}+\frac{\xi_1}{b}. \end{equation*}

We recursively define for \(k\geq 2\)

\begin{equation*} c_k := \lfloor b\xi_{k-1}\rfloor \hspace{5mm} \mathrm{and} \hspace{5mm} \xi_k = b\xi_{k-1}- c_k = \{b\xi_k\} \end{equation*}

so that \(0\leq c_k\leq b-1\) and \(\xi_k\in [0, 1).\) Then we have

\begin{equation*} \xi = \frac{c_1}{b}+\frac{c_2}{b^2}+\cdots +\frac{c_n}{b^n}+\frac{\xi_n}{b^n}. \end{equation*}

Since \(\xi_n\in [0, 1),\) we have

\begin{equation*} \lim_{n\rightarrow\infty}\frac{\xi_n}{b^n}=0, \end{equation*}

and so

\begin{equation*} \xi=\lim_{n\rightarrow\infty}\left(\frac{c_1}{b}+\frac{c_2}{b^2}+\cdots +\frac{c_n}{b^n}\right)=\sum_{i\geq 1}\frac{c_i}{b^i}. \end{equation*}

For uniqueness, assume that there are two different expansions

\begin{equation*} \xi=\sum_{i\geq 1}\frac{c_i}{b^i}=\sum_{i\geq 1}\frac{d_i}{b^i}, \end{equation*}

where \(0\leq c_i\leq b-1\) and \(0\leq d_i\leq b-1\) and for each integer \(N,\) there are \(n\) and \(m\) larger than \(N\) such that \(c_n \neq b-1\) and \(d_m \neq b-1.\) Suppose that \(k\) is the smallest index for which \(c_k \neq d_k.\) Without loss of generality we assume that \(c_k\gt d_k.\) Then

\begin{equation*} 0 = \sum_{i\geq 1}\frac{c_i-d_i}{b^i}=\frac{c_k-d_k}{b^k}+\sum_{i\geq k+1}\frac{c_i-d_i}{b^i}, \end{equation*}

so that

\begin{equation*} \frac{c_k-d_k}{b^k}=\sum_{i\geq k+1}\frac{d_i-c_i}{b^i}. \end{equation*}

But one easily sees that

\begin{equation*} \frac{1}{b^k}\leq \frac{c_k-d_k}{b^k}=\sum_{i\geq k+1}\frac{d_i-c_i}{b^i}\lt \sum_{i\geq k+1}\frac{b-1}{b^i}=(b-1)\frac{1/b^{k+1}}{1-1/b}=\frac{1}{b^k}. \end{equation*}

This contradiction proves uniqueness and the theorem.

We write the base-\(b\) expansion of a real number \(\xi\in [0, 1)\) (as in the above theorem) as

\begin{equation*} \xi = (0.c_1c_2c_3...)_b =\sum_{i\geq 1}\frac{c_i}{b^i}. \end{equation*}

Definition 8.0.3.

The base-\(b\) expansion \((0.c_1c_2c_3...)_b\) is said to terminate if there is a positive integer \(N\) such that \(c_n = 0\) for all \(n\geq N.\)

Suppose that \(\xi\) has a terminating base-\(b\) expansion. Then

\begin{equation*} \xi = (.c_1c_2...c_n)_b =\frac{c_1}{b}+\frac{c_2}{b^2}+\cdots +\frac{c_n}{b^n}=\frac{c_1b^{n-1}+c_2b^{n-2}+\cdots +c_n}{b^n}, \end{equation*}

so that \(\xi\) is rational and can be written with a denominator only divisible by primes dividing \(b.\)

Now suppose that \(\xi\in [0, 1)\) and \(\xi = r/s\) where each prime dividing \(s\) divides \(b.\) Then there is an \(N\) such that \(s\vert b^N,\) so there is an integer \(a\) such that \(sa = b^N.\) Then

\begin{equation*} b^N\xi=b^Nr/s=ar\in\mathbb{N}. \end{equation*}

Now let \((a_ma_{m-1}\cdots a_1a_0)_b\) be the base-\(b\) expansion of \(ar.\) Then

\begin{align*} \xi =\frac{ar}{b^N}=\frac{a_mb^{m}+\cdots +a_1b+a_0}{b^N} \amp=a_mb^{m-N}+\cdots +a_1b^{1-N}+a_0b^{-N}\\ \amp=(.00...0a_ma_{m-1}...a_1a_0)_b, \end{align*}

which is a terminating base-\(b\) expansion.

Definition 8.0.5.

A base-\(b\) expansion \((.c_1c_2c_3...)_b\) is called periodic if there are \(N, k\in\mathbb{N}\) such that \(c_{n+k} = c_n\) for all \(n\geq \mathbb{N}.\) If \(N\gt 1,\) we call the part \(c_1c_2...c_{N-1}\) the pre-period and the part \(c_Nc_{N+1}c_{N+k-1}\) the period where here \(k\) is minimal with respect to this property.

For the first part of the theorem, suppose that \(\xi\) has an eventually periodic base-\(b\) expansion, so that

\begin{align*} \xi \amp= (.c_1c_2...c_N \overline{c_{N+1}c_{N+2}...c_{N+k}})_b\\ \amp=\frac{c_1}{b}+ \frac{c_2}{b^2}+\cdots +\frac{c_N}{b^N}+\left(\sum_{j\geq 0}\frac{1}{b^{jk}}\right)\left(\frac{c_{N+1}}{b^{N+1}}+ \frac{c_{N+2}}{b^{N+2}}+\cdots +\frac{c_{N+k}}{b^{N+k}} \right) \\ \amp=\frac{c_1}{b}+ \frac{c_2}{b^2}+\cdots +\frac{c_N}{b^N}+\left(\frac{b^k}{b^k-1}\right)\left(\frac{c_{N+1}}{b^{N+1}}+ \frac{c_{N+2}}{b^{N+2}}+\cdots +\frac{c_{N+k}}{b^{N+k}} \right). \end{align*}

Since \(\xi\) is a sum of rational numbers it is rational.

Now suppose that \(\xi\in (0, 1), \xi = r/s\) where \(\gcd(r, s) = 1, s = TU\) where every prime dividing \(T\) divides \(b\) and \(\gcd(U, b) = 1.\) Let \(N\) be the smallest integer such that \(T\vert b^N.\)

Because \(T\vert b^N,\) there is a positive integer \(a\) such that \(aT = b^N.\) Thus

\begin{equation*} b^N\xi = b^N\frac{r}{TU}=\frac{ar}{U}=A+\frac{C}{U} \end{equation*}

where \(A\) and \(C\) are integers with

\begin{equation*} 0\leq A\lt b^N \hspace{5mm} \mathrm{and} \hspace{5mm} 0\lt C\lt U \end{equation*}

and \(\gcd(C, U) = 1.\) Now since \(A\) is a positive integer, it has a base-\(b\) expansion, say \(A = (a_na_{n-1}...a_1a_0)_b.\)

If \(U = 1,\) then the base-\(b\) expansion of \(\xi\) terminates as shown previously. Otherwise, since \(\gcd(U, b) = 1,\) we let \(v\geq 1\) be the order of \(b\) modulo \(U.\) Then

\begin{equation} b^v\frac{C}{U}=(tU+1)\frac{C}{U}=tC+\frac{C}{U},\label{Eq_8_1}\tag{8.0.1} \end{equation}

for some integer \(t,\) since \(b^v\equiv 1\pmod{U}.\) But also, we have

\begin{equation} b^v\frac{C}{U}=b^v\left(\frac{c_1}{b}+\frac{c_2}{b^2}+\cdots +\frac{c_v}{b^v}+\frac{\gamma_v}{b^v}\right),\label{Eq_8_2}\tag{8.0.2} \end{equation}

where \((.c_1c_2...)_b\) is the base-\(b\) expansion of \(\dfrac{C}{U},\) so that for \(k\geq 1,\)

\begin{equation*} c_k=\lfloor b\gamma_{k-1}\rfloor \hspace{5mm} \mathrm{and} \hspace{5mm} \gamma_k=b\gamma_{k-1}-\lfloor b\gamma_{k-1}\rfloor, \end{equation*}

and \(\gamma_0 =\dfrac{C}{U}.\) From (8.0.2) we see that

\begin{equation} b^v\frac{C}{U}=(c_1b^{v-1}+c_2b^{v-2}+\cdots +c_v)+\gamma_v.\label{Eq_8_3}\tag{8.0.3} \end{equation}

Equating the fractional parts of (8.0.1) and (8.0.3), since \(\gamma_v\in [0, 1),\) we have

\begin{equation*} \gamma_v =\frac{C}{U}=\gamma_0, \end{equation*}

and so conclude that \(c_{k+v} = c_k\) for \(k\geq 1.\) Hence \(C/U = (.\overline{c_1c_2...c_v})_b\) has a periodic base-\(b\) expansion. Thus

\begin{equation*} b^N \xi = A +\frac{C}{U}= (a_na_{n-1}...a_1a_0.\overline{c_1c_2...c_v})_b, \end{equation*}

so that dividing both sides by \(b^N\) gives

\begin{equation*} \xi = A +\frac{C}{U}= (.\underbrace{00...0a_na_{n-1}...a_1a_0}_{N \hspace{1.5mm} \mathrm{base}-b \hspace{1.5mm} \mathrm{digits}} \overline{c_1c_2...c_v})_b. \end{equation*}

So in this case, the preperiod length is \(N\) and the period length is \(v.\)

To finish the proof we must show that one cannot regroup the base-\(b\) expansion of \(\xi\) so that either the preperiod or the period are shorter. To do this, suppose that

\begin{align*} \xi \amp= (.c_1...c_{M}\overline{c_{M+1}...c_{M+k}})_b\\ \amp = \frac{c_1}{b}+\frac{c_2}{b^2}+\cdots +\frac{c_M}{b^M}+\left(\frac{b^k}{b^k-1}\right)\left(\frac{c_{M+1}}{b^{M+1}}+ \frac{c_{M+2}}{b^{M+2}}+\cdots +\frac{c_{M+k}}{b^{M+k}}\right)\\ \amp = \frac{(c_1b^{M-1}+c_2b^{M-2}+\cdots +c_M)(b^k-1)+(c_{M+1}b^{k-1}+\cdots +c_{M+k})}{b^M(b^k-1)}. \end{align*}

Because \(\xi = r/s\) with \(\gcd(r, s) = 1,\) we see that \(s\vert b^M(b^k-1).\) So \(T\vert b^M\) and \(U\vert b^k-1.\) Since \(N\) was minimal, \(M\geq N,\) and since \(v\) is the order of \(b\) modulo \(U, v\vert k\) (so \(v\leq k\)). This proves the theorem.

To write \(a/k\) in the base \(b,\) we use a sort of modified division algorithm; see Figure 8.0.7. We record here facts about the base-\(b\) algorithm, which we will need for our final results.

Figure 8.0.7. The base-\(b\) algorithm for the reduced rational \(a/k\lt 1.\)

Suppose that \(p\vert k,\) and proceed by induction on \(i.\) Firstly, \(r_0 = a\) and by assumption \(\gcd(r_0, k) = \gcd(a, k) = 1.\) Now suppose that \(\gcd(r_i, k) = 1,\) so that also \(\gcd(r_ib, k) = 1.\) Then

\begin{equation*} r_{i+1} = r_ib-q_{i+1}k\equiv r_ib \not\equiv 0 \pmod{p}, \end{equation*}

since \(\gcd(b, k) = 1.\) Thus \(\gcd(r_{i+1}, k) = 1.\)

Also, we have that equivalent \(r_j\) give equal \(q_j.\)

Suppose that \(r_i \equiv r_j \pmod{b}.\) By considering the difference between \(r_{i-1}b = q_ik + r_i\) and \(r_{j-1}b = q_jk + r_j\) modulo \(b,\) we see that \(b\vert (q_i-q_j)k,\) so that since \(\gcd(b, k) = 1,\) we have that \(b\vert (q_i-q_j).\) Since \(q_i, q_j \in \{0, 1,..., b-1\},\) we thus have that \(q_i = q_j.\)

Conversely, suppose that \(q_i = q_j.\) Here, again, we can consider the difference between the defining equations for \(q_i\) and \(q_j\) modulo \(b;\) this gives the desired result.

Indeed, the value of \(q_j\) is determined by the residue class of \(r_j\) modulo \(b\) and the value of \(k^{-1}\) modulo \(b.\)

If \(r_i \equiv j\pmod{b},\) then the equation \(r_{i-1}b = q_ik + r_i\) gives \(q_ik \equiv -j \pmod{b},\) which in turn gives that \(q_i \equiv -jk^{-1}\pmod{b}.\) Since \(q_i\in [0, b-1]\) we are done with this direction of proof.

Conversely, suppose that \(q_i = -jk^{-1}\pmod{b}.\) Then surely, \(q_i\equiv -jk^{-1}\pmod{b}\) and so \(q_ik \equiv -j\pmod{b}.\) Thus, again using \(r_{i-1}b = q_ik + r_i,\) we have that \(r_i \equiv j \pmod{b}.\)

The following Lemma is a direct corollary of Lemma 8.0.10.

Theorem 8.0.6 tells us that the base \(b\) expansion of \(a/k\) is purely periodic (recall for us \(\gcd(b, k) = 1),\) and that the minimal period is \(\mathrm{ord}_kb,\) which divides \(\varphi(k),\) so that this also is a period. This result can be exploited using a result on primitive roots. Indeed, applying Theorem 7.2.3 gives the following result.

This is a direct consequence of the base-\(b\) algorithm.

As a consequence of the above lemmas we are able to provide the following characterisation of certain base-\(b\) expansions.

The fact that \(\mathrm{period}(a/p^m)_b = \varphi(p^m)\) follows directly from \(b\) being a primitive root of \(p\) and \(p^2,\) Theorem 7.2.3 and Theorem 8.0.6. This further implies that the \(\varphi(p^m)\) values of \(r_i\) given by the base-\(b\) algorithm for \(a/p^m\) are distinct. Applying Lemma 8.0.8 gives that

\begin{equation} \{r_1, r_2,..., r_{\varphi(p^m)}\} = \{i \leq p^m:\gcd(i, p) = 1\}.\label{Eq_8_4}\tag{8.0.4} \end{equation}

Also recall that

\begin{equation*} \left(\frac{a}{p^m}\right)_b=.\overline{q_1q_1\cdots q_{\varphi(p^m)}}, \end{equation*}

and that by Lemma 8.0.11, \(q_i = 0\) if and only if \(r_i \equiv 0\pmod{b}.\) Note that there are exactly

\begin{equation*} \left\lfloor\frac{p^m}{b}\right\rfloor-\left\lfloor\frac{p^m}{bp}\right\rfloor=\left\lfloor\frac{p^m}{b}\right\rfloor-\left\lfloor\frac{p^{m-1}}{b}\right\rfloor \end{equation*}

elements of \(\{i \leq p^m: \gcd(i, p) = 1\}\) which are divisible by \(b.\) Thus using the set equality (8.0.4), we have that there are exactly \(\lfloor p^m/b\rfloor-\lfloor p^{m-1}/b\rfloor\) elements of \(\{r_1, r_2,..., r_{\varphi(p^m)}\}\) divisible by \(b.\) Appealing to Lemma 8.0.11 we then have that there are \(\lfloor p^m/b\rfloor-\lfloor p^{m-1}/b\rfloor\) of \(q_1, q_2,..., q_{\varphi(p^m)}\) such that \(q_j=0.\)

Note that while we record the \(q_i = 0\) case because of its simplicity, the method can be applied to count any value of \(q_i\) that is desired by using the appropriate case of Lemma 8.0.10.