Period of Reciprocal of Prime

From ProofWiki
Jump to navigation Jump to search

Theorem

The decimal expansion of the reciprocal of a prime $p$, $ \frac 1 p $, is periodic in base $a$ whenever $ p \nmid a $ and that the length of the period is the order of $a$ modulo $p$. If $ p \mid a $ then the decimal expansion of $ \frac 1 p $ in base $a$ terminates.


Proof

First consider the case $ p \mid a $:

Let $ q = \frac a p $
Then $ \frac 1 p = \frac q a $
So the decimal expansion of $ \frac 1 p $ in base $a$ is $0.q$ and terminates.

Now consider the case $ p \nmid a $:

From Fermat's Little Theorem, $a^{p - 1} \equiv 1 \pmod p$, we know there must be an integer $c$ such that $a^c \equiv 1 \pmod p$; $p - 1$ is one such integer.
Consider the smallest integer $d$, the order of $a$ modulo $p$, such that $a^d \equiv 1 \pmod p$ and that there is some integer $x$ such that $a^d - 1 = xp$. We can rearrange the terms to achieve the following expression:
\(\displaystyle \dfrac 1 p\) \(=\) \(\displaystyle \dfrac x { a^d - 1 }\)
\(\displaystyle \) \(=\) \(\displaystyle \dfrac x { a^d } \dfrac 1 { 1 - \frac 1 { a^d } }\) factorizing
\(\displaystyle \) \(=\) \(\displaystyle \dfrac x { a^d } \paren { 1 + \paren { \frac 1 { a^d } } + \paren { \frac 1 { a^d } }^2 + \paren { \frac 1 { a^d } }^3 ... }\) From Power Series Expansion of Reciprocal of 1 + x noting that $ -1 < -\frac 1 { a^d } < 1 $
\(\displaystyle \) \(=\) \(\displaystyle \paren { \frac 1 { a^d } } x + \paren { \frac 1 { a^d } }^2 x + \paren { \frac 1 { a^d } }^3 x ...\) rerranging

So the decimal expansion of $ \frac 1 p $ in base $a$ is $0.xxx...$ and is periodic of length $d$, which is the order of $a$ modulo $p$.

$\blacksquare$