Today I will be sharing my proof that the decimal representations of rational numbers must repeat. This proof is based on a simple idea, but turned out to be pretty involved, with several parts.
The fundamental idea can be illustrated using long division. Consider the rational number $\frac{8}{7}$. We can find its decimal representation using the long division calculation below.
Each step of this calculation begins with the remainder from the previous step (circled in red). Since the remainder on division by 7 must be an integer between 0 and 6, there are only 7 possible remainders. Thus, the remainder must repeat within no more than 8 steps. Once it repeats, the calculation will begin to cycle, causing the decimal representation it produces to repeat, as this one does.
Now let’s prepare for the more formal proof by proving two lemmas. I think the first of these is quite interesting and not immediately obvious. The second one is obvious, but I wanted to be assured of it, since it is vital to the main proof.
Lemma 1: Given a rational number $x$, if there exist two distinct digits $d_1$ and $d_2$ in the decimal representation of $x$ such that the sequence of digits following $d_1$ is the same as the sequence of digits following $d_2$, then the decimal representation of $x$ repeats.
Assume that two such digits exist and let the one which appears first be called $d_1$. Then the decimal representation of $x$ begins as follows: $s_1.s_2d_1s_3d_2$, where $s_1$ is a sequence of at least one digit and $s_2$ and $s_3$ are sequences of zero or more digits.
Now, since the sequence of digits following $d_2$ is the same as the sequence of digits following $d_1$, the decimal representation must continue: $s_1.s_2d_1s_3d_2s_3d_2$. Yet this further specifies the sequence of digits following $d_1$, so the same digits must appear again in the sequence following the initial appearance of $d_2$, yielding $s_1.s_2d_1s_3d_2s_3d_2s_3d_2$. This process (illustrated below) will continue infinitely, so $x=s_1.s_2d_1\overline{s_3d_2}$.
Thus, the lemma holds.
(I realize the notation was a little sloppy here, with $d_2$ representing both a digit and a digit with its position, but I couldn’t find a good way to fix it.)
Lemma 2: Let $x$ be a non-negative rational number such that $x=\frac{n}{m}$, where $n$ and $m$ are non-negative integers and $m\neq 0$. There is no more than one way to represent $x$ as a mixed number $q\frac{r}{m}$ such that $q$ and $r$ are non-negative integers and $r<m$.
Suppose $\frac{n}{m}=q_1\frac{r_1}{m}$ and $\frac{n}{m}=q_2\frac{r_2}{m}$ where $q_1$, $q_2$, $r_1$, and $r_2$ are non-negative integers and $r_1,r_2<m$.
It follows that $q_1+\frac{r_1}{m}=q_2+\frac{r_2}{m}$ and thence that $q_1-q_2=\frac{r_1-r_2}{m}$.
Since $0<r_1<m$ and $0<r_2<m$, $-1<\frac{r_1-r_2}{m}<1$.
Thus $-1<q_1-q_2<1$, from which it follows that $q_1=q_2$, since $q_1$ and $q_2$ are integers.
Hence $\frac{r_1-r_2}{m}=0$, so $r_1=r_2$.
Therefore, both mixed numbers are the same, and the theorem holds.
Finally, we come to the main theorem.
Proposition: If $x$ is a rational number, then the decimal representation of $x$ repeats.
For any $x$, if the decimal representation of $x$ repeats, then the decimal representation of $-x$ repeats. Thus, it is sufficient to show that the theorem holds for all non-negative $x$.
Let $x$ be a non-negative rational number. Then $x=\frac{n}{m}$ for some non-negative integers $n$ and $m$, where $m\neq 0$.
The fraction $\frac{n}{m}$ can be expressed as a mixed number $q_1\frac{r_1}{m}$ such that $q_1$ and $r_1$ are non-negative integers and $r_1<m$. By Lemma 2, there is only one way to do this.
Using algebra we have: $$q_1\frac{r_1}{m}=q_1+\frac{r_1}{m}=q_1+\frac{r_1}{m}\left(\frac{10}{10}\right)=q_1+\frac{10r_1}{m}\left(\frac{1}{10}\right)$$
As above, the fraction $\frac{10r_1}{m}$ can be expressed uniquely as a mixed number $q_2\frac{r_2}{m}$ such that $q_2$ and $r_2$ are non-negative integers and $r_2<m$.
This yields $$q_1+\frac{10r_1}{m}\left(\frac{1}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)\text{.}$$
Notice that $q_2$ has only one digit, since $0\leq\frac{r_1}{m}<1$ and $0\leq q_2\leq\frac{10r_1}{m}$. Notice also that $0\leq\frac{r_2}{m}\left(\frac{1}{10}\right)<\frac{1}{10}$, since $0\leq\frac{r_2}{m}<1$. This means that $q_2$ is the tenths-place digit of the decimal expansion of $x$.
The algorithm can be continued as shown below, $$q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+\frac{r_2}{m}\left(\frac{1}{10}\right)\left(\frac{10}{10}\right)$$ $$=q_1+q_2\left(\frac{1}{10}\right)+\frac{10r_2}{m}\left(\frac{1}{100}\right)=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+\frac{r_3}{m}\left(\frac{1}{100}\right)$$ $$=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+\frac{r_3}{m}\left(\frac{1}{100}\right)\left(\frac{10}{10}\right)=q_1+q_2\left(\frac{1}{10}\right)+q_3\left(\frac{1}{100}\right)+q_4\left(\frac{1}{1000}\right)+\frac{r_4}{m}\left(\frac{1}{1000}\right)…$$ with $q_i\frac{r_i}{m}$ for $i>1$ always the unique mixed number representation of the fraction $\frac{10r_{i-1}}{m}$ such that $q_i$ and $r_i$ are non-negative integers and $r_i<m$. By logic similar to that above, when $i>1$, $q_i$ will always be a digit of the decimal representation of $x$, with its value given by the power of $\frac{1}{10}$ by which it is multiplied.
Since, for all $i$, $r_i$ is a non-negative integer less than $m$, there are only $m$ possible values of $r_i$. This means that, among the infinite values of $r_i$, there must exist distinct $r_j$ and $r_k$ such that $r_j=r_k$. (ETA: By the Pigeonhole Principle!)
Since the mixed number representations used by the algorithm are unique, if $r_j=r_k$, then $q_{j+1}=q_{k+1}$ and $r_{j+1}=r_{k+1}$. By induction, it therefore follows that $q_{j+h}=q_{k+h}$ for all $h$. Since, when $i>1$, each $q_i$ is a digit of the decimal representation of $x$, it follows by Lemma 1 that decimal representation of $x$ repeats.
Therefore the theorem holds.
I hope this makes some measure of sense. I had a lot of trouble making this proof lucid, and eventually I had spent too much time working on. Those whose eyes did not glaze over will note that the algorithm I employed here is essentially long division. In developing it, I did not set out specifically to reproduce the long division algorithm, and I was intrigued when I noticed they are basically the same. Here is our long division problem annotated to show the relationship:
Very thorough. I’ve only ever been more casual than you, and have just talked about long division, so your proof, which shows that long division is possible, is nice.
As an undergraduate, I once gave a talk – maybe several days’ worth; I don’t remember – in a class by Irving Kaplansky about Hilbert’s Problems. (Some of your readers may know Irving’s daughter, the singer Lucy Kaplansky.) When I was done, Kaplansky came up to me and said, “That was nice, but there was one serious mistake.” Trying to stay calm and look relaxed, I said, “Yes?” Kaplansky said, ” you used the Pigeonhole Principle.” I nodded, “Yes.” Kaplansky said firmly, “When you use the Pigeonhole Principle, you have to CALL IT the Pigeonhole Principle. It’s too good a name not to use.” He smiled and hurried out of the room, and my heartbeat began to return to normal.
I’m afraid, Olly, you’ve made a serious mistake.
– Tim
That should have said that at some point or another in the argument, you used the Pigeonhole Principle.
Ah, yes. Well, I don’t know what yours was, but my excuse is that my Swiss-cheesed math knowledge no longer included the information that it is called the Pigeonhole Principle. I remember now, and it is a great name. Do you know if it has the same name in other languages?
I had no reason not to use the word. I just didn’t know it was a rule. Is it really a rule? I don’t know, but I like the idea and the name.
For younger people who have never examined an old roll-top desk, in back of the desktop are an array of open-fronted compartments about the right size to hold letters or, I suppose, pigeons. These are called pigeonholes. Pigeonholing someone is deciding which pigeonhole they belong in – dumping them in some restrictive category. “She was pigeonholed as a political wife, and never taken seriously for her own ideas.”
The Pigeonhole Principle says that if you have at least $n+1$ items (pigeons) to place in $n$ categories (holes), then at least one category contains more than one item.
When you asked that question about other languages, all I knew was that in German it’s Schubfachprinzip, though I learn from Wikipedia that it’s le principle de tissoir in French, which I think I must have met at some point. Both mean more or less the Drawer Principle, and both were used by Dirichlet, who apparently used the example of placing pearls in drawers. (Go figure. Perhaps mathematicians then were richer than we are now.) You have to speak English pretty well to know about pigeonholes, though, and the image of pigeons in holes is so graphic that “pigeonhole principle” has begun migrating to other languages. Wikipedia tells me that it’s now being used in German as “Taubenschlagprinzip,” for instance.
I first met the word in 1970, and immediately thought of old desks, though not all my fellow students did. I’m not certain, but I think that even then people were describing it as placing $n+1$ pigeons in $n$ holes. The professor who introduced me to the idea also used the word Schubfachprinzip, which he glossed as “Shoe box principle.” This was probably some combination of joke and mnemonic – he certainly knew better – but I believed him, and it was years before I learned that wasn’t what the word meant.
From what I can discern reading translations in Wikipedia, lots of languages use some variant on “box principle,” but it is sometimes combined with something about pigeons. For instance, wikipedia.es tells me that in Spanish it’s “el principio de casillas,” and “el principio de las cajas” (words for boxes) and “el principio de Dirichlet,” but also “el principio del palomar,” the pigeon loft principle.
Excellent. I think you are right that the pigeonholes referred to are probably the kind in a desk. I’ve always imagined cubbies inhabited by actual pigeons, though.