by Willie Wong
Here’s something a bit random for Friday. (Presumably this actually is quite well-known; but having never taken a course in number theory…)
Question: Given a fraction m/n in lowest terms, and expand it in “decimal notation” in a number base b. What are the conditions on m, n, and b that guarantees that the expansion eventually consists of a single repeating “digit”? (Note, we can clearly assume 0 < m < n.)
To make the question more clear, let’s look at some examples in base b = 10. Obviously, if n = 1, then the fraction is in fact integral, and its expansion is has a repeated digit 0. If n = 2, the decimal expansion is either or . Similarly n = 4, 5, 8, 10 all have terminating decimals, so repeats the digit 0 eventually. n = 3,6,9 on the other hand, will lead to repeating digits other than 0, whereas n = 7 will lead to a repetition of a string of the 6 digits …142857142857…
Here’s the solution. Suppose m/n has an expansion of the prescribed form. Recall that a “decimal expansion”
is in fact a short hand for
So the criterion specified in the question is equivalent to the condition that
There exists some integer K, a number , and a digit d such that
which corresponds to the decimal expansion
The infinite sum on the far right can be solved: . Multiplying the expression through by we have
Now, by redefining , we can replace . So we can set arbitrarily large. Which means that by doing so, after setting the left hand side to lowest terms, we can “remove” from n any prime factors that also divides . To be more precise: suppose is a prime such that and does not divide . (So that p goes into n exactly times.) Now suppose also, then the fraction , when written in lowest terms, has a denominator that cannot be divided by . Repeating this for all common prime factors of n and b we can get rid of all common prime factors from the denominator. Let us denote by the number with all the prime divisors of removed.
Our equation then implies that there exists some integer that is coprime with such that
which means that must divide . That is
Answer: Let be the number with all prime divisors of removed. Then must divide .
For base b = 10, (b-1) = 9. This means that any n for which the decimal expansion is eventually repeating with period 1 must have the form
where are non-negative integers, and is one of 0, 1, or 2.