I am currently working my way through "A Concise Introduction to Pure Mathematics" by Martin Liebeck, and have been stuck on an excersise for a couple of days now. The question reads:
"Show that for an integer n $\geq2$, the period of the decimal expression for the rational number $\frac{1}{n}$ is at most $n-1$."
I've been trying to solve this without making any substantial progress. And yes, I have seen explanations that when performing a long division the decimal expression either terminates to $0$ or eventually repeats. But I haven't seen any proof of this that I've been satisfied with, even less do I know how to formalise this type of proof. I've tried to write out long division with arbitrary digits, but that obviously turns out to be too much of a hassle and basically impossible to draw any conclusions from.
Best Answer
When you divide an integer by $n$, there are only $n$ possible remainders. If you ever get a remainder of $0$ when calculating the decimal expansion of $\frac1n$, you’re done: you’ve found the terminating decimal expansion of $\frac1n$. Suppose, then, that you never get a remainder of $0$. There are only $n-1$ other possible remainders, so after at most $n-1$ steps you must repeat a remainder.
Say that at step $k$ the division produces digit $d_k$ in the quotient and remainder $r_k$. If $r_k$ is never $0$, it is not possible for the $n-1$ remainders $r_{m+1},r_{m+2},\ldots,r_{m+n-1}$ all to be different from $r_m$, so there must be a step $m$ such that $r_m=r_{m+k}$ for some $k\le n-1$. The mechanics of long division then ensure that the digits in the quotient will repeat: $d_{m+1}=d_{m+k+1}$, because you’re dividing $n$ into the same remainder. And since you’re performing the same division, you’ll get the same remainder again: $r_{m+1}=r_{m+k+1}$. And so on: the sequence of digits in the quotient and remainders starting at step $m+k$ must be identical to the sequence starting at step $m$. Thus, the sequence of digits from $d_{m+1}$ through $d_{m+k}$ must be the same as the sequence from $d_{m+k+1}$ through $d_{m+2k}$, which must then be the same as the sequence from $d_{m+2k+1}$ through $d_{m+3k}$, and so on, because the sequences of remainders from $r_m$ through $r_{m+k-1}$, from $r_{m+k}$ through $r_{m+2k-1}$, from $r_{m+2k}$ through $r_{m+3k-1}$, and so on are the same.
Thus, the sequence $d_{m+1}d_{m+2}\ldots d_{m+k}$ of $k$ digits repeats ad infinitum, and $k$ is at most $n-1$.