2007 CMO 第 2 题

Show that:
1) If $2n-1$ is a prime number, then for any $n$ pairwise distinct positive integers $a_1, a_2, \ldots , a_n$ , there exists $i, j \in \{1, 2, \ldots , n\}$ such that
$$\frac{a_i+a_j}{(a_i,a_j)} \geq 2n-1$$
2) If $2n-1$ is a composite number, then there exists $n$ pairwise distinct positive integers $a_1, a_2, \ldots , a_n$ , such that for any $i, j \in \{1, 2, \ldots , n\}$ we have
$$\frac{a_i+a_j}{(a_i,a_j)} < 2n-1$$

Here $(x,y)$ denotes the greatest common divisor of $x,y$ .

表明：

1) 如果 $2n-1$ 是质数，则对于任何 $n$ 成对不同的正整数 $a_1, a_2, \ldots , a_n$ ，存在 $i, j \in \{1, 2, \ldots , n\}$ 使得

$$\frac{a_i+a_j}{(a_i,a_j)} \geq 2n-1$$

2) 如果 $2n-1$ 是合数，则存在 $n$ 两对不同的正整数 $a_1, a_2, \ldots , a_n$ ，这样对于任何 $i, j \in \{1, 2, \ldots , n\}$ 我们有

$$\frac{a_i+a_j}{(a_i,a_j)} < 2n-1$$

这里 $(x,y)$ 表示 $x,y$ 的最大公约数。