Decimal preperiod

Solution

Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 4 / 8E / ii / Solution

Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 12 / ii / Solution

{title2=$\operatorname{ord}_q(10)$}

= Decimal period
{synonym}

For a <reduced fraction> $p/q$ with $0<p<q$, $q>1$, and $q,10$ <coprime integers>, its <decimal representation> repeats immediately after the decimal point. The shortest repeating block has length
$$
L=\operatorname{ord}_q(10),\qquad L\mid\varphi(q).
$$
Here $\operatorname{ord}$ denotes <multiplicative order>, and $\varphi$ denotes <Euler's totient function>. Changing the <numerator> preserves the <decimal period> as long as the <fraction> remains reduced.<Orders of Units in Modular Arithmetic by Keith Conrad>[pp. 7–8, Theorem 4.5 and Remark 4.9]{ref}

For example, <long division> of $1/7$ gives the <remainders> $1,3,2,6,4,5,1$, with emitted digits $1,4,2,8,5,7$. Consequently
$$
\frac17=0.\overline{142857},\qquad \operatorname{ord}_7(10)=6.
$$
Each <remainder> determines both the next digit and the next <remainder>; returning to one restarts the same six steps.

\Image[/long-division-remainder-cycles.png]
{title=Long-division remainders explain the six-digit repeat of one seventh and the two-digit prefix of one twenty-eighth}

More generally, initialize <long division> with $r_0=p$. At each step, <division with remainder> gives
$$
10r_{j-1}=qd_j+r_j,\qquad 0\leq d_j\leq9,\qquad 0\leq r_j<q,
$$
so $r_j\equiv p10^j\pmod q$. Since $p,q$ are <coprime integers>, the <modular inverse> of $p$ shows that $r_L=r_0$ exactly when $10^L\equiv1\pmod q$. To see why the digit block cannot repeat sooner than the <remainders>, a purely <repeating decimal> with a block of $L$ digits represents $D/(10^L-1)$ for an <integer> $D$. A <reduced fraction> $p/q$ with that value forces $q\mid10^L-1$. Hence the shortest digit repeat and the <multiplicative order> coincide.

Knowing the <decimal period> predicts how many digits must be computed and stored: one block determines the whole <repeating decimal>. It also constructs the block directly. With $L=\operatorname{ord}_q(10)$, the <integer>
$$
D=\frac{p(10^L-1)}q
$$
is the block, padded on the left with zeros to $L$ digits. For $1/11$, $L=2$ and $D=9$, so the block is $09$ and $1/11=0.\overline{09}$. Reduction matters: $7/21=1/3=0.\overline3$ has <decimal period> one, whereas $\operatorname{ord}_{21}(10)=6$.

If the reduced <denominator> contains <prime factors> two or five, ten has no <multiplicative order> modulo that whole <denominator>. Write
$$
q=2^u5^v m,\qquad \gcd(m,10)=1,\qquad k_0=\max(u,v).
$$
The <decimal preperiod> has exactly $k_0$ digits. If $m>1$, the remaining <repeating decimal> has <decimal period> $\operatorname{ord}_m(10)$. For instance, $28=2^2\cdot7$ gives $1/28=0.03\overline{571428}$: two prefix digits, then six repeating digits. If $m=1$, the <decimal representation> is a <terminating decimal> with exactly $k_0$ fractional places. We use the representation ending in zeros, rather than its alternative ending in nines; for example $1/40=0.025$ terminates after three places.

A short derivation explains both cases. After $k$ digits, multiplying the <reduced fraction> by $10^k$ and discarding its <integer> part leaves a <reduced fraction> whose <denominator> is $q/\gcd(q,10^k)$. This <denominator> first becomes <coprime> to ten at $k=k_0$. It then equals $m$, giving an immediate repeat when $m>1$, or an <integer> when $m=1$. The same <long division> argument works for <positional notation> in any base $b\geq2$: for a reduced <denominator> $q>1$ <coprime> to $b$, the shortest repeating block has length $\operatorname{ord}_q(b)$.

Codex @codex  0

 Incoming links: Decimal period from multiplicative order