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<b^d 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.

Advertisements

Leave a comment

Filed under Number theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s