142857*2=285714 142857*3=428571 …

Let {a=142857}, then

\displaystyle \begin{array}{rl} a=142857,\\ 2a=285714,\\ 3a=428571,\\ 4a=571428,\\ 5a=714285,\\ 6a=857142. \end{array}

(And 7a=999999. ) This seems to be an amazing property of {a}. But then, why {142857}? Some of you may notice that {142857} comes from the decimal expansion of {\frac{1}{7}}. In fact:

\displaystyle \begin{array}{rl} 1/7=0.142857\;142857\cdots,\\ 2/7=0.285714\;285714\cdots,\\ 3/7=0.428571\;428571\cdots,\\ 4/7=0.571428\;571428\cdots,\\ 5/7=0.714285\;714285\cdots,\\ 6/7=0.857142\;857142\cdots. \end{array}

Let’s look at the arithmetic of the long division. If we want to find the decimal expansion of {1/7}, we first divide {10} by {7}, which gives the quotient {1} and remainder {3}. Then we divide {30} by {7}, which gives the quotient {4} and remainder {2}, and so on. Observe that there is a cycle of length {6} in the sequence of the remainders: { \{3, 2, 6, 4, 5, 1,\quad 3, 2, 6, 4, 5, 1, \quad \cdots\}}. Note that all possible non-zero remainders (i.e. {1, 2, 3, 4, 5, 6}) appear and that

\displaystyle \begin{array}{rl} 10&\equiv 3\quad (\textrm{mod } 7)\\ 10^2&\equiv 2\quad (\textrm{mod } 7)\\ 10^3&\equiv 6\quad (\textrm{mod } 7)\\ 10^4&\equiv 4\quad (\textrm{mod } 7)\\ 10^5&\equiv 5\quad (\textrm{mod } 7)\\ 10^6&\equiv 1\quad (\textrm{mod } 7). \end{array}

In other words, {10} is a generator of the multiplicative group {\left(\mathbb{Z}/7\mathbb{Z}\right)^\times } (the set of integers between 1 and {6=7-1} which are relatively prime to {7}, or equivalently, the congruence classes of integers relatively prime to {7}). In this case, we say {10} is a primitive root modulo {7}.

Therefore, to look for a number {p} whose expansion of {1/p} has the “cyclic” property similar to that of {1/7}, we have to find a {p} such that {\{1, \cdots , p-1\}} can all be generated by {10} (multiplicatively). Since {1} can be generated by {10}, {10} is relatively prime to {p}. But then, since all numbers between {1} and {p-1} can also be generated by {10}, they are all relatively prime to {p}. This shows that {p} must be prime. In other words, we look for primes {p} such that {10} is a primitive root modulo {p}.

Definition 1 Given a sequence of numbers {a=(a_1, \cdots, a_n)} (not necessarily distinct, and may contain {0}), we say {b} is a cyclic permutation of {a} if {b=(a_k, a_{k+1}, \cdots , a_n, a_1, \cdots, a_{k-1})}.

To conclude the discussion above,

Theorem 2 Let {1<p\in \mathbb{N}}, suppose {\frac{1}{p}} has the expansion

\displaystyle \frac{1}{p}=0.a_1 a_2\cdots a_n\;a_1a_2\cdots a_n\;a_1a_2\cdots a_n\cdots.

Then all the repetends of the decimal expansions of {\frac{2}{p}, \cdots , \frac{p-1}{p}} consist only of the cyclic permutations of {(a_1, \cdots , a_n)} if and only if {p} is prime and {10} is a primitive root modulo {p}.

For example, it can be shown that {10} is a primitive root modulo {17}. Hence it should have the “cyclic” property exhibited by {7}. Let’s look at the decimal expansions of {\frac{m}{17}} :
recurring17

(So you can now show your friends the magical property of the number {1176470588235294}: {1176470588235294\times 2=2352941176470588} etc. XD) Due to rounding of the decimals, the last digit of each line may not represent the correct digit (at this position) of the infinite expansion.

In general, it seems to be quite hard to find the primitive roots modulo {n}, even if it has one. Note that for any prime {p} , there must be a primitive root, since it can be shown that {\left(\mathbb{Z}/p\mathbb{Z}\right)^\times \cong C_{p-1}}, the cyclic group of order {p-1}. On the other hand, given a number {a} (say {10}), there are methods to test whether {a} is a primitive root modulo {p} or not, by considering its order {\mathrm{ord}(a)}, which must divide {\varphi(p)=p-1} by Lagrange’s theorem. (Here \varphi is the Euler’s totient function, which counts the number of congruence classes (\textrm{mod }p) relatively prime to p. ) Notice that a is a primitive root if and only if \mathrm{ord}(a)=p-1 (so that it generates the whole group (\mathbb{Z}/p\mathbb{Z})^\times). Therefore we only have to check that for all the prime factors {p_i} of {p-1}, {a^{\frac{p-1}{p_i}}\not \equiv 1\quad (\textrm{mod }p)}. Hence the condition in Theorem 2 is equivalent to {p} is prime and that for all prime factors {p_i} of {p-1},

\displaystyle 10^{\frac{p-1}{p_i}}\not \equiv 1 \quad (\textrm{mod }p).

Finally, we give the primitive root table (copied from Wikipedia) of all primes (and some others) less than 100: primitive root table

If {10} appears in the second column of the table, then {10} is a primitive root modulo {n}. For example, 10 is a primitive root modulo the following numbers, and so these numbers display the “cyclic” property:

\displaystyle 7, 17, 19, 23, 29, 47, 59, 61, 97.

For example, when p=23 (the repetend has length 23-1=22):

recurring23

Advertisements
This entry was posted in Number Theory. Bookmark the permalink.

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