Pigeonhole Principle and maximum length of the repeating section

Question

The question I have is, when 5 / 20483 is written as a decimal, what is the maximum length of the repeating section of the representation?

I believe I need to divide 5 by 20483 which is equal to .00024410486, but how do I figure out the maximum length of the repeating section of the representation?

Thanks,

Tony

MJD:

In the course I am taking, when working with this type of problem, the examples show long division and state that if two remainders (R$_0$, R$_1$, R$_2$, R$_3$...R$_n$) are equal then the answer (in this case: .000244104) will start to repeat. I assume that the maximum length of the repeating section will be the distance between R$_i$ and R$_j$. For example, if R$_2$ and R$_6$ were both 234 then the maximum length of the repeating distance would be R$_6$-R$_2$ = (6 - 2) = 4 digits. But I do not know if this is correct. If I am correct in my assumption then I also assume that there is an easier way to determine the maximum length of the repeating section. I hope this help to clarify what I am looking for help on.

Tony

Answer 1

When you divide 5 by 20483, you have a quotient of 0 and a remainder of 5. So you write down the 0, then multiply the remainder by 10, to get 50. Then you repeat the process: divide 50 by 20483, obtaining a quotient of 0 and a remainder of 50.

This repeats for a few more steps, until you find you are dividing 50000 by 20483. Then you have a quotient of 2 and a remainder of 9034, because $50000 = 2\cdot20843 + 9034$. So you write down the 2, again multiply the remainder by 10 to get 90340, and continue onward. This is why the quotient begins with $0.0002$.

Now at some point the remainder will have to repeat. Suppose after a long time it was 5. Then all the subsequent steps would be just like steps you had already performed, and you would be writing down all the same quotients as you did back at the beginning, when it was 5 before.

But what if it doesn't become 5 again? Well, if the remainder repeats any number that you have seen before, then the following quotients that you write down, and the following remainders, will all repeat what they did the first time.

But there are only 20483 possible remainders when you divide by 20483: you could have a remainder of 0, or a remainder of 1, or… or a remainder of 20482. So you must eventually reach the same one twice.

Now do you know the maximum length of the repeating section of the representation?

Answer 2

Consider, as you do, the sequence of remainders $R_0, R_1, \dots R_n$ that you get in the long-division process. [*See footnote below for a formal definition.]

As these are remainders on dividing by $20483$ (and are nonzero), they always satisfy $0 < R_i < 20483$, for any $i$.

If any two remainders are equal, then the digits repeat from then on. As there are only $20483 - 1$ possible distinct remainders ($1$ to $20482$), some two remainders in $R_0, \dots, R_{20482}$ must be equal (not all of them can be distinct, by the pigeonhole principle), so the maximum possible length of the repeating section of the decimal representation is $20483 - 1$.

[This is the upper bound given by the pigeonhole principle, but finding whether this upper bound is actually attained may require trying all dividends. Actually, it depends on whether $10$ is a primitive root modulo the divisor. In this case it's not, and both $5/20483$ and every single integer when divided by $20483$ has length $10241 = (20483 - 1)/2$ for its repeating part (unless of course, it's divisible by $20483$ and has only $0$s after the decimal point). But I'm pretty sure your homework only expects the answer $20482$.)]

---

[*]: The remainders can be formally defined as follows: set $R_{-1} = 5$ (your original dividend). Then for $n \ge 0$, $R_n$ is defined as the remainder on dividing $R_{n-1} \times 10$ by the divisor ($20483$ in your case). (The multiplication of $R_{n-1}$ by $10$ corresponds to "bringing down a $0$".) Note that this differs from your notation, as we get the sequence of remainders $(5, 50, 500, 5000, 9034, 8408, 2148, 997, 9970, 17768, \dots)$, and not the ones you get, where you "bring down" multiple $0$s simultaneously, as a shortcut. But this is what you should be using in your analysis.