Prove that $\sum\limits_{i=1}^{n} a_i\geq n^2$. 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. 


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$.
