2
$\begingroup$

Given a fraction of two relatively prime integers of lengths m and n, what is the maximum number of decimal places (in the decimal expansion) before the expansion starts repeating? For example I happened to compute the ratio of two four digit numbers and the answer to 15 places had no repeats. I do not know when the repeats would start.

This question differs from a "duplicate" question. I am asking for how many digits (maximum) BEFORE it starts repeating. Referred question is length of repetition.

$\endgroup$
6
  • 1
    $\begingroup$ Checking only $15$ places is not enough. $1/4999$ repeats after $357$ digits $\endgroup$ Jun 11, 2019 at 4:00
  • $\begingroup$ 1/1789 repeats after 1788 digits uwu $\endgroup$ Jun 11, 2019 at 4:03
  • $\begingroup$ @J.W.Tanner does the period of a prime p divide p-1 $\endgroup$ Jun 11, 2019 at 4:04
  • $\begingroup$ The same argument for the length of the period shows that we seek the smallest integers $s≥0,t>0$ such that $10^s\equiv 10^{s+t}\pmod n$. Then the "initial block" has length $s$ and the period has length $t$. See, e.g., this $\endgroup$
    – lulu
    Jun 11, 2019 at 4:06
  • 2
    $\begingroup$ Note: your question is not clear. Using the notation from my prior comment, are you interested in $s$ or $s+t$? if all you want is $s$, I have posted a solution below. To get $s+t$ you will, of course, need to compute the length of the period as well. $\endgroup$
    – lulu
    Jun 11, 2019 at 4:25

2 Answers 2

2
$\begingroup$

Assuming you are just interested in the length of the initial block (before the start of the period), write $n=2^a5^bN$ where $\gcd(10,N)=1$. Then the length of the initial block is $\max(a,b)$.

Example: Consider $\frac 1{360}$. We have $360=2^3\times 5^1\times 3^2$ so we expect the initial block to have length $\max(3,1)=3$. Indeed, $$\frac 1{360}=.002\overline 7$$

To prove this, let $c=\max(a,b)$. Then $10^c\times \frac mn$ is a rational number with denominator prime to $10$. For those, the decimal repeats from the start, so we are done.

If you want the total length before you see repetitions then you need to add the length of the period to this. That's the order of $10\pmod N$. Sticking with $\frac 1{360}$ we see that $N=9$ so the order of $10$ is $1$. In general, if you just want an upper bound, take $\max (a,b)+ \varphi(N)$.

$\endgroup$
7
  • $\begingroup$ Did you mean max$(3,1)?$ $\endgroup$ Jun 11, 2019 at 4:32
  • 1
    $\begingroup$ @J.W.Tanner Yes I did, thank you. I will edit accordingly. $\endgroup$
    – lulu
    Jun 11, 2019 at 4:33
  • $\begingroup$ (+1) You can actually use the Carmichael function in place of the Euler totient $\phi$. Granted, not necessarily much of an improvement to the upper bound. $\endgroup$ Jun 11, 2019 at 4:44
  • 1
    $\begingroup$ Where is the mystery? The order of $10$ $\pmod {2627}$ is $105$, so the period of this decimal has length $105$ (there is no initial block). Not sure where your $15$ comes from. $\endgroup$
    – lulu
    Jun 11, 2019 at 16:24
  • 2
    $\begingroup$ Without having worked too hard, I think the "worst" four digit denominator is $9967$. That's prime and $10$ happens to be a primitive root for it. Thus, the period for the decimal equivalent of $\frac 1{9967}$ has length $9966$. $\endgroup$
    – lulu
    Jun 11, 2019 at 16:37
0
$\begingroup$

We have two integer, $p,q$ we divide $p$ by $q$ and get some remainder $r$ with $0\le r<q$

if $r = 0$ then the decimal is finite. If we are only considering repeating decimals, $0<r<b$

And we divide $10$ by $q$ and we get a new remainder $r_2$ also with $1\le r_2<q$

And we repeat the process until we get a $r_n = r_m$ where $r_m$ is one of the previous values of remainder we have already had.

There are $q-1$ integers such that $0<r<q$ so the maximum length of the cycle is $q-1$

There is a theorem that says that if $q$ is prime does not divide 10, the length of the cycle must divide $q-1$

$\endgroup$
5
  • 1
    $\begingroup$ Did you mean must divide $q-1?$ $\endgroup$ Jun 11, 2019 at 4:30
  • $\begingroup$ The length of the cycle is forced to be a factor of $q-1$ only when $q$ is a prime not dividing ten. The period of $1/7$ has length six, that of $1/41$ five, so the period of $1/(7\cdot41)=1/287$ has length $30$. But $30$ is not a factor of $287-1$. $\endgroup$ Jun 11, 2019 at 4:36
  • 1
    $\begingroup$ The correct formulation (in the case $\gcd(q,10)=1$) relates the length of the period to the order of $10$ in the group $\Bbb{Z}_q^*$. It must thus be a factor of $\phi(q)$, but actually more can be said (Chinese remainder theorem, Carmichael function) $\endgroup$ Jun 11, 2019 at 4:37
  • 1
    $\begingroup$ @J.W.Tanner Sorry, somewhere my q's became b's. $\endgroup$
    – user317176
    Jun 11, 2019 at 5:06
  • $\begingroup$ @JyrkiLahtonen Sorry yes, I omitted a key detail, that when $q$ is prime... $\endgroup$
    – user317176
    Jun 11, 2019 at 5:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .