Corollary of a well-known fact

When students learn about decimals, they're told that every fraction either has a terminating decimal expansion or a repeating decimal expansion. The previous post gives a constructive proof of the converse: given a repeating fraction (in any base) it shows how to find what rational number it corresponds to.

Maybe you learned this so long ago that it seems obvious. But here's a corollary that I don't believe is so obvious.

For any positive integer n and for any integer b > 1, with n and b relatively prime, there is some number of the form b^k - 1 which is divisible by n.

So if I take some number, say 37, I can find a hexadecimal number consisting entirely of Fs which is divisible by 37. In fact FFFFFFFFF will do the trick. This is just the statement above with b = 16.

How does this follow from every rational number having a repeating decimal expansion?

Write 1/n as a repeating decimal in base b. (The assumption that n and b are relatively prime implies that the decimal repeats.) If the period of this decimal is k, then the previous post shows that 1/n is a multiple of 1/(b^k - 1). It follows that n is a divisor of b^k - 1.

Related post: A bevy of ones

The post Corollary of a well-known fact first appeared on John D. Cook.