# Period of Reciprocal of Prime

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$