# Monthly Archives: December 2015

## Permutation of digits by multiplication

Here is an expository write-up of this post.

The number $N=142857$ is interesting because of the following property

\begin{aligned}N&=142857\\ 2N&=285714\\ 3N&=428571\\ 4N&=571428\\ 5N&=714285\\ 6N&=857142\end{aligned}

and $7N=999999$. The last equation means that

$\displaystyle\frac 17=0.\overline{142857}.$

So multiplying $N$ by $1,2,3,4,5,6$ simply permutes the digits of $N$. As elements of $S_6$ these permutations correspond to (using cycle notation)

$\hbox{id}$, $(153)(264)$, $(165432)$, $(135)(246)$, $(123456)$, $(14)(25)(36)$

respectively. We can read off the following from this list.

• Since $(165432)$ and $(123456)$ are full-length cycles, $3$ and $5$ are primitive roots modulo $7$.
• $2$ and $4$ have order $3$ modulo $7$, while $6$ has order $2$.

In general, if $p$ is an odd prime and $b$ is a positive integer with order $d$ modulo $p$, then $1/p$ will have period $(b^d-1)/p$ of length $d$ in base $b$. This follows simply from observing 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$.

Now let $b>p$ be a primitive root modulo $p$. We shall work in base $b$. Then $1/p$ will have period $L=(b^{p-1}-1)/p$ of length $p-1$. Since the periods of $1/p,2/p,\dots,(p-1)/p$ are $L,2L,\dots,(p-1)L$, all of length $p-1$, which are all powers of some permutation of the digits of $L$, and no two of which are congruent modulo $b$, it follows that the digits of $L$ are all distinct. So we’ve shown the following.

Theorem. If $p$ is an odd prime and $b>p$ is a primitive root modulo $p$, then the base $b$ expansion of $1/p$ has period of length $p-1$ with distinct digits.

Taking $p=7$, $b=10$ gives our previous example. So the prime $7$ in base $10$ is indeed very special, since it is the only prime less than $10$ for which $10$ is a primitive root.

1 Comment

Filed under Number theory