Rational numbers have repeating decimal expansions
A couple of days ago a good friend of mine asked me for help on a more algebraic problem (I have studied more mathematical analysis), which I found cute, so I decided to write up proper proofs for it. The statement of the theorem is as follows:
A real number is rational if and only if its decimal expansion is repeating or terminating.
Background
Here I introduce the basic objects that the proof uses, in an attempt to make it more accessible and for more people to appreciate it.
Natural numbers and integers
When one begins their study of any type of mathematics, they often begin by counting. Counting uses the counting numbers; \(1\), \(2\), \(3\), \(\dots\). These are also known as natural numbers, often denoted by \(\mathbb{N}\) in mathematics. We then tend to add zero, the count of nothing, and then start counting backwards, to get the set of whole numbers, or integers, denoted by \(\mathbb{Z}\); the first couple are \(0\), \(1\), \(-1\), \(2\), \(-2\), \(\dots\).
Rational numbers
We then continue to construct more numbers. What if we divide an object between a number of people? The next natural type of number is called a rational number, denoted by \(\mathbb{Q}\). Although it is possible to enumerate them all (in the sense of listing them one-by-one), we have to choose an enumeration, and it is not completely obvious. Instead, we will give a general description of all rational numbers as the ratio of a whole number and a natural number. In other words, a number is rational if we can express it as \(p/q\) where \(p\) is a whole number, and \(q\) is a natural number, in mathematical notation, \(p\in\mathbb{Z}\) and \(q\in\mathbb{N}\) (where the \(\in\) means "in"). In other words, rational numbers are fractions. Examples of these are \(5/1\), \(33/20\), \(4/2\), \(42/7\), \(-99/17\), and so forth.
So all natural numbers are whole numbers, and all whole numbers are rational numbers. But what comes after rational numbers?
Real and irrational numbers
The next set of numbers is called the set of real numbers, these are numbers that lie anywhere on the number line, or can be written as any type of decimal (infinite, or finite in length). Examples of these are \(\pi\); the ratio of the circumference of a circle to its diameter, \(e\); the base of the natural logarithm, and \(\sqrt{2}\). Real numbers are often denoted by \(\mathbb{R}\), and the set of numbers that are real but not rational are called the set of irrational numbers, and are denoted by \(\mathbb{R}\setminus\mathbb{Q}\) (where the \(\setminus\) stands for "except for").
The theorem
The content of the theorem is that any rational number, and only a rational number, has a repeating or terminating decimal expansion. A decimal expansion of the number, is if we write it in the decimal system, for instance \(2.365\), these can also go forever, such as \(1.41421356\dots\). This means that when we write any rational number such as \(1/3\) as a decimal, we get \(1.3333\dots\), where the decimal repeats with infinitely many threes, as opposed to a seemingly random sequence of numbers (as is the case with \(\pi\), which is \(3.14159265\dots\)). The statement also says that any irrational number must have a non-repeating and non-terminating decimal expansion. From now on, I will refer to repeating or terminating decimal expansions as simply repeating decimals, as a terminating decimal can be thought of one that repeats with infinitely many zeroes.
Proof that repeating decimals represent rational numbers
We first prove the backwards case, that if a decimal is repeating, then it represents a rational number.
Intuition
Suppose we have a decimal such as \(1/3=0.33333\dots\). There is a commonly known neat trick to convert this to a fraction. First we multiply it by \(10\), or \(100\), or with the power of ten corresponding to the number of repeating digits. We then subtract one copy of the original number, which gets rid of the repeating part, and simplify to get a fraction. For instance, if \(x=1.31313131\dots\), we may proceed as:
\[ \begin{aligned} x &= 1.31313131\dots \\ 100x - x &= 130 \\ 99x &= 130 \\ x &= 130/99. \end{aligned} \]
In fact, this works for any decimal which repeats on the right of the decimal point. But what if there are some non-repeating decimals on the right before it starts repeating, such as if \(z=4.21666666\dots\), then we can simply multiply by a power of ten, and then perform the same trick, as in the example:
\[ \begin{aligned} z &= 4.21666666\dots \\ 100x &= 421.66666666\dots \\ 10(100x) - (100x) &= 3795 \\ 1000x - 100x &= 3795 \\ 900x &= 3795 \\ x &= 3795/900. \end{aligned} \]
This trick now works for any repeating decimal. If the decimal is terminating, with \(n\) digits, we may simply multiply by \(10^n\) to get a whole number, and our number is this whole number divided by \(10^n\). For instance, if \(w=5.44\), then multiply by \(100\) to get \(544\), and we have \(w=544/100\).
Formal proof
Given a repeating decimal \(x=a.b\overline{c}\) where \(a\), \(b\), and \(c\) are groups of digits, we can separate it into the non-repeating, and repeating parts. First let \(n=\lceil{\log_{10}b\rceil}\), the number of digits of \(b\), and multiply by \(10^n\). We are now left with something of the form \(10^nx=ab.\overline{c}\). If the decimals terminate, then \(c=0\), and the proof is complete. So now without loss of generality, assume \(c\neq0\) and \(x=a.\overline{c}\).
Now suppose \(c\) has \(m\) digits, then multiply by \(10^m-1\) and we are left with an integer, that straight away gives a fraction. To see this, we may write it as a geometric series:
\[ \begin{aligned} x &= a + c + 10^{-m}c + 10^{-2m}c + \cdots \end{aligned} \]
Now multiply by \(10^m-1\) to get:
\[ \begin{aligned} (10^m-1)x &= (10^m-1)a + (10^mc + c + 10^{-m}c + \cdots) \\ &\quad- (c + 10^{-m}c + 10^{-2m}c + \cdots) \\ &= (10^m-1)a + 10^mc. \end{aligned} \]
Since \(c\) has \(m\) digits, \(10^mc\) is an integer. Therefore, \(x=((10^m-1)a+10^mc)/(10^m-1)\), where \((10^m-1)a+10^mc\) is an integer and \(10^m-1\) is a natural number, as required.
Proof that rational numbers have repeating decimal expansions
This is the hard part. I originally came up with a proof working backwards with the above trick, but it is somewhat complicated, so I later produced a proof using another, simpler method.
First proof
The first way of proving this uses the above trick backwards, in other words, given a rational number, we try to change its denominator to be of the form \(10^n\) or \(10^n(10^m-1)\).
To do this, suppose \(x=p/q\) where \(p\in\mathbb{Z}\) and \(q\in\mathbb{N}\). Let the prime decomposition of \(q\) be \(2^{l_1}3^{l_2}5^{l_3}p_4^{l_4}p_5^{l_5}\dots\) where \(p_i\) is the \(i\)-th prime and \(l_i\) is a non-negative integer, the power of the \(i\)-th prime. Now let \(n=l_1\cdot l_3\), these are the primes not co-prime to \(10\). Furthermore, since \(3^{l_2}p_4^{l_4}p_5^{l_5}\cdots\) is co-prime to \(10\), Euler's theorem guarantees that \(10^{\varphi(3^{l_2}p_4^{l_4}p_5^{l_5}\cdots)-1}-1=0\pmod{3^{l_2}p_4^{l_4}p_5^{l_5}\cdots}\), (where \(\varphi\) is Euler's totient function) so we can let \(m=\varphi(3^{l_2}p_4^{l_4}p_5^{l_5}\cdots)-1\). This is of the form discussed above, and hence proves the result.
Second proof
This method manually computes the decimal places, and reasons why these must repeat. Suppose \(x=p/q\) where \(p\in\mathbb{Z}\) and \(q\in\mathbb{N}\). To compute the parts on the left hand side of the decimal point, we simply compute \(p\ \text{div}\ q=0\) (where \(\text{div}\)) denotes quotient). We can then compute the next digit (the one immediately on the right of the decimal point) by multiplying the remainder by \(10\), and taking the quotient under \(q\). To get the next digit, we again multiply the remainder of this by \(10\) and take the quotient under \(q\). Note now that we only ever use the remainder in the next step, but it is always between \(0\) and \(q-1\), with \(q\) is fixed. Therefore, by the pigeonhole principle, we must eventually get back to a remainder we have already visited, and start looping, giving the required repeating decimal. This completes the proof.
The procedure described here is essentially long division.