Compute the period of a decimal number a priori

Question

I noticed that WolframAlpha, given an operation like $\frac{n}{m},\;n,m \in N$ that result in a periodic decimal number, computes really fast the length of the period.

E.g. $\frac{3923}{6173}$ has a period of 3086: here.

I was wondering how this computation is done: is there some method to do this (except the trivial one of executing the division and looking for a sequence repetition) ?

Answer 1

The period is always a factor of the totient of the denominator. In your example, 6173 is prime, so its totient is 6172 and half of that is 3086. I suspect Alpha is just doing the long division. When the remainder at any step matches the remainder at a previous step you have found the repeat. You can also find the repeat by finding the $k$ such that $10^k \equiv 1 \pmod {denominator}$

Answer 2

Suppose that the fraction $\rm\,r\in (0,1)$ has a decimal expansion purely periodic of length $\rm\,k.\,$ Then $\rm\,10^k r - r\,\! =\,\! (10^k-1)\,\! r = n\,$ is an integer, since $\rm\,10^k r\,$ is simply $\rm\,r\,$ left-shifted by $\rm\,k\,$ places, so its digits after the decimal point are the same as those of $\rm\,r,\,$ so they cancel out in the subtraction, leaving an integer. Conversely, if $\rm\, r = n/(10^k-1)$ then $\rm\,10^k\,\! r = n + r\,$ so $\rm\,r\,$ has period $\rm\,k\,$ (or a divisor of $\rm\,k\,$ if the cycle is not minimal).

Therefore, to find the minimal period of $\rm\,r = n/m\,$ we need to find the minimal $\rm\,k\,$ such that $\rm\,(10^k-1) n/m\,$ is an integer, i.e. such that $\rm\,m\,|\,n\,\!(10^k-1)\ \,$ (where $\rm\,a\,|\,b\,$ denotes $\rm\,a\,$ divides $\rm\,b).\,$ We may assume $\rm\,n/m\,$ is in lowest terms, i.e. $\rm\,gcd(m,n) = 1.\,$ Hence, by Euclid's lemma, from $\rm\,m\,|\,n\,\!(10^k-1)\,$ we deduce $\rm\,m\,|\,10^k-1.\,$ Thus to find the least period we need to find the least $\rm\,k\,$ such that $\rm\,10^k \equiv 1\pmod{m},\,$ i.e. the order of $10,\,$ modulo $\rm\,m.\,$

If we know an integer $\rm\,k\,$ with $\rm\,10^k\equiv 1\pmod{\!m},\,$ e.g. Euler $\,\phi(m)\,$ or Carmichael $\,\lambda(m)\,$ when $\,\rm m\,$ is coprime to $10,\,$ then the Order Theorem implies that the order is a divisor of $\rm\,k,\,$ so if we also know the prime factorization of $\rm\,k\,$ then we can quickly compute the order by successively testing factors of $\rm\,k\,$ obtained by deleting primes - see the Order Test. However, requiring prime factorization generally does not lead to efficient algorithms. For the state of the art on order algorithms see the literature cited in this post.