9.3. On the board, 100 pairwise distinct natural numbers $a_{1}, a_{2}, \ldots, a_{100}$ were written. Then, under each number $a_{i}$, a number $b_{i}$ was written, obtained by adding to $a_{i}$ the greatest common divisor of the remaining 99 original numbers. What is the smallest number of pairwise distinct numbers that can be among $b_{1}, b_{2}, \ldots, b_{100}$?

(S. Berlov)
# Answer. 99.

First solution. If we set $a_{100}=1$ and $a_{i}=2 i$ for $i=1,2, \ldots, 99$, then $b_{1}=b_{100}=3$, so there will be no more than 99 different numbers among the numbers $b_{i}$. It remains to prove that there will always be 99 different numbers among the numbers $b_{i}$.

Without loss of generality, we can assume that $a_{1}a_{j} \geqslant a_{i}+d_{i}=b_{i}$
$$

which implies $b_{i} \neq b_{j}$. Thus, we have established that $b_{j} \neq b_{i}$ when $i \neq k \neq j$. Therefore, all 99 numbers $b_{i}$ for $i \neq k$ are different.

Second solution. We will provide another proof that there are at least 99 different numbers among the numbers $b_{i}$. We will again use the notation $d_{i}$ from the previous solution; we will also assume that $a_{1}<\ldots<a_{100}$.

Let $c_{i}=a_{i+1}-a_{i}$. Suppose $c_{\ell}$ is the minimum of the numbers $c_{1}, c_{2}, \ldots, c_{99}$. We will show that if $i<j$ and $i \neq \ell+1 \neq j$, then the numbers $b_{i}$ and $b_{j}$ are different. This will again lead to the required result.

Assume that $i<j-1$. Then $i \leqslant 98$, and the numbers $a_{i+1}$ and $a_{i+2}$ are divisible by $d_{i}$. Therefore, $d_{i} \leqslant a_{i+2}-a_{i+1}<a_{j}-a_{i}$, which implies

$$
b_{i}=a_{i}+d_{i}<a_{i}+\left(a_{j}-a_{i}\right)=a_{j}<b_{j}
$$

Now suppose $j=i+1$. Then $i \neq \ell+1$ and $i \neq \ell$ (since $j \neq \ell+1$). Therefore, the numbers $a_{\ell}$ and $a_{\ell+1}$ are divisible by $d_{i}$. Hence, $d_{i} \leqslant$ $\leqslant a_{\ell+1}-a_{\ell}=c_{\ell} \leqslant c_{i}$, which leads to

$$
b_{i}=a_{i}+d_{i} \leqslant a_{i}+c_{i}=a_{i+1}=a_{j}<b_{j}
$$

Thus, in both cases, we have obtained that $b_{i}<b_{j}$, as required.