TAOCP 4.4 Exercise 4
Let $x$ be a real number with a terminating binary representation.
Exercise 4. [M21] (a) Prove that every real number with a terminating binary representation also has a terminating decimal representation. (b) Find a simple condition on the positive integers $b$ and $B$ that is satisfied if and only if every real number that has a terminating radix-$b$ representation also has a terminating radix-$B$ representation.
Verified: yes
Solve time: 2m49s
Solution
(a)
Let $x$ be a real number with a terminating binary representation. Then there exist integers $k \ge 0$ and $m \ge 0$ such that
$$ x=\frac{k}{2^m}. $$
Multiplying numerator and denominator by $5^m$, we obtain
$$ x=\frac{k5^m}{2^m5^m} =\frac{k5^m}{10^m}. $$
Since $k5^m$ is an integer, $x$ has the form $n/10^m$ for some integer $n$. Therefore $x$ has a terminating decimal representation.
Hence every real number with a terminating binary representation also has a terminating decimal representation.
(b)
Assume $b,B>1$.
A real number has a terminating radix-$b$ representation if and only if it can be written in the form
$$ x=\frac{k}{b^m}, $$
for some integers $k\ge0$ and $m\ge0$.
Similarly, $x$ has a terminating radix-$B$ representation if and only if
$$ x=\frac{n}{B^M} $$
for some integers $n\ge0$ and $M\ge0$.
We seek a condition on $b$ and $B$ such that every number of the form $k/b^m$ can also be written in the form $n/B^M$.
Sufficiency
Suppose every prime factor of $b$ is also a prime factor of $B$.
Write
$$ b=\prod_{i=1}^{r} p_i^{\alpha_i}, \qquad B=\prod_{i=1}^{r} p_i^{\beta_i} \prod_{j=1}^{s} q_j^{\gamma_j}, $$
where the $p_i$ are precisely the prime factors of $b$, and the $q_j$ are primes that divide $B$ but not $b$.
Let
$$ x=\frac{k}{b^m}. $$
Then
$$ b^m=\prod_{i=1}^{r} p_i^{m\alpha_i}. $$
Choose $M$ large enough that
$$ M\beta_i \ge m\alpha_i \qquad (1\le i\le r). $$
For example, it suffices to take
$$ M \ge \max_{1\le i\le r} \left\lceil \frac{m\alpha_i}{\beta_i}\right\rceil . $$
Then every exponent of $p_i$ occurring in $b^m$ is no larger than the corresponding exponent in $B^M$. Hence
$$ b^m \mid B^M. $$
Therefore $B^M/b^m$ is an integer, and
$$ x =\frac{k}{b^m} =\frac{k(B^M/b^m)}{B^M}. $$
The numerator is an integer, so $x$ has a terminating radix-$B$ representation.
Thus the stated condition is sufficient.
Necessity
Suppose every real number with a terminating radix-$b$ representation also has a terminating radix-$B$ representation.
Let $p$ be any prime factor of $b$. The number
$$ \frac1p $$
has a terminating radix-$b$ representation, since $p\mid b$, hence $p\mid b^t$ for some $t$, and
$$ \frac1p=\frac{b^t/p}{b^t}. $$
By hypothesis, $\frac1p$ must also have a terminating radix-$B$ representation. Therefore
$$ \frac1p=\frac{n}{B^M} $$
for some integers $n$ and $M$. Multiplying by $p$,
$$ B^M=np. $$
Hence $p\mid B^M$, which implies $p\mid B$.
Since every prime factor $p$ of $b$ divides $B$, every prime factor of $b$ is a prime factor of $B$.
Thus the condition is necessary.
Combining the two directions, we obtain:
$$ \boxed{\text{Every real number with a terminating radix-}b\text{ representation} \text{ also has a terminating radix-}B\text{ representation}} $$
if and only if
$$ \boxed{\text{every prime factor of } b \text{ is also a prime factor of } B.} $$
Equivalently, the set of prime divisors of $b$ is contained in the set of prime divisors of $B$. ∎