1. The greatest common divisor (GCD) of natural numbers $m$ and $n$ is 1. What is the greatest possible value of the GCD of the numbers $m+2000n$ and $n+2000m?$
1. Let $a=2000 m+n, b=2000 n+m, d$ be the greatest common divisor of $a$ and $b$. Then $d$ also divides the numbers

$$
2000 a-b=\left(2000^{2}-1\right) m \quad \text { and } \quad 2000 b-a=\left(2000^{2}-1\right) n .
$$

Since $m$ and $n$ are coprime, $d$ is also a divisor of the number $2000^{2}-1$ (see comment). On the other hand, for $m=2000^{2}-2000-1, n=1$, we get $a=\left(2000^{2}-1\right)(2000-1), b=2000^{2}-1=d$.

Comment. We used the following statement: if $m$ and $n$ are coprime, then GCD $(d m, d n)=d$. This follows from a more general statement:

$$
\text { GCD }(d x, d y)=d \text { GCD }(x, y) .
$$

We will give a sketch of the proof. Let $p_{1}, \ldots, p_{n}$ be all the prime divisors of the numbers $x, y$ and $d$. Write the prime factorizations of these numbers:

$$
\begin{aligned}
& x=p_{1}^{k_{1}} p_{2}^{k_{2}} \ldots p_{n}^{k_{n}} \\
& y=p_{1}^{l_{1}} p_{2}^{l_{2}} \ldots p_{n}^{n_{n}} \\
& d=p_{1}^{m_{1}} p_{2}^{m_{2}} \ldots p_{n}^{m_{n}}
\end{aligned}
$$

(Some of the numbers $k_{i}, l_{i}$ and $m_{i}$ may be zero. Compare with the comment to problem 4 for 9th grade of the 1995 olympiad.)

Let $\min (p, q)$ denote the smaller of the numbers $p$ and $q$. Then

$$
\text { GCD }(x, y)=p_{1}^{\min \left(k_{1}, l_{1}\right)} p_{2}^{\min \left(k_{2}, l_{2}\right)} \ldots p_{n}^{\min \left(k_{n}, l_{n}\right)}
$$

Similarly,

$$
\text { GCD }(d x, d y)=p_{1}^{\min \left(m_{1}+k_{1}, m_{1}+l_{1}\right)} p_{2}^{\min \left(m_{2}+k_{2}, m_{2}+l_{2}\right)} \ldots p_{n}^{\min \left(m_{n}+k_{n}, m_{n}+l_{n}\right)}
$$

It remains to note that for any $i$ the equality holds

$$
\min \left(m_{i}+k_{i}, m_{i}+l_{i}\right)=m_{i}+\min \left(k_{i}, l_{i}\right)
$$

Another proof can be obtained using the following fact: for any integers $x$ and $y$ there exist integers $a$ and $b$ such that $a x+b y=$ GCD $(x, y)$, see for example $[30]$.