Let $q\ge2$ be a fixed element of $\mathbb{N}$. It is well known that the set of rational numbers, $\mathbb{Q}$, is precicely the set of periodic $q$-nary standard fractions, that is periodic 'decimals' in base $q$. The following result gives more information on the length of the period of fractions whose denominator $n$ is coprime to the base $q$.
Theorem (Length of period). Let $\dfrac{m}{n}$ be a positive irreducible simple fraction. Let $\gcd(q, n) \sim 1$. If $\delta$ is the multiplicative order of $q$ modulo $n$, then
\begin{align*}\frac{m}{n}=&\ \frac{c_1}{q} + \frac{c_2}{q^2} + \dots + \frac{c_\delta}{q^\delta} +\\
&+ \frac{c_1}{q^{\delta + 1}} + \frac{c_2}{q^{\delta + 2}} + \dots + \frac{c_\delta}{q^{2\delta}} + \\
&+ \frac{c_1}{q^{2\delta + 1}} + \dots =\\
=&\ 0.(c_1c_2\dots c_\delta) = 0.\overline{c_1c_2\dots c_\delta},\tag{E}\end{align*}
i.e. the length of the period in base $q$ is $\delta$, and there is no non-repeating prefix; of course, $0 \leq c_i < q$, $c_i \in \mathbb{N_0}$.
Outline of attempted proof
(Skip to Question if you wish)
- Divide $qm$ by $n$ with remainder: $$qm = nc_1 + r_1, \quad 0\leq r_1 < n. \tag{1}$$
- Show that in fact $1 \leq r_1 < n$ and $\gcd(q, r_1) \sim 1$. This basically shows that the same assumptions are true for $\dfrac{r_1}{n}$ which were true for $\dfrac{m}{n}$.
- Repeat step $(1)$ a total of $k \in \mathbb{N}_+$ times giving
\begin{align*}qm &= nc_1 + r_1, \quad 1 \leq r_1 < n, \tag{1}\\
qr_1 &= nc_2 + r_2, \quad 1 \leq r_2 < n, \tag{2}\\
&\ \ \vdots \qquad \qquad \qquad \qquad \vdots\\
qr_{k-1} &= nc_k + r_k, \quad 1 \leq r_k < n, \tag{k} \end{align*}
and define $r_0 := m$ if necessary. - The numbers $c_i$ can be interpreted as digits in base $q$ because $0 \leq c_i < q – \dfrac{r_i}{n}.$
- Divide equations $(i)$ with $q^i n$ and substitute step-by-step to arrive at
\begin{align*}\frac{m}{n} &= \frac{c_1}{q} + \frac{r_1}{qn} = \frac{c_1}{q} + \frac{c_2}{q^2} + \frac{r_2}{q^2 n} = \\
&= \ldots = \frac{c_1}{q} + \frac{c_2}{q^2} + \dots + \frac{c_k}{q^k} + \frac{r_k}{q^k n}. \tag{*}\end{align*} - Because $\dfrac{r_k}{q^k n} < \dfrac{1}{q^k}$, the base $q$ representation indeed begins as $0.c_1c_2\dots c_k$. If we multiply equation $(*)$ by $q^k n$, we see that $$q^k m = \left(c_1q^{k -1} + c_2 q^{k – 2} + \dots + c_k \right) n + r_k. \tag{**}$$
Take $k := \delta$, then via $q^\delta \equiv 1 \pmod{n}$ from
$(**)$ we get $$q^\delta m \equiv m \equiv r_\delta \pmod{n}$$ which
by $1 \leq m, r_\delta < n$ results in $m = r_\delta$. - Therefore, repeating starts. More precicely, as $m = r_\delta$, we get
\begin{align*}qm &= nc_1 + r_1, \qquad 1 \leq r_1 < n, \tag{1} \\
&\ \ \vdots \qquad \qquad \qquad \qquad \vdots\\
qm = nc_\delta + r_\delta &= nc_\delta + m, \qquad 1 \leq r_\delta = m < n, \tag{$\delta$}\\
qm &= nc_1 + r_1, \qquad \qquad 1 \leq r_1 < n, \tag{$\delta$ + 1}\\
&\ \ \vdots \qquad \qquad \qquad \qquad \vdots \end{align*}
and so on. It is impossible for $r_k = m$ to hold for any $k\in\mathbb{N}_+$ such that $k < \delta$. This would conflict with the choice of $\delta$. - As far as I see it, only one step remains (see section: Question).
Question
So far, we have shown that $\dfrac{m}{n} = 0.c_1c_2\dots c_\delta c_1c_2\dots c_\delta c_1c_2\dots c_\delta\dots$ and so on. What remains to be shown is that $\delta$ is actually the period. Yes, we have shown that a block of $\delta$ digits does repeat, and that the smallest $k\in\mathbb{N}_+$ such that $r_k = m$ is $k = \delta$. However, to prove that $\delta$ is indeed length of the period, we must rule out the possibility of a smaller repeating unit from any source, not just $r_k = m$.
In other words, one possibility of having a smaller repeating unit would be to have $r_k = m$ with $k < \delta$. We have ruled this particular option out. But the hypothetical possibility remains that there is some smaller repeating unit regardless of the fact that $r_1, r_2, \dots, r_{\delta-1} \neq m$. Maybe what I have shown, for instance with $\delta := 4$, is that $\dfrac{m}{n} = 0.1010\dots$ while the actual period is still smaller, in fact with length $2$, and $\dfrac{m}{n} = 0.(10)$. These and other examples are the kinds of things I would wish to rule out. This is where I am stuck.
- Q: How do I prove that such (and other) pathological examples cannot occur? In other words, how to show that $c_1c_2\dots c_\delta$ is also the smallest repeating unit? In other words still, is the only option for the start a new repeat cycle indeed $r_k = m$?
Best Answer
If the period is $k$, then for some $c$, $$\frac{m}{n} = \frac{c}{q^k} + \frac{c}{q^{2k}} + \ldots = \frac{c}{q^k - 1}$$ i.e. $$m (q^k - 1) = n c$$ Since $m$ and $n$ are coprime, $n$ must divide $q^k-1$, i.e. $q^k \equiv 1 \mod n$. But you assumed that $\delta$ was the order of $q$ mod $n$.