Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
    
"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. –  Arturo Magidin Jun 19 '11 at 20:25
1  
the title is quite misleading: the question has nothing to do with continued fractions, it seems –  Grigory M Jun 19 '11 at 20:26
    
@Arturo Magidin: Oh, thank you for pointing that out and the correction as well. –  Chan Jun 19 '11 at 20:27
    
@Grigory M: You're right, thank you. I think Arturo Magidin already edited it. –  Chan Jun 19 '11 at 20:28

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Thank you. I don't know why I still don't see it yet. –  Chan Jun 19 '11 at 21:27
    
@Chan: Try writing out $$(3\cdot 10^{3-5})+(9\cdot 10^{3-6})+(2\cdot 10^{3-7})$$ as a decimal. –  Zev Chonoles Jun 19 '11 at 21:45
    
Thanks again. –  Chan Jun 19 '11 at 21:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.