Determine the smallest natural number $n > 2$, or show that no such natural numbers $n$ exists, that satisfy the following condition: There exists natural numbers $a_1, a_2, \dots, a_n$ such that \[ \gcd(a_1, a_2, \dots, a_n) = \sum_{k = 1}^{n - 1} \underbrace{\left( \frac{1}{\gcd(a_k, a_{k + 1})} + \frac{1}{\gcd(a_k, a_{k + 2})} + \dots + \frac{1}{\gcd(a_k, a_n)} \right)}_{n - k \ \text{terms}} \]
Problem
Source: INAMO 2020 P8
Tags: number theory, construction, Bounding, bait
IndoMathXdZ
14.10.2020 08:00
Fake NT. The main difficulty of this problem is to notice that when $n = 4$, there are $6$ terms in the right which is too freaking hard to bash. So find a pair. The answer is $n = 4$, which is achieved by pairs $(2,6,6,6)$. We just need to prove that $n = 3$ is not achievable. Now, we have \[\gcd(a_1, a_2, a_3) = \frac{1}{\gcd(a_1, a_2)} + \frac{1}{\gcd(a_1, a_3)} + \frac{1}{\gcd(a_2, a_3)} \]Notice that if $k \mid \gcd(a_1, a_2, a_3)$, then $k \mid \gcd(a_i, a_j)$, $\forall 1 \le i < j \le 3$. Thus, \[ k \le \gcd(a_1, a_2, a_3) \le \frac{3}{k} \]forcing $k \le 1$. Therefore, $\gcd(a_1, a_2, a_3) = 1$. Now, just bash $\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1$. WLOG $x \le y \le z$, and let $x = \gcd(a_1, a_2), y = \gcd(a_1, a_3), z = \gcd(a_2, a_3)$ for simplicity. \[ \frac{3}{z} \ge \frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1 \]Thus, $z \le 3$, and for obvious reasons $z > 1$. If $z = 3$, then we must have equality, forcing $x = y = z = 3$, but $\gcd(x,y,z) \mid \gcd(a,b,c)$, which is a contradiction. If $z = 2$, then we must have $\frac{1}{y} + \frac{1}{z} = \frac{1}{2}$. Easy case bash just like this will give us $(y,z) = (4,4)$ or $(3,6)$. The first one is impossible as $4 \mid \gcd(a_1, a_3), \gcd(a_2, a_3)$ shows that $4 \mid a_1, a_2$ forcing $4 \mid \gcd(a_1, a_2)$. The second one is also impossible as $2 \mid \gcd(a_1, a_2), \gcd(a_2, a_3)$ shows that $2 \mid a_1, a_3$, but $\gcd(a_1, a_3) = 3$.
naman12
14.10.2020 08:15
First we show that $n=3$ is not achievable. If $\gcd(a_1,a_2,a_3)=\frac 1{\gcd(a_1,a_2)}+\frac 1{\gcd(a_1,a_3)}+\frac 1{\gcd(a_2,a_3)}$, we clearly see no two are relatively prime. Furthermore, the gcd of all three must be 1, as we can note \[\gcd(a_1,a_2)\geq 2\implies \frac 1{\gcd(a_1,a_2)}+\frac 1{\gcd(a_1,a_3)}+\frac 1{\gcd(a_2,a_3)}\leq\frac 32\]However, we can now do dumb bounding. Assuming an order $\gcd(a_1,a_2)\leq\gcd(a_1,a_3)\leq\gcd(a_2,a_3)$, we see that $\gcd(a_1,a_2)=2,3$. If it is $2$, we get that $\gcd(a_1,a_3)\leq 4$. If it is $2$ or $4$, we get that $2$ divides each number, absurd. If it is $3$, we get that the last gcd is $6$, once again implying that $2$ divides all numbers. Now, to finish off, if $\gcd(a_1,a_2)=3$, we get that $\gcd(a_1,a_3)=3$, a contradiction. Thus $n=3$ does not work. To check $n=4$ works, we look at small pairs of integers. And indeed we find one that works - $(2,6,6,6)$. I hypothesize this is the only one, which probably can be solved by casework which I am too lazy to do.
anggalol
14.10.2020 08:29
Where P1-P4?