A common algorithm for converting a decimal number that is between 0 and 1 to binary is to multiply by 2 and record the integer part of the result. Then, you subtract that integer from the result and repeat the process.
Example = ${0.1}_{10} = \frac{1}{10}$
Result = ${0.0 0011 0011 0011…}_2$
Is there any simple way to tell the maximum repeating period of a binary fraction obtained using that conversion algorithm?
Best Answer
A number that has a finite decimal notation with $k$ digits after the decimal point is a fraction with denominator $10^k$. Multiplying by $2$ $k$ times cancels the $k$ factors of $2$ and makes the denominator $5^k$. The period of the repeating $b$-ary representation of a fraction with denominator $d$ is the order of $b$ modulo $d$. Since $2$ is a primitive root modulo $5$, and if $b$ is a primitive root modulo $p$ then it is a primite root modulo all powers $p^k$ unless $b^{p-1}\equiv1\bmod p^2$ (I don't know how to prove that, I just found it on Wikipedia), $2$ is a primitive root modulo $5^k$ for all $k$, so its order modulo $5^k$ is $\phi\left(5^k\right)$, where $\phi$ is Euler's totient function that counts the number of numbers coprime to its argument. Since $\phi\left(5^k\right)=4\cdot5^{k-1}$, a number that has a finite decimal notation with $k$ digits after the decimal point has period $4\cdot5^{k-1}$ in binary notation. In your example, $k=1$ and the period is $4\cdot5^{1-1}=4$.