Maths Olympiad Prep

Track / Stage 6 / 380 of 400 #1380 of 1964

Problem 1380

National olympiad, first round
Number theory Difficulty 6.9 Prove it

Theorem 16 If bb is a prime and 10 is a primitive root of bb, then
1b,2b,,b1b\frac{1}{b}, \frac{2}{b}, \ldots, \frac{b-1}{b}

have cycles consisting of b1b-1 digits, and they differ only by a cyclic permutation.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

For each 1jb11 \leqslant j \leqslant b^{-1}, it is clear that (j,b)=1(j, b)=1. By Lemma 4, each fraction in (58) must be a pure repeating decimal when converted to a decimal, and the length of the repeating cycle is b1b-1. Let
1b=0.a˙1a2a˙b1\frac{1}{b}=0 . \dot{a}_{1} a_{2} \cdots \dot{a}_{b-1}

If {x}\{x\} denotes the fractional part of xx, it is easy to see from (59) that for any integer m0m \geqslant 0,
{10mb}={10m+b1b}\left\{\frac{10^{m}}{b}\right\}=\left\{\frac{10^{m+b-1}}{b}\right\}

Thus, for integers m0m \geqslant 0, the set of numbers
{10mb}(m=0,1,2,)\left\{\frac{10^{m}}{b}\right\} \quad(m=0,1,2, \cdots)

contains at most b1˙\dot{b-1} distinct numbers. Furthermore, since 10 is a primitive root of bb,
100=1,10,102,,10b2,10^{0}=1,10,10^{2}, \cdots, 10^{b-2},

these b1b-1 numbers are pairwise incongruent modulo bb. Therefore, in the set (60), there are exactly b1b-1 distinct numbers, i.e.,
{1b},{10b},,{10b2b}\left\{\frac{1}{b}\right\},\left\{\frac{10}{b}\right\}, \cdots,\left\{\frac{10^{b-2}}{b}\right\}

On one hand, we know that
1,10,,10b21,10, \cdots, 10^{b-2}

exactly runs through the reduced residue system of bb, 1,2,,b11,2, \cdots, b-1. Thus, (61) is precisely a permutation of the following array:
1b,2b,,b1b\frac{1}{b}, \frac{2}{b}, \cdots, \frac{b-1}{b}

On the other hand, it is easy to see from (61) and (59) that each number in (61) is a pure repeating decimal, all with a repeating cycle length of b1b-1, and each is composed of the same b1b-1 digits in the repeating cycle of 1b\frac{1}{b}, but with a different cyclic permutation. This is exactly what we need to prove.

More generally, we have the following result.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.