2
$\begingroup$

In the textbook "Elementary Number Theory" by Kenneth H. Rosen,

Theorem 12.3. (page 472) The real number $\alpha$, $0 \leq \alpha \lt 1$, has a terminating base $b$ expansion if and only if $\alpha$ is rational and can be written as $\alpha = \dfrac{a}{s}$, where $0 \leq r < s$, and every prime factor of $s$ also divides $b$.

Proof
First suppose that $\alpha$ has a terminating base $b$ expansion, $$\alpha = (.c_1c_2 \ldots c_n)_b$$ Then $$\alpha = \dfrac{c_1}{b} + \dfrac{c_2}{b^2} + \ldots + \dfrac{c_n}{b^n} = \dfrac{c_1b^{n-1} + c_2b^{n-2} + \ldots + c_n}{b^n}$$ so that $\alpha$ is rational, can be written with a denominator divisible only by primes dividing b.
Conversly, suppose that $0 \leq \alpha < 1$, and $$\alpha = \dfrac{r}{s}$$ where each prime dividing $s$ also divides $b$. Hence, there is a power of $b$, say, $b^{N}$, that is divisible by $s$. Then $$b^N\alpha = b^N\dfrac{r}{s} = ar,$$ where $sa = b^N$, and $a$ is a positive integer because $s|b^N$. Now let $(a_ma_{m-1}\ldots a_1a_0)_b$ be the base $b$ expansion of $ar$. Then $$\alpha = \dfrac{ar}{b^N} = \dfrac{a_mb^m + a_{m-1}b^{m-1} + \ldots + a_1b + a_0}{b^N}$$ $$= a_mb^{m-N} + a_{m-1}b^{m-1-N} + \ldots + a_1b^{1-N} + a_0b^{-N}$$ $$= (.00\ldots a_ma_{m-1} \ldots a_1a_0)_b$$ Hence $\alpha$ has a terminating base $b$ expansion. $\square$

For the only if proof I got it straight, but for the if I don't understand how the author goes from: $$= a_mb^{m-N} + a_{m-1}b^{m-1-N} + \ldots + a_1b^{1-N} + a_0b^{-N}$$ to $$= (.00\ldots a_ma_{m-1} \ldots a_1a_0)_b$$

Where did $.00$ come from? Besides, "....Now let $(a_ma_{m-1}\ldots a_1a_0)_b$ be the base $b$ expansion of $ar$" From here, did the author assume that the expansion of $ar$ is terminating? I was confused here because the way it was written. If it's not terminating, or periodic, should I write it as $(a_0a_1 \ldots)_b$?

Thank you,

  • 0
    "iff" is supposed to be an abbreviation for "if and only if"; an "iff" is divided into two implications, the "if", and the "only if". In this case, the first part of the proof is the "only if" part, and the second is the "if" part. So it looks like you got the "only if" part and are having trouble with the "if" part. (That is, you are having trouble showing that $\alpha$ has a terminating expansion **if** it can be written as $\frac{r}{s}$, etc.2011-06-19
  • 1
    the title is quite misleading: the question has nothing to do with [continued fractions](http://en.wikipedia.org/wiki/Continued_fraction), it seems2011-06-19
  • 0
    @Arturo Magidin: Oh, thank you for pointing that out and the correction as well.2011-06-19
  • 0
    @Grigory M: You're right, thank you. I think Arturo Magidin already edited it.2011-06-19

1 Answers 1

3

The $0$'s are there because $N$ is not necessarily equal to $m-1$. The number $$a_mb^{m-N} + a_{m-1}b^{m-1-N} + \ldots + a_1b^{1-N} + a_0b^{-N}$$ written in base $b$ will have its first non-zero digit at the $m-N$'th place, i.e. $a_m$ is in the $b^{m-N}$'s place. So, slightly more explicitly, the number is equal to $$= (.\underbrace{00\ldots0}_{m-N-1}a_ma_{m-1} \ldots a_1a_0)_b$$

Also, presumably the author has already proven that the base $b$ expansion of an integer (such as $ar$) always terminates.

  • 0
    Thank you. I don't know why I still don't see it yet.2011-06-19
  • 0
    @Chan: Try writing out $$(3\cdot 10^{3-5})+(9\cdot 10^{3-6})+(2\cdot 10^{3-7})$$ as a decimal.2011-06-19