Reciprocal Cycles

A unit fraction contains $1$ in the numerator. The decimal representation of the unit fractions with denominators $2$ to $10$ are given:
\begin{align}
1/2 &= 0.5\\
1/3 &=0.(3)\\
1/4 &=0.25\\
1/5 &= 0.2\\
1/6 &= 0.1(6)\\
1/7 &= 0.(142857)\\
1/8 &= 0.125\\
1/9 &= 0.(1)\\
1/10 &= 0.1
\end{align}
Where $0.1(6)$ means $0.166666\cdots$, and has a $1$-digit recurring cycle. It can be seen that $1/7$ has a $6$-digit recurring cycle.
Find the value of $d \lt 1000$ for which $1/d$ contains the longest recurring cycle in its decimal fraction part.

This problem is tied to the mathematical field of number theory, specifically to the concept known as the order of a number. The length of the repeating decimal of a fraction 1/d is related to the order of 10 mod d.

If an integer n has an order of m modulo d (we write it as ord_d(n) = m), this means that n^m ≡ 1 (mod d), and there is no positive integer k < m with n^k ≡ 1 (mod d). In this instance, the integer m is the least positive integer such that d divides n^m - 1. In other words, m is the length of the repeating block in the decimal fraction of 1/d if (and only if) n and d are relatively prime (i.e., they don't have any common factors except for 1). This applies to our case because 10 and d are relatively prime for all 1 < d < 1000, except for those d that are multiples of 2 or 5 (in which case, 1/d is a terminating decimal, not a recurring one). This directly gets us to the longest recurring cycles. The maximum order of 10 for a modulus less than 1000 happens, in fact, with 999. However, we are looking for the smallest such number, and that happens to be 983. So, d = 983. The proof that these are maximum is quite involved and would usually be covered in a college-level course on Number Theory, but boils down to properties of primitive roots of prime numbers and the multiplicative order of one number modulo another.

More Answers: