problem-26.md

title	Problem 26: Reciprocal Cycles
layout	post
mathjax	true

Reciprocal Cycles

Problem

Here is problem 26:

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

$$ \begin{align*} &\dfrac{1}{2} = 0.5 \\ &\dfrac{1}{3} = 0.\overline{3} \\ &\dfrac{1}{4} = 0.25 \\ &\dfrac{1}{5} = 0.2 \\ &\dfrac{1}{6} = 0.1\overline{6} \\ &\dfrac{1}{7} = 0.\overline{142857} \\ &\dfrac{1}{8} = 0.125 \\ &\dfrac{1}{9} = 0.\overline{1} \\ &\dfrac{1}{10} = 0.1 \\ \end{align*} $$

Where $$0.1\overline{6}$$ means $$0.16666...$$, and has a 1-digit recurring cycle. It can be seen that $$\dfrac{1}{7}$$ has a 6-digit recurring cycling.

Find the value of $$d \le 1000$$ for which $$\dfrac{1}{d}$$ contains the longest recurring cycle in its decimal fraction part.

Solution

It is better to search searching for cycles starting from $$d = 999$$ and decrementing because the longest cycle will occur when $$d$$ is largest. A number $$\dfrac{1}{n}$$ cannot have more than $$n$$ repeating digits in its decimal expansion. To illustrate this, consider what is happening when you do long division to calculate $$\dfrac{1}{7}$$:

First you divide 1.0 by 7 and find the remainder. Computationally, this is the same as dividing 10 by 7, then multiplying the remainder by 10, dividing by 7 again, and so on. See the sequence of computations for calculating 1/7 below, written in this manner:

$$ \begin{align*} &(1 * 10) / 7 = \textbf{(1)} * 7 + 3 \\ &(3 * 10) / 7 = \textbf{(4)} * 7 + 2 \\ &(2 * 10) / 7 = \textbf{(2)} * 7 + 6 \\ &(6 * 10) / 7 = \textbf{(8)} * 7 + 4 \\ &(4 * 10) / 7 = \textbf{(5)} * 7 + 5 \\ &(5 * 10) / 7 = \textbf{(7)} * 7 + 1 \\ &(1 * 10) / 7 = \textbf{(1)} * 7 + 3 \\ &(3 * 10) / 7 = \textbf{(4)} * 7 + 2 \\ \end{align*} $$

In equation (1), the remainder of 3 is multiplied by 10 in equation (2). In equation (2), the remainder of 2 is multiplied by 10 in equation (3), and so on. The bolded numbers happen to form the decimal expansion of $$\dfrac{1}{7} = \overline{14285714}$$. If the above process is continued, the bolded digits repeat (and the digits of the decimal expansion of $$\dfrac{1}{7}$$ also repeat).

Further notice that:

$$ \begin{align*} &1 * 10 \pmod{7} \equiv 10^1 \pmod{7} \\ &3 * 10 \pmod{7} \equiv 10^2 \pmod{7} \\ &2 * 10 \pmod{7} \equiv 10^3 \pmod{7} \\ &6 * 10 \pmod{7} \equiv 10^4 \pmod{7} \\ &4 * 10 \pmod{7} \equiv 10^5 \pmod{7} \\ &5 * 10 \pmod{7} \equiv 10^6 \pmod{7} \\ &1 * 10 \pmod{7} \equiv 10^7 \pmod{7} \\ &3 * 10 \pmod{7} \equiv 10^8 \pmod{7} \\ \end{align*} $$

As you can see, at the next to last step, the digits start to repeat. In fact, the number of repeating digits is given by $$e = ord_{10}n$$, where $$e$$ is the smallest positive integer such that $$10^e \equiv 1 \pmod{n}$$ (this concept is called the multiplicative order. The preceding is not a proof of this fact, but it was enough to start searching for solutions near 999.