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.

  • 1
    $\begingroup$ What is this mod function? $\endgroup$ – Ovi Jul 18 '18 at 0:24
  • $\begingroup$ @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$. $\endgroup$ – Arnaud Mortier Jul 18 '18 at 0:27
  • $\begingroup$ @ArnaudMortier Ah got it thanks $\endgroup$ – Ovi Jul 18 '18 at 0:29
  • $\begingroup$ How far have you been looking for a counterexample? How far do you know this to be true? $\endgroup$ – Arnaud Mortier Jul 18 '18 at 0:36
  • 1
    $\begingroup$ 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! $\endgroup$ – farshid evazabadian Jul 18 '18 at 0:42

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

  • $\begingroup$ +1 very elegant. $\endgroup$ – user159517 Aug 4 '18 at 16:15
  • $\begingroup$ 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. $\endgroup$ – zhoraster Aug 4 '18 at 16:44
  • $\begingroup$ @zhoraster Right, I forgot that the OP only wanted a hint. I don't like spoiler tags for long solutions, but thanks :) $\endgroup$ – 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$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.