When does the decimal representation of 1/d terminate?
Consider the number $\frac{1}{d} \in \mathbb{R}$ for $d \in \mathbb{N}$, and in particular, its decimal representation. For example, $\frac{1}{2} = 0.5, \frac{1}{3} = 0.\bar{3}, \frac{1}{4} = 0.25$, etc. Notice that in some cases the decimal representation of $\frac{1}{d}$ terminates (e.g. $\frac{1}{5} = 0.2$), and in some case it is infinitely long (e.g. $\frac{1}{9} = 0.\bar{1}$). For a particular $d$, can we tell when the decimal representation of $\frac{1}{d}$ terminates, versus when it is infinitely long?
This question came up after a night of poker between me and some friends, in the context of problem #26 from Project Euler. One of my friends claimed that if the prime factors of $d$ are limited to $2$ and $5$ (i.e. one, the other, or both), then the decimal representation of $\frac{1}{d}$ will terminate. Upon a moment of reflection, he also claimed that the converse is true: if $d$ has a prime factor other than $2$ and $5$, then the decimal representation of $\frac{1}{d}$ will be infinitely long.
We looked at a couple examples and couldn't think of a counter-example. My friend said something about this being because we are in the base $10$ number system (and presumably something like $2 \times 5 = 10$). Ok, this is kind of an intuitive explanation for why the claims might be true. But are they really true, and if so, can we prove it?
Computing the decimal representation: long division
To compute the decimal representation of $\frac{n}{d}$ (for $n, d \in \mathbb{N}$), we can use the long division algorithm, which you may remember from grade school. The below example demonstrates long division to compute that $\frac{1}{8} = 0.125$.
$$
\require{enclose}
\begin{array}{rll}
0.\color{orange}{1}\color{teal}{2}\color{purple}{5} && \hbox{} \\[-3pt]
\color{red}{8} \enclose{longdiv}{1.000}\kern-.2ex \\[-3pt]
\underline{-\phantom{0}8\phantom{00}} && \hbox{($\color{red}{8} \times \color{orange}{1} = 8$)} \\[-3pt]
\phantom{0}\color{blue}{2}0\phantom{0} && \hbox{($10 - 8 = \color{blue}{2}$)} \\[-3pt]
\underline{-\phantom{0}16\phantom{0}} && \hbox{($\color{red}{8} \times \color{teal}{2} = 16$)} \\[-3pt]
\phantom{0}\color{blue}{4}0 && \hbox{($20 - 16 = \color{blue}{4}$)} \\[-3pt]
\underline{-\phantom{00}40} && \hbox{($\color{red}{8} \times \color{purple}{5} = 40$)} \\[-3pt]
\phantom{00}0
\end{array}
$$
And the below example demonstrates long division to compute that $\frac{1}{3} = 0.\bar{3}$
$$
\require{enclose}
\begin{array}{rll}
0.\color{orange}{3}\color{teal}{3}\color{purple}{3}\ldots && \hbox{} \\[-3pt]
\color{red}{3} \enclose{longdiv}{1.000\phantom{000}}\kern-.2ex \\[-3pt]
\underline{-\phantom{0}9\phantom{00000}} && \hbox{($\color{red}{3} \times \color{orange}{3} = 9$)} \\[-3pt]
\phantom{0}\color{blue}{1}0\phantom{0000} && \hbox{($10 - 9 = \color{blue}{1}$)} \\[-3pt]
\underline{-\phantom{0}9\phantom{0000}} && \hbox{($\color{red}{3} \times \color{teal}{3} = 9$)} \\[-3pt]
\phantom{0}\color{blue}{1}0\phantom{000} && \hbox{($10 - 9 = \color{blue}{1}$)} \\[-3pt]
\underline{-\phantom{00}9\phantom{000}} && \hbox{($\color{red}{3} \times \color{purple}{3} = 9$)} \\[-3pt]
\phantom{00}\ldots\phantom{0}
\end{array}
$$
Note that the decimal representation of $\frac{n}{d}$ terminates when the long division of $n/d$ terminates (i.e. reaches a $0$), and is infinitely long when the long division continues infinitely.
Observation. The decimal representation of $\frac{n}{d}$ terminates if-and-only-if the long division of $n / d$ terminates.
If we were to write the long division algorithm as pseudocode, it would look something like:
$
\underline{\text{LongDiv}(n,d)}: \\
q \xleftarrow{} \text{empty}\\
n' \xleftarrow{} n\\
\text{while } n' \neq 0: \\
\phantom{00}\text{if } n' < d: \\
\phantom{0000} q \xleftarrow{} \text{Adjust}(q, n', d)\\
\phantom{0000} n' \xleftarrow{} 10n'\\
\phantom{00}\text{else}:\\
\phantom{0000} q \xleftarrow{} \text{Adjust}(q,n',d)\\
\phantom{0000} n' \xleftarrow{} n' \% d\\
\text{return } q
$
..where $\text{Adjust}$ "appropriately expands" the quotient $q$ for a given iteration of the algorithm. We are purposefully being vague about how $\text{Adjust}$ works. For our purposes, we do not care about the numerical result $q$ of the long division, just whether the procedure terminates. In the above pseudocode, termination is solely a function of $n'$ (which is itself a function of $n$ and $d$) and $d$, and so we can abstract away the computation of $q$ for simplicity.
When does long division terminate?
So far, we have reduced the problem of determining whether the decimal representation of $\frac{1}{d}$ terminates to whether $\text{LongDiv}(1,d)$ terminates. But when does $\text{LongDiv}(1,d)$ terminate?
Looking closer at the $\text{LongDiv}$ algorithm, we can see that it will only stop if the variable $n'$ reaches $0$. Initially, the value of the variable $n'$ is the dividend $n$. At each iteration, a new value of $n'$ is obtained; either the current $n'$ multiplied by a factor of $10$, or the remainder of dividing the current $n'$ by $d$. This means that $\text{LongDiv}(n,d)$ continues to apply multiplications by $10$ and remainder-after-dividing-by-$d$ to the dividend $n$ until the result is $0$ (if ever). In other words, $\text{LongDiv}(n,d)$ terminates exactly when there is an integer $x \geq 0$ such that $10^x n \equiv 0 \mod d$.
Observation. $\text{LongDiv}(n,d)$ terminates if-and-only-if there is an integer $x \geq 0$ such that $10^x n \equiv 0 \mod d$
Putting it all together
Combining the above observations, we obtain that the decimal representation of $\frac{1}{d}$ terminates if-and-only-if there exists an integer $x \geq 0$ such that $10^x \equiv 0 \mod d$. An equivalent way of saying $10^x \equiv 0 \mod d$ is that $d$ divides $10^x$, or $10^x$ is a multiple of $d$. Therefore, to determine whether or not the decimal representation of $\frac{1}{d}$ terminates, it is sufficient check if there exists an integer $x \geq 0$ such that $10^x$ is a multiple of $d$ (or equivalently $d$ divides $10^x$).
To determine whether or not the decimal representation $\frac{1}{d}$ terminates, it is sufficient check if there exists an integer $x \geq 0$ such that $10^x$ is a multiple of $d$ (or equivalently $d$ divides $10^x$).
With this, we are now ready to evaluate my friend's claims, restated below.
Claim 1. If the prime factors of $d$ are limited to $2$ and $5$ (i.e. one, the other, or both), then the decimal representation of $\frac{1}{d}$ will terminate.
Claim 2. If $d$ has a prime factor other than $2$ or $5$, then the decimal representation of $\frac{1}{d}$ will be infinitely long (i.e. not terminate).
Let's tackle the first claim. Given that $d$ is assumed to only have prime factors of $2$ and $5$, we can write $d = 2^i 5^j$ for some integers $i,j \geq 0$. From our earlier observations, we know that the the decimal representation of $\frac{1}{2^i 5^j}$ will terminate if there exists an integer $x \geq 0$ such that $10^x$ is a multiple of $2^i 5^j$. For $10^x$ to be a multiple of $2^i 5^j$, there must exist an integer $a$ such that $a \times 2^i 5^j = 10^x$. Rewriting $10^x = 2^x 5^x$ and doing some algebra, we can obtain an expression for $a$, namely $a = (2^x 5^x) / (2^i 5^j) = 2^{x-i} 5^{x-j}$. For certain values of $x$, for example $x = \max(i,j)$, $a$ is an integer and for such values of $x$, $10^x$ is a multiple of $2^i 5^j$. Therefore, the decimal representation of $\frac{1}{2^i 5^j}$ will terminate. $\Box$
The second claim can be proven using a similar argument. Assume that $d$ has at least one prime factor that is not $2$ or $5$. The decimal representation of $\frac{1}{d}$ will terminate if-and-only-if there exists an integer $x \geq 0$ such that $d$ divides $10^x$. For $d$ to divide $10^x$, there must exist an integer $a$ such that $a \times d = 10^x$. By the fundamental theorem of arithmetic, we can uniquely factor both sides of this equation into products of (powers of) primes. On the left-hand side $a \times d$, at least one of the factors will be a prime that is neither $2$ nor $5$ (by assumption $d$ has at least one such prime factor). On the right-hand side $10^x$, the prime factorization is $2^x 5^x$. For both sides to be equal, the prime factorizations must be the same. However, the left-hand side will always have a prime factor that is not on the right-hand side, namely, the prime factor of $d$ that is neither $2$ nor $5$. Therefore, there does not exist an integer $a$ such that $a \times d = 10^x$, regardless of choice of integer $x \geq 0$. In other words, $d$ with at least one prime factor other than $2$ or $5$ cannot divide $10^x$, regardless of choice of $x$. Therefore, the decimal representation of $\frac{1}{d}$ for such $d$ will not terminate. $\Box$
Back to base 10
