5. The government has decided to privatize civil aviation. For each pair of 202 cities in the country, the airline connecting them is sold to one of the private airlines. The mandatory condition for the sale is as follows: each airline must 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 airlines?
Answer: 101.

Solution. First, we prove that for $k \in \{1, \ldots, 100\}$, the remainders of the numbers

$$
0, k, 2k, 3k, \ldots, 99k, 100k
$$

when divided by the prime number 101 are distinct. Indeed, if for some $0 \leqslant a < b \leqslant 100$ the numbers $ak$ and $bk$ give the same remainder when divided by 101, then the number $bk - ak = (b-a)k$ is divisible by 101, which is impossible because $1 \leqslant k \leqslant 100$ and $0 < b-a < 101$. Now consider the numerical sequence

$$
\mathcal{P}_{k}: \quad 0, k, 2k, 3k, \ldots, 99k, 100k, 100k+101, 99k+101, \ldots, 3k+101, 2k+101, k+101, 101
$$

Notice that all the remainders of the numbers in $\mathcal{P}_{k}$ when divided by 202 are distinct. Indeed, if two different numbers in $\mathcal{P}_{k}$ give the same remainder when divided by 202, then they also give the same remainder when divided by 101. Then these numbers are of the form $ak$ and $ak + 101$, which is impossible because they have different parities. Since $\mathcal{P}_{k}$ contains exactly 202 numbers, their remainders take all possible values from 0 to 201.

Now let's move on to solving the problem. Since each airline must ensure communication between all cities, it must have at least 201 air routes. The total number of air routes is $\frac{202 \cdot 201}{2}$, so the number of airlines does not exceed 101.

We will now show that the number of airlines participating in the privatization of air routes can be exactly 101. Let's agree to denote the remainder of the division of an integer $a$ by 202 by $\langle a \rangle$. We will number the cities from 0 to 201. For any $k = 1, \ldots, 100$, we will assign to the $k$-th airline the air routes connecting cities with numbers $\langle a \rangle$ and $\langle b \rangle$, where $a$ and $b$ are adjacent numbers in the sequence $\mathcal{P}_{k}$. Since the remainders of the numbers in $\mathcal{P}_{k}$ run through (in a certain order) all values from 0 to 201, the airline can ensure travel from any city to any other. Note also that no air route will be assigned to two airlines at the same time. Indeed, let $k$ and $m$ be different numbers from 1 to 100, and $(a, b)$ and $(c, d)$ be pairs of adjacent numbers from the sequences $\mathcal{P}_{k}$ and $\mathcal{P}_{m}$ respectively, such that $\{\langle a \rangle, \langle b \rangle\} = \{\langle c \rangle, \langle d \rangle\}$. Then, by the above, $\{a, b\} = \{c, d\}$, which is impossible since $b - a = k \neq m = d - c$.

We will sell all the remaining air routes from the first hundred airlines to the 101st airline. We will prove that it can also ensure travel from any city to any other. Obviously, it owns the air route $(0, 101)$, since 0 and 101 do not neighbor in the sequence $\mathcal{P}_{k}$ for any $k$. Now we will show that for any $m \in \{1, \ldots, 100\}$, the air routes $(0, 202 - m)$ and $(101, 101 - m)$ also belong to the 101st airline. Indeed, let the route $(0, 202 - m)$ belong to the airline with number $k \leqslant 100$. Then $202 - m = k$, which is impossible since $k + m \leqslant 200$. The second statement is verified similarly. Thus, the 101st airline connects any two cities via the cities 0 and 101.