2
$\begingroup$

My problem is this: given a fraction $ \frac {1} {d} $ where $d$ is an integer, convert to a decimal fraction, like say $ \frac {1} {6} = 0.166666... $ then identify how many digits is in the repeating part of the fraction. This is a problem on a programming challenge problem website, so it can be solved with code. I won't mention which website so that I don't spoil it for anyone else doing a Google search. I am a computer science tutor and want to explain this to a student of mine, so I want to make sure I understand it well.

To make this a little easier to consider for myself (not being too familiar with the relevant math), I considered just the integer result of dividing some power of 10 by d: say $ \frac {100} {6} = 16$. Then we notice $ \frac{1000} {6} = 166$. Hmm, this seems like progress: we can observe the repeating pattern in the result of the division.

Say $d = 7$. Note that $\frac {10^6} {7} = 142857$ and $ \frac{10^{12}}{7} = 142857142857$. Okay this seems like good evidence that the cycle length for $ d=7$ is 6. I could probably write code to check this. But I feel a bit uncomfortable knowing how to identify a cycle, or not having the mathematics to back up my algorithm for finding a cycle.

I did write some code that got the right answer, but I still don't feel I understand.

So I made an attempt to understand further. I noticed that when we divide by increasing powers of ten, we get not just an integer but a remainder. So if $$ \frac{10^p} {d}$$ has a remainder of $r_1$, we can write $$ 10^p \cong r \mod d $$ I have this intuitive sense that as we track remainders as we increase the power of ten, at some point we'll get a remainder we had earlier, and the number of times we took an increasing power of ten is the cycle length. So if $$ 10 ^ p \cong 10^q \mod d$$ then $$ 10 ^ {p+1} \cong 10 ^ {q+1} \mod d$$ which I believe follows from the laws of modular arithmetic.

Then I can intuitively see that $q-p$ is some multiple of the cycle length, and the smallest q such that $ 10 ^ p \cong 10^q \mod d$ means $q-p$ is the cycle length exactly.

But two things: #1 I don't feel clear enough on why this works and #2 I need to explain this to a 9th grader, so I'm hoping there's a simple way to see it better.

$\endgroup$
7
  • $\begingroup$ Consider a repeating decimal $0.a_1a_2...a_n... = \frac{p}{q}$, where I assumed for simplicity $p<q$ and $gcd(p,q)=1$. Here $n$ is the length of the cycle. Then $\frac{10^np}{q}$ has the cycle before the decimal point ending at the decimal point. Note that $(10^n-1)\frac{p}{q}=a_1...a_n$, and thus $\frac{p}{q} = \frac{a_1...a_n}{10^n-1}$. Thus, $q$ is a factor of $10^n-1$ and $p$ a factor $a_1...a_n$. So I think to find the length of the cycle, we just need to find the smallest $n$ such that $q$ divides $10^n-1$. ( Not sure if this is helpful or not ) $\endgroup$ May 30 '20 at 21:39
  • $\begingroup$ @RohaNuckchady Thanks. One issue seems to be that these repeating decimal representations may have an initial non-repeating portion. I think it works out that $q$ must be a factor of $ 10^n - 10^m, m < n$ which is harder to search for using an algorithm. I don't know how to choose n and m other than every possibility. $\endgroup$ May 30 '20 at 23:32
  • $\begingroup$ I'm not sure, for example $b_1...b_m.a_1..a_n = \frac{p}{q}$, then we may substract $b_1...b_m=k$ to get $\frac{p}{q}-k=a_1....a_n$, then then we have the same thing as before in that, $\frac{p+kq}{q}(10^n-1)=a_1...a_n$, if $p$ and $q$ are co-prime, then so are $p+kq$ and $q$. So don't we still get $q$ divides $10^n-1$? $\endgroup$ May 31 '20 at 0:11
  • $\begingroup$ If we take a specific example, let's say, $12.279279.....$, this should correspond to $12+279/999=\frac{12*111+31}{111}$. So $q = 111$, and the smallest $n$ is indeed $3$. Can you engineer a specific case in which the idea might fail ? $\endgroup$ May 31 '20 at 0:19
  • $\begingroup$ Yes, 1/6 = 0.16666 doesn't work. Because this repeats with cycle length one, we should have $ (10^1 - 1) = 9 $ which should be divisible by 6. But it's not. My computer couldn't find any $n$ for which $10^n -1 $ is divisible by 6. However, $ 10^2 - 10^1 $ is divisible by 6, the cycle length is $2-1 = 1$. Maybe I didn't understand something; you certainly seem to know more than I do. $\endgroup$ May 31 '20 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.