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.

I'm currently reading Elementary Number Theory and Its Applications by Kenneth H. Rosen. In chapter 12 - Decimal Fraction, he provided a proof about the period length of the base $b$ is $\mathrm{ord}_n b$. and pre-period length. However, I found this proof so confusing, and it's not short, so I'm looking for an alternative proof for this theorem. Any reference or information would be greatly appreciated.

This is the original theorem from Rosen's book.
Theorem 12.4 - page 474

Let $b$ a positive integer. Then $a$ periodic base $b$ expansion represents a rational number. Conversely, the base $b$ expansion of a rational number either terminates or is periodic. Futher, if $0 < \alpha < 1$, $\alpha = r/s$, where $r$ and $s$ are relatively prime positive integers, and $s = TU$, where every prime factor of $T$ divides $b$ and $(U,b) = 1$, then the period length of base $b$ expansion of $\alpha$ is $\mathrm{ord}_U b$, and the pre-period length is $N$, where $N$ is the smallest positive integer such that $T|b^N$.

Furthermore, is there an alternative presentation of this theorem? I was really confused about what this theorem is all about.

Thanks,

share|improve this question
2  
The more you can elaborate the better an answer you may receive. What precisely is "confusing" and why do you seek an alternative presentation? Spending an extra few minutes composing your questions to provide these essential contextual details might save you days if not weeks of struggles. Don't rob yourself of this potential help by omitting essential details in the question. –  Bill Dubuque Apr 26 '11 at 1:37
    
@Bill Dubuque: Thanks for your advice. I take your words! –  Chan Apr 26 '11 at 3:41
add comment

3 Answers

up vote 4 down vote accepted

Here is something about period length but nothing about pre-period length.


The first question is whether a fraction is periodic or not. If it's not periodic it's of the form $x/b^r$ for example 36.542 = 36542/1000 = 18271/500. The contrapositive of this tells us that if a fraction is of the form $x/y$ with $b \not | y$ then the expansion is periodic, for example in base 10: $10 \not | 73$ so 15/73 is periodic: $0.2054794520547945\ldots$.

It suffices to consider only fractions between 0 and 1 so let's do that. How do we compute the base $b$ expansion of a fraction? For example how do we compute $0.14285714285714285\ldots$ from $1/7 = p/q$ multiply both sides by 10 and throw away the remainder to get the first digit $d = \text{floor}(\frac{b p}{q})$. To get the rest of the digits we just do the same process on $r/q$, where $r$ is the remainder of the division $\frac{b p}{q}$. Here is an example of this

p q d r
1 7 1 3
3 7 4 2
4 7 2 6
8 7 8 4
4 7 5 5
5 7 7 1
...

and if you read the digits column we have the correct digits.

So how can we use this idea of repeatedly applying the division algorithm to find the period length? It seems like a difficult problem so for a warm up lets just find out when the period has length 1, for example $1/3 = 0.333\ldots$ has that property. Why? Well it's obvious from the table

p q d r
1 3 3 1
1 3 3 1
...

It's got period 1 because $p = r$, the remainder of dividing $bp$ by $q$ is $p$, $bp \equiv p \pmod q$. In fact it turns out this solves the problem completely - 1/7 is periodic with period 6 in base 10 because it is periodic with period 1 in base 10^6! So what is the smallest $r$ such that $b^r p \equiv p \pmod q$? It's just that ord thing that was mentioned.

share|improve this answer
    
Thank you. But you did half and Ross Millikan did half. How could you pick the answer! You guys confused me now ^_^! –  Chan Apr 26 '11 at 3:49
add comment

For the pre-period part, perhaps it is easier if we specialize to base 10. Then $T=2^a5^b$ has all the factors of $2$ and $5$ in $s$, and $U$ has all the other factors. It says you need to find the smallest $N$ such that $T$ divides $10^N$, which is just the maximum of $a$ and $b$. The repeat comes about because you are finding the smallest number of the form $999\ldots000\ldots$ that $s$ divides into. The number of zeros is just $N$ and the number of nines is enough to take care of the other factors of the number. You can see this with $\frac{1}{3}=0.33333, \frac{1}{6}=0.1666666, \frac{1}{12}=0.083333$, where $\frac{1}{6}$ has one digit after the decimal point before the repeat starts (the pre-period) and one factor of $2$, and $\frac{1}{12}$ has two digits before the repeat starts and two factors of $2$. I'd suggest trying some more examples.

share|improve this answer
    
I will try some more examples to see the how the pattern works out. Thank you. –  Chan Apr 26 '11 at 3:50
add comment

Here's a simple proof. If $\rm\:\alpha\in \mathbb R\cap(0,1)\:$ is periodic in radix $\rm\:b\:$ with preperiod,$\:$ period lengths $\rm\:n,m\:$ then, since multiplying or dividing by $\rm\:b^n\:$ and $\rm\:b^k-1\:$ corresponds to shifting left or right by the preperiod and period, $\:$ it follows that $\rm\:\alpha\:$ is rational, expressible with denominator $\rm\:b^n\ (b^k-1)\:,\ $ so its least denominator $\rm\: s\ |\ b^n\ (b^k-1)\:,\:$ so $\rm\ s = tu,\ t\ |\ b^n,\ u\ |\ b^n-1\:$ by Euclid's Lemma or unique factorization, utilizing $\rm\:\ (b^n,\:b^k-1)\ =\ 1\:.\ $ In a bit more detail

$\rm\quad\quad\quad\quad\quad\ \ \alpha\ =\ 0\:.a\:\overline{c}\ =\ 0\:.a_1a_2\cdots a_n\:\overline{c_1c_2\cdots c_k}\ $ in radix $\rm\:b\:$

$\rm\quad\iff\quad \beta\ :=\ b^n\: \alpha - a\ =\ 0\:.\overline{c_1c_2\cdots c_k}$

$\rm\quad\iff\quad b^k\: \beta\ =\ c + \beta$

$\rm\quad\iff\quad (b^k-1)\ \beta\ =\ c$

$\rm\quad\iff\quad (b^k-1)\ b^n\: \alpha\ \in\ \mathbb Z$

share|improve this answer
add comment

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.