5. The government has decided to privatize civil aviation. For each pair of the country's 127 cities, the connecting airline is sold to one of the private airlines. Each airline must make all the purchased air routes one-way, but in such a way as to ensure the possibility of flying from any city to any other (possibly with several layovers). What is the maximum number of companies that can buy the air routes?
# Answer: 63.

Solution. For integers $k$ and $n$, let $N_{k, n}$ denote the remainder when $k \cdot n$ is divided by the prime number 127. First, we prove that if $k$ is not divisible by 127, then the numbers $N_{k, 0}, \ldots, N_{k, 126}$ are distinct. Indeed, if for some $0 \leqslant a < b \leqslant 126$ the numbers $a k$ and $b k$ give the same remainder when divided by 127, then the number $b k - a k = (b - a) k$ is divisible by 127, which is impossible since $0 < b - a < 127$. Therefore, the numbers $N_{k, 0}, \ldots, N_{k, 126}$ take all values from 0 to 126, and $N_{k, 127}$ is zero.

Now let's proceed to solving the problem. Take an arbitrary airline participating in the privatization. Since it must ensure communication between all cities on its own, for any city, it must have an airline leading to this city and an airline leading out of it. Thus, each city must be connected by at least two airlines belonging to this company. Therefore, the company must have at least 127 airlines. The total number of airlines is $\frac{127 \cdot 126}{2} = 127 \cdot 63$, so the number of airlines does not exceed 63.

Now we show that exactly 63 airlines could have participated in the privatization. Number the cities from 0 to 126. For any $k = 1, \ldots, 63$, assign to the $k$-th airline the airlines leading from the city with number $N_{k, n}$ to the city with number $N_{k, n+1}$, where $n \in \{0, \ldots, 126\}$. By the above, such airlines, starting and ending in city 0, cyclically pass through (in a certain order) all other cities. Thus, the $k$-th airline can ensure a flight from any city to any other. It remains to check that no airline is assigned to two companies at the same time. Indeed, let $k, m \in \{1, \ldots, 63\}$ and some airline is assigned to both the $k$-th and $m$-th companies. Then there exist $i, j \in \{1, \ldots, 126\}$ such that $N_{k, i} = N_{m, j}$ and $N_{k, i+1} = N_{m, j+1}$. We get $N_{k, i+1} - N_{k, i} = N_{m, j+1} - N_{m, j}$, which implies $k = m$.