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$?
Best Answer
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.