China Mathematical Olympiad

(1) Let $p=2n-1$ be a prime. Without loss of generality, we assume that $(a_1,a_2,\dots ,a_n)=1$. If there exists $i$ ($1\le i\le n$) such that $p\nmid a_i$, then there exists $j(\ne i)$ such that $p\nmid a_j$. Therefore $p\nmid (a_i,a_j)$. Then we have $$\frac{a_i+a_j}{(a_i,a_j)}\ge \frac{a_i}{(a_i,a_j)}\ge p=2n-1.$$ Next, we consider the case when $(a_i,p)=1,i=1,2,\dots ,n$. Then $p\nmid (a_i,a_j)$ for any $i\ne j$. By the Pigeonhole Principle, we know that there exist $i\ne j$ such that either $a_i\equiv a_j(\mathrm{mod}p)$ or $a_i+a_j\equiv 0(\mathrm{mod}p)$.

Case $a_i\equiv a_j(\mathrm{mod}p)$, we have $$\frac{a_i+a_j}{(a_i,a_j)}\ge \frac{a_i-a_j}{(a_i,a_j)}\ge p=2n-1.$$

Case $a_i+a_j\equiv 0(\mathrm{mod}p)$, we have $$\frac{a_i+a_j}{(a_i,a_j)}\ge p=2n-1.$$ That completes the proof of (1).

(2) We will construct an example to justify the statement. Since $2n-1$ is a composite number, we can write $2n-1=pq$ where $p,q$ are positive integers greater than 1. Let $$\begin{array}{rl}{a}_1& =1,a_2=2,\dots ,a_p=p,a_{p+1}=p+1,\\ a_{p+2}& =p+3,\dots ,a_n=pq-p.\end{array}$$ Note that the first $p$ elements are consecutive integers, while the remainders are $n-p$ consecutive even integers from $p+1$ to $pq-p$.

When $1\le i\le j\le p$, it is obvious that $$\frac{a_i+a_j}{(a_i,a_j)}\le a_i+a_j\le 2p<2n-1.$$ When $p+1\le i\le j\le n$, we have $2|(a_i,a_j)$ and then $$\frac{a_i+a_j}{(a_i,a_j)}\le \frac{a_i+a_j}{2}\le pq-p<2n-1.$$ When $1\le i\le p$ and $p+1\le j\le n$ we have the following two possibilities:

(i) Either $i\ne p$ or $j\ne n$. Then we have $$\frac{a_i+a_j}{(a_i,a_j)}\le pq-1<2n-1.$$ (ii) $i=p$ and $j=n$. Then $$\frac{a_i+a_j}{(a_i,a_j)}=\frac{pq}{p}=q<2n-1.$$ That completes the proof.