Why can't the decimal fraction part of $\frac{1}{d}$, $d \in \mathbb{N}^\ast$ have a recurring cycle of length greater than $d$?

Question

I am trying to solve problem 26 from project euler which asks Find the value of $d < 1000$ for which $1/d$ contains the longest recurring cycle in its decimal fraction part.

I noticed that all the cycle lengths are smaller than $d$ (at least for numbers $d < 1'000'000$), and I was wondering why this seems to be true. Is there a deep reason for this, or is this just something trivial I am not seeing?

Answer 1

Because there is maximum of $d-1$ possible remainders when dividing $1 \cdot 10, 2 \cdot 10 , ... (d-1) \cdot 10$ by $d$ and eventually in the process of division you divide some of these numbers with $d$ again and then all repeats.

Answer 2

Seing as you are familiar with the long division algorithm, I'll give a reason based on that (at least the way I hope you're used to doing it, something similar to this video, only you keep going after the decimal point). During the long division algorithm, after you've "pulled down" all the non-zero digits, and start pulling down zeroes, note that whatever remainder you get (the result of the "subtraction" part, before you pull down the next $0$) will entirely dictate how all the rest of the divisions go. For this discussion I will assume that you've gotten to this point of the long division already (as the periodic nature won't appear until you start pulling down only $0$'s).

Say, for instance, you're calculating $10\div7$, you've gotten to the answer $1.4$, and a ramainder of $2$. You pull down a $0$, get $20$, write a $2$ in the answer, subtract $20-14 = 6$. So if one remainder is $2$, the next digit in the answer will always be $2$, and the next remainder will always be $6$.

Continuing, we see that any time the remainder is $6$, the next digit of the answer will be $8$ and the remainder will be $4$. And any time the remainder is $4$... I assume you can see how this continues. Whenever we reach a remainder we've had before, the pattern will start repeating.

Since we never get a remainder of $0$ (since that would mean the division doesn't give an infinite expansion), and you will never get a remainder equal to or larger than $7$ (as long as you do things corerctly), there are only $6$ possible remainders. Which means that the repeating pattern of remainders, and therefore the repeating pattern of decimals in the answer, can at most be $6$ long.

This discussion will, of course, work for any other number than $7$ as well. Note, however, that this does not prove that the expansion will always be $d-1$ long. Only that $d-1$ is the longest it can possibly get.

For instance, with $d = 9$, the remainder never changes (at least in base ten). If you are calculating $10\div 9$, and you've gotten to $1.1$ with a remainder of $1$, you pull down a $0$, get the next digit $1$, and a remainder of $1$ again. The pattern jsut repeats immediately.