Let $m,n\ge 2$ be given integers. Prove that there exist positive integers $a_1<a_2<\ldots<a_m$ so that for any $1\le i<j\le m$ the number $\frac{a_j}{a_j-a_i}$ is an integer divisible by $n$.
Problem
Source: Poland 73-3-2
Tags: number theory
01.04.2022 02:18
This problem was proposed by Burii.
17.04.2022 15:46
Let $a_i\in\mathbb{Z}$ rather than $\mathbb{N}$. Call, Diviseq, a sequence that satisfies the conditions of the problem. We proceed by induction on $m$.
16.05.2022 17:57
Amazing problem! We proceed by induction on $m$. For $m=2$, we may take $a_1=n-1,a_2=n$, which clearly works. Now, suppose that the problem holds for $m$. Then, there exists a sequence $a_1<a_2<...<a_m$ of positive integers such that $n| \frac{a_j}{a_j-a_i}$ for all $1 \leq i < j \leq m$. Let $L=\operatorname{lcm}{(a_1,a_2,...,a_m)}=p_1^{e_1}p_2^{e_2}...p_l^{e_l}$. By inductive hypothesis, we know that $n|L$. Consider the polynomial $F(X)=(X-a_1)(X-a_2)...(X-a_m)$. Let $S=\{q_1,q_2,...,q_k\}$ be the set of all primes less than $a_m$ such that $q_j \not | L$. Observe that $q> \binom {m}{2}$ for all $q \in S$, because otherwise there would be $a_{i_1} \equiv a_{i_2} \pmod{q} \implies q_j| a_{i_1}-a_{i_2}| a_{i_1}$, a contradiction. Hence, by Lagrange's Theorem, $F(X) \equiv 0 \pmod{q}$ has at most $degF=m$ solutions $\pmod{q}$ for each $q \in S$. Since $\binom{m}{2} > m$ for $m \geq 3$, we have that for each $1 \leq j \leq k$, there exists an $r_j$ such that $F(r_j) \not \equiv 0 \pmod{q_j}$. Now, by CRT, choose $a_{m+1}$ such that $$a_{m+1} \equiv p_i^{e_i+N} \pmod{p_i^{e_i+N+1}},\\ a_{m+1} \equiv r_j \pmod{q_j}$$for a suitable choice of $N$. Observe that picking $N$ large enough, $\nu_{p_i}(a_{m+1})=e_i+N$, so $\nu_{p_i}(a_{m+1}-a_j)=\nu_{p_i}(a_j) \implies \nu_{p_i}(a_{m+1})=e_i+N > \nu_{p_i}(a_{m+1}-a_j)$. Moreover, $F(a_{m+1})=(a_{m+1}-a_1)(a_{m+1}-a_2)...(a_{m+1}-a_m) \not \equiv 0 \pmod{q_j}$, so none of the $q \in S$ divide $a_{m+1}-a_i$ and they do not divide any $a_i$ with $1 \leq i \leq m$. Therefore, $\frac{a_i}{a_{m+1}-a_i}$ is an integer, so $\frac{a_{m+1}}{a_{m+1}-a_i}$ is also an integer. Since $n | L$, by picking $N$ large enough, we assure that $n$ divides $\frac{a_{m+1}}{a_{m+1}-a_i}$, so we are done. $\blacksquare$
19.10.2022 18:01
Didn't solve the problem yet, but solve the case where $n=1$. I'm just saving my partial solution here for now. We prove by induction in $m$. Suppose we have $(a_2,a_3,\dots,a_{m})$ such that, for $2\leq i<j\leq m$, we have $$a_j-a_i\mid a_j.$$Let $P=\prod_{j>i}(a_j-a_i)$ and $R=\prod_{i\geq2}a_i$. See that, if we sum $R$ to every $a_i$ the condition is preserved. By mapping $a_i\to a_i+RP$ for $2\leq i\leq m$ and taking $a_1=RP$ we get a solution for $m$. I'm still trying to generalize this solution for a generic $n$
09.01.2023 14:53
Solved with Krutarth Shah and Malay Mahajan. We do it by induction on $m$, for $m = 2$ anything satisfying $n(a_2 - a_1) \mid a_2$ works, so $a_1 = nk-k$ and $a_2 = nk$ works for any $k$. Now, note that if $L$ is the lcm of all numbers of the form $a_j - a_i$ with $j > i$, then shifting all elements by $L$ also results in a valid sequence. To induct, add a $0$ to the sequence and shift to get all of them to be positive integers. The end. $\blacksquare$