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

• What is this mod function? – Ovi Jul 18 '18 at 0:24
• @Ovi $\mod(a,b)$ stands for the residue of $a$ modulo $b$. It is common in math softwares. Hence, $\mod(a,b)>0$ is equivalent to $b\not\mid a$. – Arnaud Mortier Jul 18 '18 at 0:27
• @ArnaudMortier Ah got it thanks – Ovi Jul 18 '18 at 0:29
• How far have you been looking for a counterexample? How far do you know this to be true? – Arnaud Mortier Jul 18 '18 at 0:36
• I edited the problem notation, so it is clearer now. I have tried for n=2,3,4,5,6. Then I stopped and guessed it might be true. I coded the problem with an optimisation software GAMS to find the minimum value of summation of a(i) for all the numbers lower than 100, however I am not done yet! – farshid evazabadian Jul 18 '18 at 0:42

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

• +1 very elegant. – user159517 Aug 4 '18 at 16:15
• Wonderful! I'm not sure though that the reference to CRT is needed. Also I think you may hide some parts of your answer under the spoiler tag, as OP asked not to post a complete solution. – zhoraster Aug 4 '18 at 16:44
• @zhoraster Right, I forgot that the OP only wanted a hint. I don't like spoiler tags for long solutions, but thanks :) – nbarto Aug 4 '18 at 16:49

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