Number Theory – How to Compute the Period of a Decimal Number A Priori

number theoryrational numbers

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) ?

Best Answer

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}$