Finding prefix and repetend length

We interrupt your regularly scheduled primality testing to bring you something else fun I’ve been thinking about. It’s well-known that any rational number $a/b$ has a decimal expansion that either terminates, or is eventually periodic—that is, the digits after the decimal point consist of some initial sequence of digits, followed by a sequence of digits that repeats forever:

$a/b = 0.p_1 p_2 \dots p_k \overline{r_1 r_2 \dots r_n}$

(Let’s assume $a < b$ ; if $a > b$ then we can just pull out the integer part before analyzing the part after the decimal point.) We’ll call $p_1 \dots p_k$ the prefix, which has $k$ digits, and $r_1 \dots r_n$ is the $n$ -digit repetend.

The question is, given a fraction $a/b$ , how long will the prefix and repetend be (i.e. what are the smallest possible values of $k$ and $n$ )? In particular, it possible to compute $k$ and $n$ without simply doing long division?

It turns out that it is possible, and I’d like to explain how it can be done. I wrote about this a long time ago (exactly ten years and two days ago, actually!!) but I think I can do a better job explaining it now.

An example

Let’s start by looking at the fraction

$\displaystyle \frac{89}{420} = 0.21\overline{190476}$

It starts with a two-digit prefix $21$ (that is, $k = 2$ ), and after that it repeats the sequence of $n = 6$ digits $190476$ forever.

Let’s play with this a bit. First of all, let’s multiply by $10^2$ to shift the prefix over to the left of the decimal point:

$\displaystyle 10^2 \cdot \frac{89}{420} = 21.\overline{190476}$

Now if we multiply by another $10^6$ , we shift one entire copy of the repetend to the left of the decimal point as well:

$\displaystyle 10^2 \cdot 10^6 \cdot \frac{89}{420} = 21190476.\overline{190476}$

If we subtract these, the infinite repeating parts to the right of the decimal point will cancel, and we will be left with an integer:

$\displaystyle 10^2 \cdot 10^6 \cdot \frac{89}{420} - 10^2 \cdot \frac{89}{420} = 21190476.\overline{190476} - 21.\overline{190476} = \text{an integer}.$

(Of course in this case the integer is $21190476 - 21 = 21190455$ , but we don’t really care: since we’re only interested in the length of the prefix and repetend, it turns out that it doesn’t actually matter what the integer is, only the fact that it is one!)

We can now factor the left-hand side a bit to get

$\displaystyle 10^2 \cdot (10^6 - 1) \cdot \frac{89}{420} = \text{an integer}.$

Let’s think about why this is an integer. Note that $420 = 10 \cdot 2 \cdot 21 = 2^2 \cdot 3 \cdot 5 \cdot 7$ . First, the $10^2 = 2^2 \cdot 5^2$ cancels with the $2^2$ and $5$ in $420$ , leaving

$\displaystyle 5 \cdot (10^6 - 1) \cdot \frac{89}{21}.$

Now note that $10^6 - 1 = 999999 = 3^3 \cdot 7 \cdot 11 \cdot 13 \cdot 37$ is divisible by $21$ , so the remaining denominator cancels and we are left with an integer. In fact, as you can check, $6$ is the smallest value of $n$ such that $10^n - 1$ is divisible by $21$ .

Generalizing

Let’s generalize: suppose we have

$\displaystyle \frac{a}{b} = 0.p_1 \dots p_k \overline{r_1 \dots r_n}$

and assume that $a/b$ is in lowest terms, that is, $a$ and $b$ share no common factors. Multiplying by $10^k$ shifts the prefix to the left of the decimal point,

$\displaystyle 10^k \cdot \frac{a}{b} = p_1 \dots p_k.\overline{r_1 \dots r_n},$

then multiplying by $10^n$ and subtracting cancels the repeating part to the right of the decimal point:

$\displaystyle 10^k \cdot 10^n \cdot \frac{a}{b} - 10^k \cdot \frac{a}{b} = \text{an integer}.$

Again, we can factor the left-hand side, yielding

$\displaystyle 10^k \cdot (10^n - 1) \cdot \frac{a}{b} = \text{an integer}.$

We want to find the smallest values of $k$ and $n$ which make this work. Note that since we assumed $a$ and $b$ share no common factors, $a$ is actually irrelevant: it doesn’t contribute to cancelling $b$ at all. (This explains why repetends are always the same length for a given denominator.) So in the end, the question becomes:

What are the smallest values of $k$ and $n$ such that $10^k \cdot (10^n - 1)$ is evenly divisible by $b$ ?

Or, put another way, how can we choose $k$ and $n$ in such a way that every prime factor of $b$ also shows up in $10^k \cdot (10^n - 1)$ ? I’ll continue in future posts; for now, I leave you with a few questions:

Can you see why we get to determine the values of $k$ and $n$ separately, i.e. neither value influences the other at all? (Hint: which prime factors of $b$ could possibly be canceled by $10^k$ ? Which could be canceled by $10^n - 1$ ?)
Can you figure out how to find the right value of $k$ ?
Can you say anything at all about the right value of $n$ ?

(Hints: finding $k$ turns out to be much easier than finding $n$ , and requires only knowing some basic facts about divisibility. Saying useful things about $n$ requires knowing some number theory and/or group theory.)