I can't solve the following problem.
Show that for an integer $n \ge 2$, the period of the decimal expression for the rational number $\frac{1}{n}$ is at most $n-1$.
On StackExchange I already found an answer to this question
When you carry out long division of 1 by n, either the process terminates and you have a finite decimal, or you obtain a sequence of remainders among 1,2,…,n−1. Once a remainder is repeated, the decimals must start repeating too. Since there are only n−1 possible remainders, the repetition must occur by the nth decimal place at the latest. The period is then the distance between this and the previous occurrence of the same remainder, which must be at most n−1 decimal places.
I do not understand this proof ? Could you please help me with the following question ?
- What are the remainders ?
- Why do we obtain a sequence of remainders among 1,2…,n-1 ?
Best Answer
Take an example, say $\frac 1{13}$.
$$ \require{enclose} \begin{array}{r} 0.0769.. \\[-3pt] 13 \enclose{longdiv}{1.000000} \\[-3pt] \underline{-91}\phantom{2222} \\[-3pt] \color{blue}{9}0\phantom{222} \\[-3pt] \underline{-78}\phantom{211} \\[-3pt] \color{blue}{12}0\phantom{22} \\[-3pt] \underline{-117}\phantom{22} \\[-3pt] \color{blue}{3}0\phantom{2} \\[-3pt] \vdots\phantom{22} \end{array} $$
This sequence $9,12,3$ and so on are the sequence of remainders referred to in the answer. Now, the point is that if the remainder $9$ came again, then doing long division will just repeat the same remainder sequence again (so if you have $9$, you will always bring down the $0$, subtract $78$ and get $12$ as the next remainder, and then $3$ as the remainder after that, and so on).
Note that because each remainder is coming from division by $13$, the remainders are all between $0$ and $12$. Similarly, when we divide by $n$, we get remainders that would be between $0$ and $n-1$.
So, if you want to show that the remainder sequence repeats, then all you need to do, is show that some pair of remainders are the same in the remainder sequence, between $0$ and $n-1$.
Note that if $0$ is a remainder at some point of time , then the long division stops, and there is no repeating part at all (or, depending on which way you look at it, a repeating part of period $1$).
If $0$ is not a remainder, then there are only $n-1$ possible remainders,namely $1,2,...,n-1$. By the $n$th stage, one of these numbers must have occurred twice , since $n>n-1$. However, that shows that the repeating part must come from within the first $n-1$ divisions, so can't be of period more than $n-1$.
Example : keep going with $13$, you eventually get $0.\overline{076923}$, with remainder sequence $9,12,3,4,1,10,9,12,3,...$ where the $9$ repeated by the sixth step, so everything after that repeats as well, giving the repeated decimal.