# Proof completion: Finding the length of period for $q$-nary irreducible fraction $m / n$ with $q$, $n$ coprime

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}$$.

1. Divide $$qm$$ by $$n$$ with remainder: $$qm = nc_1 + r_1, \quad 0\leq r_1 < n. \tag{1}$$
2. 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}$$.
3. 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.
4. The numbers $$c_i$$ can be interpreted as digits in base $$q$$ because $$0 \leq c_i < q - \dfrac{r_i}{n}.$$
5. 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*}
6. 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$$.
7. 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$$.
8. 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$$?

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$$.