# Monthly Archives: January 2016

## Midy’s theorem

Let $b$ have order $d$ modulo $p$. Then the base $b$ expansion of $1/p$ has period $L=(b^d-1)/p$ of length $d$. To see this, note that if $b^d-1=mp$, then

$\displaystyle\frac 1p=\frac{m}{b^d-1}=\frac{m}{b^d}+\frac{m}{b^{2d}}+\frac{m}{b^{3d}}+\cdots$.

Note also that $aL for any $1\le a\le p-1$. Hence $a/p$ has period $aL$. Now suppose that $d$ is even. Since $b$ has order $d$ modulo $p$, it follows that $b^{d/2}\equiv -1\pmod p$. Hence $p-a\equiv b^{d/2}a\pmod p$. This means that at their midpoints the two numbers $aL$ and $(p-a)L$ are mirror images of one another. This means that splitting $aL$ midway into two equal parts and adding them gives $b^{d/2}-1$, i.e., a string of $(b-1)$‘s in base $b$. This is known as Midy’s theorem.

For example, with $p=7$ and $b=10$ we get $d=6$, and $L=142857$. Split $L$ into two equal parts $142$ and $857$, adding which gives

$142+857=999$.

In general, if $m$ is any divisor of $d$, then

\begin{aligned} b^d-1&=(b^m-1)(1+b^{d/m}+b^{2d/m}+\cdots+b^{(m-1)d/m})\\&\equiv 0\pmod p\end{aligned}

so

$b^{d/m}+b^{2d/m}+\cdots+b^{(m-1)d/m}\equiv -1\pmod p$

and so splitting $L$ into $m$ equal parts and adding them will always give a multiple of $b^{d/m}-1$.