Suppose you have a fraction a/b where 0 < a < b, and a and b are relatively prime integers. The decimal expansion of a/b either terminates or it has an initial non-repeating part followed by a repeating part.
How long is the non-repeating part? How long is the period of the repeating part?
The answer depends on the prime factorization of the denominator b. If b has the form
b = 2α 5β
then the decimal expansion has r digits where r = max(α, β).
Otherwise b has the factorization
b = 2α 5β d
where d is some integer greater than 1 and relatively prime to 10. Then the decimal expansion of a/b has r non-repeating digits and a repeating part with period s where r is as above, and s is the smallest positive integer such that
d | 10s − 1,
i.e. the smallest s such that 10s − 1 is divisible by d. How do we know there exists any such integer s? This isn’t obvious.
Fermat’s little theorem tells us that
d | 10d −1 − 1
and so we could take s = d − 1, though this may not be the smallest such s. So not only does s exist, we know that it is at most d − 1. This means that the period of the repeating part of a/b is no more than d − 1 where d is what’s left after factoring out as many 2’s and 5’s from b as possible.
By the way, this means that you can take any integer d, not divisible by 2 or 5, and find some integer k such that dk consists only of 9’s.
Related post: Cyclic fractions
And the repeating part starts with floor(log10(d)) zeros?
A typo?
d | 10^(s – 1)
should read:
d | 10^s – 1
Note that in modern computers systems, finding d, alpha and beta costs more that simple division.
> How do we know there exists any such integer s? This isn’t obvious.
Another way of thinking about this is to consider computing the decimal expansion via long division. At each step the state of the division algorithm is a remainder mod d, and you never get 0, so there are at most (d-1) states to loop through.
Moreover I think this tells you that s is a factor of (d-1): the states of the algorithm are the powers of 10 mod d which is a subgroup of the nonzero numbers mod d under multiplication, so Lagrange’s theorem says it must divide (d-1).
Excellent! Two quick comments. That the decimal expansion of a repeating 1/n has at most n-1 digits, follows from the pigeon hole principle, as David points out above. Your argument that d|10^(d-1) – 1 uses Fermat’s Theorem, which assumes that d is prime. If d=21, then 10^20-1 = 3^2*11*41*101*271*3541*9091*27961, which is not divisible by 21.
[I was unable to get the formatting of this comment to work. Please follow this link to the comment. — John]