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.

Advertisements

1 Comment

Filed under Number theory