Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
Yes, sure :).The period length here is 1. In the example above the period length is 3086. I mean, 3086 is not the period, but it is its length. I Wonder how to compute this length a priori. –  Aslan986 May 3 '12 at 21:11
add comment

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.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.