I'm a newbie with number theory and I've been reading this page and trying to figure out how to calculate the length of the digits before the period and digits of the period of a rational number of the form $m/n$.
I came up with the following steps but unfortunately this doesn't always work
- Compute the prime factors for the denominator $n$
- If there are 10-coprimes factors, there's a period otherwise there isn't
- If there's a period, calculate its length taking each 10-coprime factor and doing the discrete logarithm $10^k\equiv 1 \pmod{factor}$ to find the maximum $k \le n$ (i.e. the maximum multiplicative order between the factors)
- There are digits before the period only if the denominator $n$ can be expressed as $n_02^\alpha5^\beta$ (and $n_0$ is coprime to 10) so the length of the digits before the period is the maximum between 0, $\alpha$ and $\beta$
The approach above, however, doesn't work since I'm getting length of 1 for the digits before the period for a simple rational number like $124/6 = 20,\bar6$ (while the result should be 0). I suppose the error should be in step 4.
Best Answer
Let me elaborate a bit on my comments:
Suppose $n$ is coprime to $10$. Then we have $10^{\varphi(n)}\equiv 1\pmod n$, and thus it follows that $10^k\equiv 1\pmod n$ for some $k$ dividing $\varphi(n)$. Choose the smallest such $k$. This corresponds to 3. in your suggested algorithm. Then $n$ must divide $10^k-1$ and so all prime factors of $n$ can be found in $$ 10^k-1=\overbrace{999......999}^{\text{the digit }9\text{ repeated }k\text{ times}} $$ Now for any $r\in\mathbb N$ such that $r<n$ we then have $$ \frac rn=\frac{d}{10^k-1} $$ where $d<10^k-1$ so that the above rational is recognized as a number in $[0,1)$ having a recurring decimal expansion of length $k$. The digits of $d$ with zeros padded on the left if necessary will then be the digits of the $k$-cycle.
Suppose now we are given any coprime natural numbers $m,n$ where one of them possibly is not coprime to $10$. Then we may find the minimal $s\in\mathbb Z$ such that $$ 10^s\cdot\frac mn=\frac{m'}{n'} $$ where $m',n'$ are coprime and $n'$ is coprime to $10$. In that case $$ \frac{m'}{n'}=\frac{qn'+r}{n'}=q+\frac d{10^k-1} $$ with $0\leq r<n$ and thus $0\leq d<10^k-1$. Since $s$ was chosen to be minimal, we cannot divide by $10$ any more times without the denominator sharing factors with $10$. Thus none of the decimals in $q$ will be recurring. In effect, $\frac{m'}{n'}$ has its digits precisely split into its recurring part and its non-recurring part by the decimal point. It will be of the form $$ \frac{m'}{n'}=q.\overline{00...d} $$ where the zeros are only padded to the left if necessary in order to match the period length, $k$. Finally we conclude that $$ \frac mn=10^{-s}\cdot\frac{m'}{n'}=10^{-s}q.\overline{00...d} $$ where $q$ is the non-recurring part and $\overline{00...d}$ is the recurring part. Here $s$ denotes the length of the antiperiod. Note that $s$ can also be negative as in $$ 54321.\overline{321}=10^3\cdot 54.\overline{321} $$ which in this sense has an antiperiod of length $s=-3$. Also note that $m'$ will be divisible by either $2$ or $5$ or none of them, but never both since then a smaller value of $s$ would be possible.