# How do you calculate how many decimal places there are before the repeating digits, given a fraction that expands to a repeating decimal?

If you have a fraction such as $$\frac{7}{26}=0.269230\overline{769230}$$ where there are a number of digits prior to the repeating section, how can you tell how many digits there will be given just the fraction?

I believe I could run through the standard long division algorithm until I come across the same remainder for the second time and then use the location of the first instance of this remainder to calculate the number of digits before the repeating section, but this feels very cumbersome.

After lots of reading online, I came across what looks like a formula for it from Wolfram MathWorld:

When a rational number $\frac{m}{n}$ with $(m,n)=1$ is expanded, the period begins after ${s}$ terms and has length ${t}$, where ${s}$ and ${t}$ are the smallest numbers satisfying $10^s\equiv10^{s+t}\pmod{n}$.

I know how to calculate the length of the period of a fraction, and so in the case of my original fraction we have $10^s\equiv10^{s+6}\pmod{26}$, but I don't know how to solve for ${s}$ in this equation!

So there are really two questions here - the one in the title, and a sneaky one about how to take logs in a modulo arithmetic equation.

• Nobody else knows how either; it's an open problem. You can use trial-and-error, and there are some things you can do with Fermat's theorem to cut down the number of exponents you have to check, but I don't think anything significantly better than brute force is known. – MJD Mar 26 '14 at 0:37
• @MJD That's not quite true; the algorithm is quite simple, but there isn't a constant-time closed form AFAIK. – Alex Becker Mar 26 '14 at 0:38
• @BobbyOcean You are correct that they are the best rational approximation, but that's very different than the best decimal approximation. – Alex Becker Mar 26 '14 at 0:44
• I disagree with the point you chose to claim as beginning repetition in $7/26$. It can be considered as repeating with the second decimal place. – hardmath Mar 26 '14 at 0:45
• @BobbyOcean Note that the continued fraction representations for the numbers $\frac1n$ all have the same length; each is $[0; n]$. But they have completely different base-10 periods, for example the period of $[0; 3]$ is 1 and the period of $[0; 17]$ is 16 and the period of $[0; 21]$ is 9. – MJD Mar 26 '14 at 1:15

Rewrite the fraction as $$\frac{m}{n}=\frac{p}{10^sq}$$ where $p,q$ are coprime and $q$ is not divisible by $2$ or $5$ while $p$ is not divisible by $10$. Computing $s$ (the pre-period) is easy; it is the larger of the number of times $2$ divides $n$ and the number of times $5$ divides $n$. Then we want the smallest $t$ such that $10^t\equiv 1\;(\bmod\;q)$. By Fermat's little theorem, we have $10^{\varphi(q)}\equiv 1\;(\bmod\;q)$, thus $\;t|\varphi(q)$ so it suffices to check the divisors of $\varphi(q)$.
• It would be $\varphi(q)$, not generally $q-1$. And if I read the question right, the OP is more interested in the length of the pre-period than of the period, that would be $s$, provided $10 \nmid p$. – Daniel Fischer Mar 26 '14 at 0:49