Length of period of decimal expansion of a fraction

Question

Each rational number (fraction) can be written as a decimal periodic number. Is there a method or hint to derive the length of the period of an arbitrary fraction? For example $1/3=0.3333...=0.(3)$ has a period of length 1.

For example: how to determine the length of a period of $119/13$?

Answer 1

This answer seeks to explain why Ross Millikan's answer works, and provides further information on techniques to speed up the process of seeking the period:

Consider the fraction $\frac17$. The decimal expansion of this is $$ \frac17 = 0.\overline{142857} $$ for a period of 6. Now consider what happens when we multiply it by $10^6$: $$ 10^6\times\frac17 = 142857.\overline{142857} $$ Subtracting the original fraction from this gives $$ (10^6-1)\times\frac17 = 142857 $$ And so, we have $$ \frac17 = \frac{142857}{10^6-1} $$ As you can see, the denominator is one less than a power of 10, and the power is the period of the decimal expansion. This is no accident, and works for any fraction - if you can rewrite it in this form, the denominator reveals the period.

Now, rearrange the equation: $$ 10^6-1 = 142857\times 7 $$ So $10^6$ must be one more than a multiple of 7 (or, more generally, $10^n$ must be one more than a multiple of $d$, where $d$ is the denominator of the fraction and $n$ is the period of the decimal expansion) - indeed, it must be the smallest power of 10 (larger than 1) that has this property.

As such, we can use modular arithmetic to look for the period. Since $a\times d\equiv 0 \pmod d$, we have that $10^n-1\equiv0 \pmod d$, or $$10^n \equiv 1\pmod d$$ And therefore you can just look for the smallest $n>0$ satisfying this.

Of course, there are other approaches to gain the same result, but they're all fundamentally variants of the same idea. That said, if you can factor $\phi(d)$ - the euler totient function of the denominator - then you can accelerate the process of looking for the smallest $n$. For example, when checking 13, you have $\phi(13)=12$, so $n\in\{1,2,3,4,6,12\}$ (as these are the factors of 12) - this can save you a lot of computation (especially where $\phi(d)$ has only a few large factors and 2).

For example, $\phi(167)=166 = 2\times83$, so $n\in\{1,2,83,166\}$. Therefore, we need to check only these four, and we can do it quite efficiently. Obviously, neither $10$ nor $100=10^2$ are equivalent to 1 mod 167, so we only need to actually check 83. For this we can use binary exponentiation. Note that $83 = 2^6 + 2^4 + 2^1 + 2^0$. So we can write $$\begin{align} 10^{83} &= 10^{2\times(2^5 + 2^3 + 1)}\times 10\\ &= (10^{2^3\times(2^2+1)}\times 10)^2 \times 10\\ &= ((10^{2^2}\times10)^{2^3}\times 10)^2 \times 10 \end{align}$$ So, working in modular arithmetic, we can go $$\begin{align} 10^{83} &\equiv ((10^{2^2}\times10)^{2^3}\times 10)^2 \times 10 \mod 167\\ &\equiv ((100^2\times 10)^{2^3}\times 10)^2\times10\mod167\\ &\equiv ((147\times 10)^{2^3}\times 10)^2\times10\mod167\\ &\equiv (134^{2^3}\times 10)^2\times10\mod167\\ &\equiv (87^{2^2}\times 10)^2\times10\mod167\\ &\equiv (54^2\times 10)^2\times10\mod167\\ &\equiv (77\times 10)^2\times10\mod167\\ &\equiv 102^2\times10\mod167\\ &\equiv 50\times10\mod167\\ &\equiv 166\mod167 \end{align}$$ This is the same as $-1\pmod{167}$, so $n=166$ is the only possible period, and $\frac1{167}$ has a period of 166.

Also note that you don't actually have to expand out the product like that. You can just write the number in binary ($83_{10} = 1010011_2$), then work through the binary digits left-to-right - start with 1, and for each digit, $b$, multiply by $10^b$. Square it after each digit except the last one.

Answer 2

Assuming there are no factors of $2,5$ in the denominator, one way is just to raise $10$ to powers modulo the denominator. If you find $-1$ you are halfway done. Taking your example: $10^2\equiv 9, 10^3\equiv -1, 10^6 \equiv 1 \pmod {13}$ so the repeat of $\frac 1{13}$ is $6$ long. It will always be a factor of Euler's totient function of the denominator. For prime $p$, that is $p-1$.

Answer 3

The length of the period is given by the multiplicative order of $10 \pmod q$, where $q$ is your quotient. It is closely related to the discrete logarithm. Wikipedia lists several algorithms that are faster than going through all the powers of ten, which is relevant if you're dealing with very large numbers (hundreds of digits).

Answer 4

First you have to simplify to the lowest integer denominator.

Then, the proof for finiteness of repeating part of the decimal representation involves the pigeonhole principle. When you keep on dividing, at some point you will run into a repeat value for the remainder. Given that the remainders that keep the operation going range from 1 to (denominator-1), the possible number of pigeonholes is (denominator-1) as the number of pigeonholes; so that's your worst possible case scenario - in any base.

The particular cases, as described by the other answers, depend on the base, because the denominator may have a special relationship with the base.

• e.g., in base 10 fractions over 3 will have one repeating decimal, (3) or (6), as 3 divides 9(=10-1), and the remainder will keep repeating.