Prove that for an integer n larger than or equal to 2, the period for the decimal expression of the rational number $\frac{1}{n}$ is at most n -1.

Question

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.

Answer 1

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$.

Answer 2

Formalizing this may take a bit of work but:

When you find the decimal expansion of $n$ you start by dividing $n$ into $10$ and taking the remainder. You then take the remainder and multiply it by $10$. ANd you divide $n$ to that and take the remainder and repeat. And you do this an infinite number of times.

Now three things:

1) If you have get a remainder of $0$ then everything ends and this is a terminating decimal. A terminating decimal is actually one with an infinite number of zeros. This has a period of $1 = 2- 1\le n-1$.

2) If you ever reach a point were you get a remainder that you had already gotten before, then when you multiply by $10$ you we get the same thing you got before and when you divide $n$ into it the next remainder you get this time, will be the same as the next remainder you got last time. And so on. So if you ever get the same remainder twice then from that point on everything will repeat in a period pattern.

(When you formally write this up, you can refer to this as the Principle of Induction)

3) You WILL reach a point were you get a remainder that you had already gotten before.

If you never get $0$ as a remainder there are only $n-1$ possible remainders you can ever get. So within $n-1$ steps you will repeat a remainder. (Formally we can call that the Pigeon Hole Principal.)

And so the period will repeat within $n-1$ steps and the period can be at most $n-1$.

Now, write that up in formal terms.

(The most tedious part that I personally hate is describing the process of $10r_k = d_{k+1}n + r_{k+1}$ to describe taking $10$ times the remainder you got in the $k$th step, dividing it by $n$ to get $d_{k+1}$, the $k+1$th decimal, and $r_{k+1}$ then $k+1$th remainder. But even though it is tedious it is straitforward.)