Cyclotomic polynomials and repeating decimals
Ever since I was a small child I have been fascinated with repeating decimals, decimal expansions that end up repeating a sequence of digits indefinitely. For example:
, which repeats the four digits 2970 again and again. In this particular example, the digit string 2970 is called the reptend, and the decimal is said to have period length 4. Over the years, my intent shifted specifically to studying decimals between 0 and 1 whose digits started repeating right after the decimal point, and I started seeing the repeating digits more as their own separate entity with addition and multiplication rules that just happened to be isomorphic to the addition and multiplication of repeating decimals. In this post, I will attempt to explain some of the many discoveries and surprises I found when studying these numbers.
Rationality of Repeating Decimals
One of the first obvious things to notice about repeating decimals is that the numbers they describe are always rational. The proof of this fact is simple, and many readers have probably already seen it. It amounts to showing that each repeating decimal number x can be expressed as an infinite geometric series (1):
In this series, x0 is the part of the decimal before the repeating digits, r is the reptend as an integer, p is the period length, and s is the number of digits after the decimal point before the reptend. Summing the series reveals that
. Because x0 is rational (as it is a terminating decimal) and the numerator and denominator of the fraction are integers, it follows that the sum of the two is also rational. Based on the fact that the decimal expansion for x0 terminates after s digits, we can rewrite this expression as (2)
In this expression, t is the integer formed from digits of the decimal before the beginning of the reptend. The numerator and denominator of each fraction are integers, so we have just expressed x as the sum of two rational numbers, which it itself a rational number. This shows that every repeating decimal is a rational number.
It is slightly harder to prove that every rational number is a repeating decimal. Let x be rational. It follows that
for some integers a and b. Now, consider the sequence of reals s defined by (3):
Let n be any positive integer. As s1 is rational and sn consists of an integer subtracted from an integer multiple of sn - 1, it follows by induction that sn is rational. Similarly, it follows by induction that b·sn is an integer, and because each sn is calculated by taking the fractional part of a real number, it follows that 0 ≤ sn < 1.
Thus sn must be equal to
for some integer an between 0 and b - 1. Since each term is calculated solely from the previous term, then if sn = sn + p for some positive integer p, it follows that sk = sk + p for all integers k greater than n. Because sn can take on only a finite number of values, a duplicate term in the sequence like this must happen eventually. This reasoning suffices to show that the terms in s eventually enter into a cycle.
Now, it can be shown inductively that
for n > 1. Because the formula for the nth digit in the decimal expansion of x is
, the decimal expansion of x must also enter into a cycle. Thus, all rational numbers have repeating decimal expansions.
Unit fractions
Now, consider the decimal expansion of a number of the form
, where a is an integer. For this value of x,
, and in all following terms of the sequence, the numerator is made by multiplying the previous numerator by 10 and taking the result mod 2a. Thus, all terms after s1 have even numerators, so s1 does not appear again in the sequence and the first digit in the decimal expansion of x is not part of the reptend. The same logic holds for numbers of the form
, so it can be deduced that all unit fractions whose denominator is a multiple of 2 or 5 have non-repeating digits at the beginning of their repeating decimal expansions.
What about when the denominator is not a multiple of 2 or 5? As it turns out, in this case the reptend will always repeat from the beginning, regardless of the value of the numerator. However, to simplify our calculations, we will only prove this for unit fractions.
To see this, consider equation (2). If our fraction is
, where a is not divisible by 2 or 5, then the right side of equation (2) can be rewritten as a single fraction with integers as its numerator and denominator:
. Rearranging, we get
. Because a, not being divisible by 2 or 5, has no factors in common with 10s, then (10p - 1)t + r must be divisible by 10s, and thus 10s can be factored out of both the numerator and denominator. Therefore, x can be rewritten as
, where r' is an integer less than 10p - 1. This suffices to show that the reptend in the decimal expansion of x starts at the beginning.
An interesting consequence of this observation is that 10p - 1 is a multiple of a. Furthermore, we see that the quotient of these two values, r', is just the reptend of x. This gives a theorem:
Theorem 1a
For every a not divisible by 2 or 5, there exists a value p, equal to the length of the reptend of 1/a, such that a divides 10p - 1. The value (10p - 1)/a is the reptend of 1/a.
Because 10p - 1 divides 10kp - 1 for all k > 1, r divides 10kp - 1 as well. But r does not divide 10n - 1 for any n not divisible by p. If it did, formula (2) with s = t = 0 could be used to show that 1/a repeated after n digits, contradicting our assumption that p did not divide n.
Theorem 1b
For every a not divisible by 2 or 5, there exists a value p, equal to the length of the reptend of 1/a, such that for every integer n, a divides 10n - 1 if and only if p divides n.
As an example, take a = 31:
In this case, the bar over the digits mean that the digits repeat; that is, they make up the reptend. The period length p is 15, and indeed, we see that
. We also can check that 9, 99, 999, 9999... 99999999999999 are not divisible by 31.
Generalization to arbitrary bases
All the logic so far in this post can be generalized straightforwardly from base 10 to any other (integer) base greater than 1; each repeating base-b expansion of digits corresponds to a rational number and vice versa. Unit fractions whose denominators a are coprime to b (not divisible by any prime factor of b; such as indivisibility by 2 or 5 in base 10) are precisely those unit fractions whose base-b expansions have no digits before the reptend begins, and it is those values of a that divide bp - 1 for some value of p, and only multiples of that value, which is what Theorems 1a and 1b have already stated for b = 10:
Theorem 2
For every positive integer a coprime to a base b > 2, there exists a value p, equal to the length of the reptend in the base-b expansion of 1/a, such that for every integer n, a divides bn - 1 if and only if p divides n. The value (bp - 1)/a is the reptend of 1/a.
In the interest of abstraction, the rest of this post will generally speak of base b instead of base 10.
How to find the value of p?
It is an interesting problem to find the value of p corresponding to given a and b. The least trivial case happens when a is prime. From Fermat's little theorem, it is known that when a is prime and coprime to b, a divides ba - 1 - 1. Therefore, p must divide a - 1.
When p = a - 1 for some prime a, a is called a long prime or full reptend prime to base b. The fraction of primes which are long primes to a base is not known, but for most bases it is thought to be equal to Artin's constant, about 0.373956.... When b is a perfect square, no odd prime can be a long prime to base b because for any odd prime a = 2q + 1, bq - 1 = (√b)a - 1 - 1 is divisible by a. In general, there is no way to see what the period length of 1/a will be without checking it.
Given p and b, how do we find a?
Continuing to talk of prime values of a, how would we find all the primes whose reciprocals had a given period length in a given base? Or, given p and b, how do we find a?
For p to be the period length, it is necessary that a divide bp - 1. The simplest way to find these values is to check every prime factor of bp - 1 as a possible value of a. We can check these contenders by defining a sequence tn (4):
The resulting values are just a·sn + 1, where sn is defined as in (3) except the inductive step involves multiplication by b instead of 10. The index of the second occurrence of 1 is the length of the repeat, and we need to check that this index value is p.
Let's use this method for an example where p = 8 and b = 31. We have bp - 1 = 852891037440, which is 28·3·5·13·37·409·1129. Checking each of these prime factors x, we get the sequences:
2: 1, 1, 1, 1, 1, 1, 1, 1, 1...
3: 1, 1, 1, 1, 1, 1, 1, 1, 1...
5: 1, 1, 1, 1, 1, 1, 1, 1, 1...
13: 1, 5, 12, 8, 1, 5, 12, 8, 1...
37: 1, 31, 36, 6, 1, 31, 36, 6, 1...
409: 1, 31, 143, 343, 408, 378, 266, 66, 1...
1129: 1, 31, 961, 437, 1128, 1098, 68, 692, 1...
We need to check the location of the first 1 in each sequence after the initial term. If the initial term is considered the 0th, only two numbers' sequences have the second 1 at the 8th place, which is required for p to be 8. Only x = 409 and x = 1129 satisfy this property, so the only possible values of a are 409 and 1129.
Note that because the terms of t are formed by repeatedly multiplying by b mod x,
. Since x divides bp - 1, tp = 1 for each sequence t, but this is not always the first occurrence of 1 after t0. Equivalently, the base-p expansion of 1/x always repeats after p digits, but it is not always the minimum repeat length.
We see many problems with this method. For one thing, it involves factoring a number whose length is proportional to the value of p. For another, we already showed that p must divide a - 1. This eliminates all values of x except 409 and 1129.
Let y be any factor of p other than p. As all primes whose reciprocals have period length y are factors of by - 1, all primes whose reciprocals have period length p are factors of the quotient (bp - 1)/(by - 1). If we could divide bp - 1 by the product of by - 1 for all factors y of p, the resulting number would still have all possible values of a in its prime factors.
Cyclotomic polynomials
Define a sequence of polynomials as follows (5):
The resulting polynomials will be:
We will now prove that each term of this sequence is a polynomial. Note that the zeroes of xn - 1 are the nth roots of unity, n complex numbers all having 1 as their nth power. Based on the formula for these numbers as the exponential function of imaginary numbers, we can define a set of binomials Bn the product of whose members equals xn - 1:
We can define another set of binomials Sn as follows:
We claim that: (6)
This is trivially true for n = 1. Now assume that it is true for all n < k. In particular, it holds true for all factors of k less than k, which we will call f1, f2.... The expression for each member p(x) of the set Bk contains a fraction k'/k (in the exponent of the constant term) where k' is a non-negative integer less than k. If GCD(k', k) ≠ 1, then this fraction can be reduced to fz'/fz, where fz is some factor of k less than k. As the fraction has been reduced to lowest terms, GCD(fz', fz) = 1. Thus, p(x) is a member of Sfz. In this way, every member of Bk where GCD(k', k) ≠ 1 belongs to a unique set Sfz for some factor fz of k. Also, every member of one of the aforementioned sets also belongs to Bk, as can be seen by multiplying the numerator and denominator of the member's fraction by the factor required to make the denominator k. Thus, there is a one-to-one correspondence between Bk and the other sets.
The remaining members of Bk are those where GCD(k', k) = 1, and their product is equal to
. By our assumption of (6), the denominator is equal to the product of cf(x) for each given value of f. Thus, the product of the members of Sk can be written:
. By definition, this is equal to ck(x). We have just verified (6) for n = k. By induction, (6) holds for all positive integer values of n. Furthermore, (6) defines cn(x) as a polynomial while (5) shows, via polynomial long division, that the coefficients of cn(x) are integers.
We have just proved that each cn(x) is a polynomial with integer coefficients. Because the zeroes of this polynomial are roots of unity, which when plotted on the complex plane appear as points on the unit circle, the polynomials cn(x) are known as cyclotomic polynomials.
Cyclotomic polynomials and repeating decimals
Let's say we find the value of cp(x) at the point x = b. If b is an integer, then cp(b) is also an integer. Let P be the multiset of all prime factors of bp - 1, let Qn be the multiset of prime factors of cn(b). Let f1, f2, f3... be the proper divisors of p. Due to the factorization of bp - 1, the multiset P can be partitioned into the multisets Qf1, Qf2 ... Qp.
Now let f be a proper divisor of p. Because cf(b) is a factor of bf - 1, any prime a from Qf is a prime factor of bf - 1 and hence is not a valid value of a corresponding to the given p and b. The only valid values of a must be in P but not in any Qf. Therefore, they must be in Qp, or equivalently factors of cp(b).
This gives us an easy way to narrow down the possible values of a. The value cp(b) often has fewer than half the number of digits of the value bp - 1. However, we still don't know if every prime factor of cp(b) is a possible value of a. In particular, the only possible values of a are one more than multiples of p.
Let us assume that a divides cp, and a = m·p + 1 for some integer m. Then a divides bp - 1. If 1/a does not have a period length of p and instead has a period length that is some proper divisor k of p, then a divides bk - 1. Since the factorization of bp - 1 into cyclotomic numbers includes every cyclotomic number in the factorization of bk - 1 in addition to cp, we conclude that cp divides
. Since each of the p/k terms on the right hand side is congruent to 1 mod a, a must divide p/k. But a = m·p + 1. This creates a contradiction, whereby a is both greater than and not greater than p. We conclude that the period length of 1/a being a proper divisor of p is impossible.
Theorem 3
The primes a such that 1/a has period length p in base b are precisely the factors of cb one more than mutliples of p.