# Compute the period of a decimal number a priori [duplicate]

Possible Duplicate:
Upper bound/exact length of decimal expansion of simple fraction

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

-
Note: i'm not a mathematician, I apologize if I have done some mistake with names, tags, etc.. –  Aslan986 May 3 '12 at 20:54

## marked as duplicate by Ross Millikan, sdcvvc, William, t.b., rschwiebSep 14 '12 at 16:39

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

-
consider for example $10/3=0.333333333333333$ which has period 3,or 33 or as you like,it happens when one number can't be divided by another exactly and during this division,some sequence of numbers is repeating
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)\:$ (here $\rm\:a\:|\:b\:$ denotes $\rm\:a\:$ divides $\rm\:b).\:$ We may assume that $\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.\:$ There are various algorithms known for computing such orders, e.g. see the references in this post.