(This is a cleaned-up, somewhat revised/expanded version of my Twitter thread here.)
Among math enthusiasts, the number \( 142857 \) is pretty cool. Move its leftmost digit to the right, and you get \( 428571 \), which is three times the original: \( 428571 = 142857 \times 3 \). Do this again, and you get \( 285714 \), which is two times the original: \( 285714 = 142857 \times 2 \). We can keep doing this until we return to \( 142857 \), as follows:
\[ \begin{align*} 142857 &= 142857 \times 1 & 142857 \times 1 &= \color{red} 142857 \\ 428571 &= 142857 \times 3 & 142857 \times 2 &= 2857\color{red}14 \\ 285714 &= 142857 \times 2 & 142857 \times 3 &= 42857\color{red}1 \\ 857142 &= 142857 \times 6 & 142857 \times 4 &= 57\color{red}1428 \\ 571428 &= 142857 \times 4 & 142857 \times 5 &= 7\color{red}14285 \\ 714285 &= 142857 \times 5 & 142857 \times 6 &= 857\color{red}142 \end{align*} \]
Numbers that give you consecutive multiples when cycled as above are referred to as cyclic numbers.
If we want to be strict about it, the only nontrivial cyclic number in our usual base \( 10 \) (decimal) is \( 142857 \). However, if we relax the rules a little bit to allow for some leading zeros (i.e., zeros at the beginning), we get other interesting examples, such as \( 0588235294117647 \). I will leave it to the reader to verify that the aforementioned \(16\)-digit number is cyclic, giving its multiples from \(1\) to \(16\) as one cycles through its digits.
Anyway, let's go back to \( 142857 \). Where else have most people seen it aside from this context? For those who have used a digital calculator with a \(10\)-digit display, if you divide some whole number by \( 7 \) that is not evenly divisible by such, you will end up with a floating decimal part. In particular, if you divide \( 1 \) by \( 7 \), you get \( 1/7 \approx 0.142857143 \). This isn't quite an exact value, but it's close enough. You can get more precision by using Excel or WolframAlpha, or doing the division by hand. Then, you eventually figure out that
\[ \frac{1}{7} = 0.142857142857\ldots := 0.\overline{142857} \]
wherein the overline indicates a string of digits that repeats infinitely.
One way to view this decimal expansion is as an infinite series: we can write
\[ 0.\overline{142857} = 0.142857 + 0.000000142857 + \dots \]
This is an infinite geometric series, i.e., a sum of the form \( a + ar + ar^2 + \dots \). The first term is \( a = 0.142857 \) and the common ratio is \( r = 0.000001 \). These series converge when \( -1 < r < 1 \), in which case the value of the series is \( a/(1 - r) \). We then have
\[ 0.\overline{142857} = \frac{0.142857}{1 - 0.000001} = \frac{0.142857}{0.999999} = \frac{142857}{999999} = \frac{1}{7}. \]
And indeed, we get that \( 142857 \times 7 = 999999 \).
Similarly, \( 1/17 = 0.\overline{0588235294117647} \), and \( 0588235294117647 \times 17 = 9999999999999999 \).
The above suggests the following: cyclic numbers in base \(10\) are obtained by looking at the base-\(10\) representations of \( 1/n \) for positive integers \( n\). Now, not all values of \( n \) will give a cyclic number. For example, when \(n = 1, 2, 4, 5, 8, 10 \), we get a decimal representation that terminates:
\[ \frac{1}{1} = 1, \frac{1}{2} = 0.5, \frac{1}{4} = 0.25, \frac{1}{5} = 0.2, \frac{1}{8} = 0.125, \frac{1}{10} = 0.1 \]
Other times, we get short repeating blocks that are not all that interesting:
\[ \frac{1}{3} = 0.\overline{3}, \frac{1}{9} = 0.\overline{1}, \frac{1}{11} = 0.\overline{09} \]
Sometimes we get a decimal representation that is not purely periodic, but eventually is:
\[ \frac{1}{6} = 0.1\overline{6}, \frac{1}{12} = 0.08\overline{3}, \frac{1}{14} = 0.0\overline{714285} \]
Now, on to the topic at hand. Consider the expansion of \( 1/13 = 0.\overline{076923} \). This is purely periodic, with repeating block \( 076923 \). And, if we cycle through the digits of \( 076923 \) like we did with \( 142857 \), we get
\[ \begin{align*} 076923 &= 076923 \times 1 & 076923 \times 1 &= \color{red} 076923 \\ 769230 &= 076923 \times 10 & 076923 \times 3 &= 23{\color{red}0769} \\ 692307 &= 076923 \times 9 & 076923 \times 4 &= 3{\color{red}07692} \\ 923076 &= 076923 \times 12 & 076923 \times 9 &= 6923{\color{red}07} \\ 230769 &= 076923 \times 3 & 076923 \times 10 &= 76923{\color{red}0} \\ 307692 &= 076923 \times 4 & 076923 \times 12 &= 923{\color{red}076} \end{align*} \]
This is not quite a cyclic number, because the multiples are not consecutive. And if we go over the multiples that got skipped, as it turns out, they have a cool little cycle thing going on themselves!
\[ \begin{align*} 076923 \times 2 &= \color{red} 153846 \\ 076923 \times 5 &= 3846\color{red}15 \\ 076923 \times 6 &= 46\color{red}1538 \\ 076923 \times 7 &= 53486\color{red}1 \\ 076923 \times 8 &= 6\color{red}15384 \\ 076923 \times 11 &= 846\color{red}153 \end{align*} \]
The above multiplication tables partition the positive integers from \( 1 \) to \( 12 \) into two sets: \( \{ 1, 3, 4, 9, 10, 12 \} \) and \( \{ 2, 5, 6, 7, 8, 11 \} \). Is there anything interesting about this division?
Let's take a quick little detour for a moment. What are the possible remainders when a perfect square is divided by some given prime \( p \)? For instance, when \( p = 3 \), we have \( 0^2 = 0 \) leaves a remainder of \( 0 \) when divided by \( 3\), while \(1^2 = 1 \) and \(2^2 = 4 \) both leave remainders of \( 1 \) when divided by \( 3\). However, no square leaves a remainder of \( 2 \) when divided by \( 3\). In the parlance of number theory, we say that \( 0 \) and \( 1 \) are quadratic residues mod \( 3 \), while \( 2 \) is a quadratic nonresidue mod \( 3 \). In the case \(p = 5 \), the quadratic residues mod \( 5\) are \( 0, 1, 4 \); the nonresidues are \(2 \) and \( 3 \).
Where does this question even come from, anyway? For high school students with some knowledge of number theory tricks, this can be used to determine whether or not certain equations, usually appearing in contests such as the International Mathematical Olympiad, have integer solutions. The truth is, this question is much, much more important than that. Its solution via the law of quadratic reciprocity, a theorem in which Gauss took great pride, is at the heart of what is known as class field theory; many important results in number theory arise from specific applications of this theory.
Consider now the case wherein \( p = 13\). We have
\[ \begin{align*} 1^2 &\equiv 1 \equiv 12^2 \pmod{13} \\ 2^2 &\equiv 4 \equiv 11^2 \pmod{13} \\ 3^2 &\equiv 9 \equiv 10^2 \pmod{13} \\ 4^2 &\equiv 3 \equiv 9^2 \pmod{13} \\ 5^2 &\equiv 12 \equiv 8^2 \pmod{13} \\ 6^2 &\equiv 10 \equiv 7^2 \pmod{13} \end{align*} \]
As it happens, the residues mod \(13\) (except for \( 0 \)) are precisely the ones in the \( 076923 \) cycle, while the nonresidues mod \(13\) are the ones in the \( 153846 \) cycle! Why is this the case?
Let's go back to \( 142857 \). Recall, as earlier stated, that this appears in the expansion of \( 1/7 \):
\[ \frac{1}{7} = 0.\overline{142857} \]
If we multiply by \( 10 \), everything moves to the left, and we get what looks like a cyclic shift:
\[ \frac{10}{7} = 1.\overline{428571} \]
To complete the cyclic shift, we lop off everything to the left of the decimal point, i.e., we subtract \( 1 \). This leaves us with
\[ \frac{3}{7} = 0.\overline{428571}. \]
This is another way of thinking about \( 142857 \times 3 = 428571. \) Rinsing and repeating gives us
\[ \begin{align*} \frac{30}{7} &= 4.\overline{285714} \\ \frac{2}{7} &= 0.\overline{285714} \end{align*}. \]
We can do this until we go back to \( 1/7 = 0.\overline{142857} \).
Two observations: First, it doesn't matter in which order we perform the multiplication by \( 10 \) and removing of the integer part. For instance, we could've multiplied by \( 10 \) twice in a row to start, giving us
\[ \begin{align*} \frac{100}{7} &= 14.\overline{285714} \\ \frac{2}{7} &= 0.\overline{285714}. \end{align*} \]
Second, when we subtract the integer part, we are subtracting a multiple of \( 7 \) from the numerator, and in fact, the largest possible multiple of \( 7 \). What then remains is precisely the remainder when the original numerator is divided by \( 7 \).
In short, subtracting the integer part is tantamount to reducing the numerator mod \( 7 \), and so cycle shifts can just be viewed as multiplication by \( 10 \) mod \( 7 \). That is, the remainder when \( 10^1 \) is divided by \( 7 \) is \( 3 \), while the remainder when \( 10^2 \) is divided by \( 7 \) is \( 2 \). The key to \( 142857 \) giving all its multiples from \( 1 \) to \( 6 \) is precisely that each of \( 1, 2, \dots, 6 \) appears as a remainder when \( 10^n \) is divided by \( 7 \).
This isn't going to be the case with \( 13 \) and \( 076923 \). For one, there are \( 12 \) possible nonzero remainders, but cyclic shifts will only give us at most \( 6 \) of these. We have, proceeding as in earlier,
\[ \begin{align*} \frac{1}{13} &= 0.\overline{076923} \\ \frac{10}{13} &= 0.\overline{769230} \\ \frac{100}{13} = 7.\overline{692307} \Rightarrow \frac{9}{13} &= 0.\overline{692307} \end{align*} \]
and so on and so forth. You don't have to start with \( 1 \), either:
\[ \begin{align*} \frac{2}{13} &= 0.\overline{153846} \\ \frac{20}{13} = 1.\overline{538461} \Rightarrow \frac{7}{13} &= 0.\overline{538461} \\ \frac{70}{13} = 5.\overline{384615} \Rightarrow \frac{5}{13} &= 0.\overline{386415} \\ &\vdots \end{align*} \]
In the language of group/field theory: if \( p \) is a prime, then the ring of integers mod \( p \), is in fact a field, usually written as \( \mathbb{F}_p \); the set of nonzero elements \( \mathbb{F}_p^{\times} \) forms a cyclic group under multiplication. That is, there is at least one nonzero \( a \) in \( \mathbb{F}_p \) such that every nonzero element of \( \mathbb{F}_p \) can be written as some power of \( a \). We refer to \( a \) as a generator of \( \mathbb{F}_p^{\times} \), and write \( \mathbb{F}_p^{\times} = \langle a \rangle \).
Taking \( p = 7 \), in \( \mathbb{F}_7 \), \( 10 \) is \( 3 \). We then have \(3^1 = 3, 3^2 = 2\), and so on and so forth, until \(3^6 = 1\). You can verify that each of \(1, 2, 3, 4, 5, 6\)--the units of \(\mathbb{F}_7\)--appears exactly once. This tells us that \( 3 \) generates \( \mathbb{F}_7^{\times} \). In the parlance of number theory, we say that \( 3 \) is a primitive root mod \( 7 \).
On the other hand, in \( \mathbb{F}_{13} \), \( 10 \) does not generate the entire group of units \( \mathbb{F}_{13}^{\times} \); for instance, \( 10^n \ne 2 \) for any \( n \). So, what could be a primitive root mod \( 13 \)?
As the congruence table from earlier suggests, since \( 6^2 \equiv 10 \pmod{13} \), we have \(10 = 6^2\) in \(\mathbb{F}_{13}\). This suggests that \( 6 \) is a primitive root mod 13, and generates \(\mathbb{F}_{13}^{\times} \). Indeed, we can verify that over \( n = 1, 2, \dots, 12 \), \( 6^n \) takes on all values in \( \mathbb{F}_{13}^{\times} \), so \( \mathbb{F}_{13}^{\times} = \langle 6 \rangle \).
Moreover, in \( \mathbb{F}_{13} \), we have that \( 10^n = (6^{2})^{n} = (6^n)^2 \), and so the numbers of the form \( 10^n \) are all perfect squares, of which there are 6. And since \( (-n)^2 = n^2 \), we get two elements of \( \mathbb{F}_{13} \) mapped to the same square, so there are at most \( 12/2 = 6 \) distinct nonzero squares. Thus, in fact, these are all the nonzero perfect squares in \( \mathbb{F}_{13} \), i.e., all the nonzero quadratic residues mod \( 13 \). As it turns out, these form a group as well; the product and quotient of two quadratic residues is also a quadratic residue. This group consists of the elements of the form \( 10^n \), i.e. it is the cyclic subgroup \( \langle 10 \rangle \) of the larger unit group \( \mathbb{F}_{13}^{\times} \).
On the other hand, the nonresidues are not a subgroup, but are the coset \( 6\langle 10 \rangle \) obtained by multiplying \( 6 \) (or some other primitive root) by the above subgroup. This coset is not closed under multiplication, but it is closed under multiplication by \( 10 \), i.e., multiplying an element of this coset by \( 10 \) gives you another element in this same coset.
To conclude, notice that the period of \( 0.\overline{076923} \) is equal to \( 6 \), which is the order of the subgroup \( \langle 10 \rangle \). This is no coincidence. Since \( 10 \) has order \( 6 \) in \( \mathbb{F}_{13}^{\times} \), \( 6 \) is the smallest value of \(n\) such that \( 10^n - 1 \) is divisible by \( 13 \), with \( (10^6 - 1)/13 = 76923 \), or
\[ \frac{1}{13} = \frac{76923}{10^6 - 1} = \frac{0.076923}{1 - 0.000001} = 0.\overline{076923}. \]
Going back to \( p = 7 \), since \( 10 \) generates \( \mathbb{F}_7^{\times} \), we have that \( 10 \) also has order \( 6 \) in \( \mathbb{F}_7^{\times} \), and so \( 1/7 = 0.\overline{142857} \) has period \( 6\) as well.
From the discussion above, when \( p \) is prime, \( 1/p \) yields a cyclic number if and only if \( 10 \) is a primitive root mod \( p \). How frequently does this happen? Does it even happen infinitely often? Emil Artin conjectured, assuming that the primes behave randomly enough, that \( 10 \) is a primitive root mod \(p\) about 37% of the time. For where that figure comes from, I will defer to M. Ram Murty's exposition here.
A proof of this conjecture would hinge heavily on the assumption that the primes behave "randomly enough." Christopher Hooley gave a conditional proof that this randomness does hold, subject to the generalized Riemann hypothesis, which is an extension of a notoriously difficult unsolved problem.
Exercises
- By looking at the decimal expansion of \( n/11 \), verify that \( 9n \) and \( 9(11 - n) \) are reverses of each other for \( n = 1, 2, \dots, 10 \).
- After \( 17 \), what is the next positive integer \( n \) for which the decimal expansion of \( 1/n \) gives a cyclic number? (You might want to use a computer for this one.)
- Prove Midy's theorem: If \( p > 5 \) is a prime and the decimal representation of \( a/p = 0.\overline{a_1a_2\dots a_{2k}} \) has period \( 2k \), then
\[ a_1a_2 \dots a_{k} + a_{k+1}a_{k+2}\dots a_{2k} = 10^k - 1. \] (In the above are concatenated digits, not products. For instance, with \( p = 7, a = 1 \), we have \( 1/7 = 0.\overline{142857} \) which has period \( 2k = 6\), and \(142 + 857 = 999 = 10^3 - 1 \).) - There is no need to limit ourselves to base \( 10 \); show that the above condition for \( 1/p \) to generate a cyclic number in base \( 10 \) remains true if we replace \( 10 \) with any base \( b > 1 \). Show then that for any prime number \( p \), there is always a base \( b > p \) for which the base-\( b \) representation of \( 1/p \) generates a cyclic number.
- Is there a composite number \( n \) for which \( 1/n \) generates a cyclic number (in base \( 10 \) )? If so, find the smallest such; otherwise, explain why there is none. How about in other bases \( b \)?
- Show that if \(b \) is a perfect square, then there are no nontrivial cyclic numbers in base \(b \).
Comments
Post a Comment