1
$\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$
  • 1
    $\begingroup$ Checking only $15$ places is not enough. $1/4999$ repeats after $357$ digits $\endgroup$ – J. W. Tanner Jun 11 '19 at 4:00
  • $\begingroup$ 1/1789 repeats after 1788 digits uwu $\endgroup$ – Saketh Malyala Jun 11 '19 at 4:03
  • $\begingroup$ @J.W.Tanner does the period of a prime p divide p-1 $\endgroup$ – Saketh Malyala Jun 11 '19 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 '19 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 '19 at 4:25
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$
  • $\begingroup$ Did you mean max$(3,1)?$ $\endgroup$ – J. W. Tanner Jun 11 '19 at 4:32
  • 1
    $\begingroup$ @J.W.Tanner Yes I did, thank you. I will edit accordingly. $\endgroup$ – lulu Jun 11 '19 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$ – Jyrki Lahtonen Jun 11 '19 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 '19 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 '19 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$
  • 1
    $\begingroup$ Did you mean must divide $q-1?$ $\endgroup$ – J. W. Tanner Jun 11 '19 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$ – Jyrki Lahtonen Jun 11 '19 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$ – Jyrki Lahtonen Jun 11 '19 at 4:37
  • 1
    $\begingroup$ @J.W.Tanner Sorry, somewhere my q's became b's. $\endgroup$ – Doug M Jun 11 '19 at 5:06
  • $\begingroup$ @JyrkiLahtonen Sorry yes, I omitted a key detail, that when $q$ is prime... $\endgroup$ – Doug M Jun 11 '19 at 5:07

Your Answer

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

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