Prove that for any positive real number $\lambda$,there are $n$ positive numbers $a_1,a_2,\cdots,a_n(n\geq 2)$,so that $a_1<a_2<\cdots<a_n<2^n\lambda$ and for any $k=1,2,\cdots,n$ we have \[\gcd(a_1,a_k)+\gcd(a_2,a_k)+\cdots+\gcd(a_n,a_k)\equiv 0\pmod{a_k}\]
Problem
Source: 2022 China Southeast Grade 11 P7
Tags: number theory
Justanaccount
03.08.2022 08:47
Does $n$ depend on $\lambda$?
MathLover_ZJ
03.08.2022 08:49
Justanaccount wrote: Does $n$ depend on $\lambda$? Yes.
Thomas.L
03.08.2022 09:40
I think this question needs a clever construction
CANBANKAN
05.08.2022 05:29
We first talk about motivation. We note that the sequence $a_1=a_2=1, a_j=2^{j-2}$ satisfies the sum condition and achieves a $\lambda=\frac 14 + \epsilon$. To generalize, the idea is to have more "non-power-of-two" odd terms that are pairwise coprime. To do this, we can put $x_1, \cdots, x_{2^a}$ coprime odd, then add $2^a, 2^{a+1}, \cdots, 2^{n-2^a+a-1}$, which has a total of $2^a + (n-2^a+a-1) - a+1=n$ terms. Setting $n=1+\prod\limits_{j=1}^{2^a} x_j$ works because the sum of gcd's with an odd number is this odd number plus $n-1$ 1's, and $n-1$ is a multiple of that odd number. For $2^t$, we can see we need to sum $2^a$ 1's, $2^a, 2^{a+1}, \cdots$. The largest term is obviously $2^{n-2^a+a-1}$. This works for all $\lambda > 2^{a-2^a-1}$.
Justanaccount
05.08.2022 06:49
I found the answer by looking at $n=4$ and $a_1=1,a_2=2,a_3=3,a_4=4$, this specific case give us the motivation, too. We need a lot of powers of 2, but not all. Now look at $a_k$, if it is odd, then the powers of 2 give gcd equal to 1, and looking at n=4, we will just choose everything coprime to $a_k$, and looking at the powers of 2 tell us that the number of odd integers should be a power of 2, too. The rest is easy.
nEpg
08.08.2022 04:28
My solution during the test:
Let $t$ satisfying $2^{t-2^t}<\lambda $
Then let $p_1,p_2 \cdots p_{2^t-1}$ be different prime numbers.($p_{2^t-1}$ is the largest)
Then let $n=kp_1p_2\cdots p_{2^t-1}+1$,and $k$ is large enough to satisfy that $2^{n-2^t+t}>p_{2^t-1}$.
Let $A=\{1,p_1,p_2,\cdots p_{2^t-1}\}$ and $B=\{2^t,2^{t+1},\cdots 2^{n-2^t+t-1} \}$ ,then we can know that $|A\cup B|=n$.
Let $\{a_1,a_2,\cdots a_n\}=A\cup B$,we prove $a_1,a_2,\cdots a_n$ satisfying the condition.
For $a_i \in A$,notice that $a_i | n-1$,and for $j\neq i$, $gcd(a_i,a_j)=1$,so $a_i$ satisfies the condition.
For $a_i \in B$,let $a_i=2^s$ ,we know that for $a_j\in A$,$gcd(a_i,a_j)=1$,and for $a_j\in B$,we can know when$j>i$,$gcd(a_i,a_j)=a_i$ ,and when $j<i$,$gcd(a_i,a_j)=a_j$
Then $\gcd(a_1,a_i)+\gcd(a_2,a_i)+\cdots+\gcd(a_n,a_i)\equiv 2^t+2^t+2^{t+1}+\cdots +2^{s-1}\equiv 0\pmod{a_i}\ $.
And we have $a_n=2^{n-2^t+t}<\lambda 2^n $.
Then we are done.