We say distinct positive integers $a_1,a_2,\ldots ,a_n $ are "good" if their sum is equal to the sum of all pairwise $\gcd $'s among them. Prove that there are infinitely many $n$ s such that $n$ good numbers exist. Proposed by Morteza Saghafian
Problem
Source: Iranian TST 2018, third exam day 2, problem 4
Tags: number theory, Iran, Iranian TST
19.04.2018 17:08
I think so that n!+1,n!+2,n!+3......n!+n are good
20.04.2018 16:42
Smita wrote: I think so that n!+1,n!+2,n!+3......n!+n are good You have misunderstood the problem.
20.04.2018 18:01
Etemadi wrote: Smita wrote: I think so that n!+1,n!+2,n!+3......n!+n are good You have misunderstood the problem. Can u pls then explain.pls????
20.04.2018 18:23
Smita wrote: Etemadi wrote: Smita wrote: I think so that n!+1,n!+2,n!+3......n!+n are good You have misunderstood the problem. Can u pls then explain.pls???? $$\sum a_i=\sum _{1\le i < j\le n}\gcd (a_i,a_j) $$
20.04.2018 23:49
$\left(1, \: 2, \: 2^2, \: \dots, \: 2^{n - 2}, \: n - 2\right)$ works for every $n > 4$ divisible by $4$.
21.04.2018 05:49
Thanks etamadi
21.04.2018 15:01
Consider $\left(1, \: 2, \: 2^2, \: \dots, \: 2^{n - 2}, \: n - 2\right)$ for every $n > 4$ which is divisible by $4$. Thus we also have $$\sum a_i=\sum _{1\le i < j\le n}\gcd (a_i,a_j)=2^{n-1}+n-3$$ This concludes the proof $\blacksquare$
21.04.2018 18:39
$2^{a},2^{a+1}$ together with $(3\times 2^a-3a-4)\times 2^i$ for $i=0,1,2,...,2^a-1$ also work for all odd integer $a>1$.
22.04.2018 14:33
$(1,2,2^2,...2^n,2^{2k+1}(2^{2k+2}-2k-1))$ with $n=2^{2k+2}-2$ also works.
11.05.2018 15:25
It seems that the answers are similar,if we change 2 to 4t then it works when t is odd for 1,4t,4,8,2^n-1