There are $2025$ positive integers $a_1, a_2, \cdots, a_{2025}$ are placed around a circle. For any $k = 1, 2, \cdots, 2025$, $a_k \mid a_{k-1} + a_{k+1}$ where indices are considered modulo $n$. Prove that there exists a positive integer $N$ such that satisfies the following condition. (Condition) For any positive integer $n > N$, when $a_1 = n^n$, $a_1, a_2, \cdots, a_{2025}$ are all multiples of $n$.
Problem
Source: 2025 Korea Winter Program Practice Test P7
Tags: number theory, abstract algebra
Supercali
19.01.2025 18:52
Such arrangements are very interesting. To solve this problem we need a new property of these arrangements. Lemma: Define a sequence $T(3),T(4), \dots$ by $T(2)=2$ and $T(k+1)=(2T(k))!$ for all $k \geq 2$. For $m \geq 2$, let $a_1,a_2, \dots, a_m$ be positive integers arranged on a circle such that $a_i \mid a_{i-1}+a_{i+1}$ for all $i$. Then $a_i \mid T(m) a_{i \pm 1}$ for all $i$. (Indices modulo $m$ in both cases). Proof: We will use induction. For $m=2$ the given conditions imply $a_1 \mid 2a_2$ and $a_2 \mid 2a_1$, so $T(2)=2$ works. Now assume the statement is true up to $m-1 \geq 2$. Let $a_1,a_2, \dots, a_m$ be the given arrangement. Suppose $a_i=\max\{a_1,a_2, \dots, a_m\}$. If $a_i=a_{i+1}$, then $a_{i+1} \mid a_i + a_{i+2}$ $\implies$ $a_{i+1}|a_{i+2}$ $\implies$ $a_{i+2}=a_{i+1}$ because of maximality. Thus, propagating this, all the $a_i$ are equal, so the divisibility is trivially satisfied. Now assume $a_i>a_{i+1}$, and similarly $a_i>a_{i-1}$. Then, $a_i \mid a_{i-1}+a_{i+1} < 2a_i$ $\implies$ $a_i=a_{i-1}+a_{i+1}$. Now, delete $a_i$ from the circle. Then, $a_{i-1} \mid a_i+a_{i-2}=a_{i-1}+a_{i+1}+a_{i-2}$ $\implies$ $a_{i-1} \mid a_{i+1}+a_{i-2}$, and similarly $a_{i-1} \mid a_{i-1}+a_{i+2}$. Thus this new arrangement of $m-1$ numbers also satisfies the condition. Hence $a_j \mid T(m-1) a_{j+1} \mid T(m)a_{j+1}$ for all $j \neq i,i-1$ and $a_j \mid T(m-1) a_{j-1} \mid T(m)a_{j-1}$ for all $j \neq i,i+1$. Further, $a_{i \pm 1} \mid T(m-1) a_{i \mp 1}$. In particular, $$a_{i \pm 1} \mid T(m-1)(a_{i \pm 1} + a_{i \mp 1}) = T(m-1)a_i \mid T(m)a_i.$$Hence it is enough to prove that $a_i \mid T(m)a_{i \pm 1}$. Let $a_{i-1}=db$ and $a_{i+1}=dc$ where $d$ is their $\gcd$ and $b,c$ are coprime. So $db \mid T(m-1)dc$ $\implies$ $b \mid T(m-1)c$ $\implies$ $b \mid T(m-1)$ since $b,c$ are coprime. Similarly $c \mid T(m-1)$. Hence, $b+c \leq 2T(m-1)$ $\implies$ $b+c \mid (2T(m-1))!=T(m)$. Therefore, $$a_i=db+dc \mid T(m)d \mid T(m) a_{i \pm 1},$$which completes the induction. $\blacksquare$ Now we come back to the main problem. We claim that $N=2024T(2025)+1$ works. Indeed, suppose $n>N$, and the $a_i$ are arranged as in the question with $a_1=n^n$. The above lemma implies $a_1 \mid T(2025)^{k-1} a_k \mid T(2025)^{2024} a_k$ for all $k=1,2,3, \dots, 2025$. Now for any prime $p \mid n$, $$nv_p(n)=v_p(a_1) \leq 2024v_p(T(2025))+v_p(a_k),$$and so $$v_p(a_k)=v_p(n)+(n-1)v_p(n)-2024v_p(T(2025)) \geq v_p(n)+n-1-2024v_p(T(2025)) > v_p(n),$$where the last inequality holds because $n>N=1+2024T(2025) \geq 1+2024v_p(T(2025))$. Since this holds for all $p \mid n$, we get $n \mid a_k$ for all $k$, as required.
Acorn-SJ
19.01.2025 18:55
Call such arrangements with $m(\ge 3)$ positive integers “$m$-reengs”. Call a reeng ‘monic’ if gcd of all elements of that reeng is $1$.
Step 1) There are exactly three monic $3$-reengs, namely $(1,1,1),\,(1,1,2),\,(1,2,3).$
Step 2) If the gcd of some two adjacent elements of a reeng is $d$, then $d$ is a divisor of all elements of that ring. Also, dividing all elements of a reeng by the common gcd of all elements results in a monic reeng.
Step 3) Removing a maximal element from a $m$-reeng produces a $m-1$ reeng. If the original reeng was monic, then so is the new one. Use the result of Step 2 to simplify the proof.
Step 4) The maximum element of a monic $m$-reeng is bounded for a fixed $m$. To prove this use the result of Step 1 and 3 appropriately.
Step 5) Use induction to prove that the problem statement holds for general $m$-reengs. (The problem becomes the case when $m=2025.$) Base case $m=3$ is proved using the result of Step 1 and 2.
Inducting can be done as follows: first, if $n^n$ is not the maximal value of the reeng, deleting the maximal value will not remove it from the reeng. Then we get a reeng with one less element that contains $n^n$, so apply induction hypothesis.
If $n^n$ is the maximal value of the reeng, the gcd of all elements $d$ must be multiple of $n$, finishing the induction. For if it were not true, then $frac{n^n}{d}$ would be the maximal value of a monic reeng which is impossible when $n$ gets sufficiently large.