Prove that $\sum\limits_{i=1}^{n} a_i\geq n^2$.

Question

A hint can be helpful, but not a whole solution.

The Problem (conjecture):

Given a natural number $n \geq 1$ and a sequence of natural numbers $(a_i)_{1 \leq i \leq n}$ in which for every pair $(i,j)$ with $i \neq j,$ we have $$\gcd(a_i,a_j)\nmid i-j$$ prove that $\sum\limits_{i=1}^{n} a_i\geq n^2$.

What I have done:

During my research, I ran into this problem and I am not quite sure if it is true. It is clear if we put $a_i=n$ then the problem will be solved and the summation will be equal to $n^2$. I tried to solve this problem.

For example, I showed that $$a_i> max(i,n-i)$$ otherwise, I can put $j=i+a_i$ or $j=i-a_i$ and considering the fact $\gcd(a_i,a_j) \mid a_i,$ then we conclude that $\gcd(a_i,a_j)\mid i-j,$ hence, $a_i> max(i,n-i)$ which means that $a_i\geq \dfrac{n} {2}$.

Moreover, if $a_i\leq n$ and p are prime divisors of $a_i$ by putting $j=i-\dfrac {a_i}{p}$ for $i\geq \dfrac {n} {2}$ and $j=i+\dfrac {a_i}{p}$ for $i\leq \dfrac {n} {2}$ we could conclude that $a_i \mid a_j$.

I could go further, but it is not enough to prove the conjecture. I also tried Induction and considered that the property holds for every $n\leq k$ and then try to prove the theorem for $n= k+1$ but again, there are some issues that I could not go further.

Answer 1

Just some ideas: if $a_n \geq 2n - 1$, you can proceed by induction. Hence you may assume that $n \leq a_n \leq 2n - 1$. In this case your second observation becomes quite a bit stronger. Indeed, for any prime $p$ dividing $a_n$ we may take $i = n$ and $j = n - \frac{a_n}{p}$. Note that $1 \leq j < n$ exactly by our condition $n \leq a_n \leq 2n - 1$.

Answer 2

Your conjecture is true.

If you want only a hint, stop reading after recalling that $\gcd(a_i,a_j) \mid i-j$ is equivalent to the solvability of the system of congruences $$ \left\{ \begin{align*} x \equiv i \pmod {a_i} \\ x \equiv j \pmod {a_j}\end{align*}\right.$$

---

By the Chinese remainder theorem, we can formulate the problem equivalently as follows: consider $n$ arithmetic progressions in $\mathbb Z$, $(S_i)_{1 \leq i \leq n}$ with $i \in S_i$ for all $i$ and with differences $a_i$. That is, $S_i = i + a_i \mathbb Z$. If the $S_i$ are pairwise disjoint, prove that $\sum a_i \geq n^2$.

The conclusion remains true even without the hypothesis that $i \in S_i$:

If the $S_i$ are disjoint, they are also disjoint mod $a_1 \cdots a_n$, and hence $$\begin{align*} \sum_{i=1}^n\# (S_i \bmod a_1 \cdots a_n) & \leq a_1 \cdots a_n \\ \sum_{i=1}^n \prod_{j \neq i} a_j &\leq \prod_{i=1}^n a_i \end{align*}$$ divide by the RHS to obtain $$\sum_{i=1}^n\frac1{a_i} \leq 1$$ And by AM-HM $$\sum_{i=1}^n a_i \geq n^2$$

Also from AM-HM we have that equality occurs iff $a_1 = \cdots = a_n = n$.