Travel

In a country there are $n$ cities, numbered from $1$ to $n$. The traveler is initially in city $1$ and wants to visit all the cities. We know that he acts according to the following algorithm: first, an integer $m$ is randomly chosen in the interval [1, n - 1]. After that, cities are visited in the order of 1,\ 1 + m \bmod n,\ 1 + (2 \cdot m) \bmod n,\ \ldots and so on, until it gets to an already visited city. Note that this process will always be finite, since the set of cities is finite. Find the probability that the traveler will visit all the cities of the country.