Let $n>1$ be an integer. Prove that there exists an integer $n-1 \ge m \ge \left \lfloor \frac{n}{2} \right \rfloor$ such that the following equation has integer solutions with $a_m>0:$ $$\frac{a_{m}}{m+1}+\frac{a_{m+1}}{m+2}+ \cdots + \frac{a_{n-1}}{n}=\frac{1}{\textrm{lcm}\left ( 1,2, \cdots , n \right )}$$ Proposed by Navid Safaei
Problem
Source: 2017 Iran TST third exam day1 p1
Tags: number theory, Iran, Iranian TST
26.04.2017 19:16
Notice that $\textrm{lcm}(1,2,...,n)=\textrm{lcm}(\left \lfloor \frac{n}{2} \right \rfloor+1,\left \lfloor \frac{n}{2}\right \rfloor+2,..,n)$ since every positive integer $k\leq \left \lfloor \frac{n}{2} \right \rfloor$ has a multiple in the interval $[\left \lfloor \frac{n}{2} \right \rfloor+1,n]$.
We will prove that any $m$ that satisfies $\textrm{lcm}(m+1,m+2,...,n)=\textrm{lcm}(1,2,...,n)$ will work, in particular $m=\left \lfloor \frac{n}{2} \right \rfloor$. Let $N=\textrm{lcm}(1,2,...,n)$. Since $\gcd(\frac{N}{m+1},\frac{N}{m+2},...,\frac{N}{n})=1$, there are $x_{m+1},...,x_{n-1}$ such that $\frac{N}{m+1}a_{m+1}+\frac{N}{m+2}a_{m+2}+...+\frac{N}{n}a_{n-1}=1$. Choose an integer $t$ large enough so that $x_{m+1}+t\frac{N}{m+2}>0$. Let $$a_{m+1}=x_{m+1}+t\frac{N}{m+2}$$$$a_{m+2}=x_{m+2}-t\frac{N}{m+1}$$$$a_i=x_i \quad \forall m+3\leq i\leq n-1$$We clearly have $\frac{a_m}{m+1}+....+\frac{a_{n-1}}{n}=\frac{1}{\textrm{lcm}(1,2,...,n)}$.
21.02.2022 19:49
My solution Let's prove the claim by induction on $n$ +) For $n=2$, we have $1 = \lfloor \frac{2}{2} \rfloor \le m \le 2-1 =1 $ then $m=1$ It's easy to see that with $a_1=1$, we have $$ \frac{a_1}{1+1}=\frac{1}{2} = \frac{1}{ \textrm{lcm}(1,2)}$$ +) Now suppose that the claim is true with all $k \le n$, we want to prove that for $k=n+1$, the claim is still right Note that for $k=n$, by the induction claim, there exists $m \in [ \lfloor \frac{n}{2} \rfloor, n-1 ]$ such that there exists $(a_m,a_{m+1},a_{m+2}, \ldots , a_n )$ such that $$\frac{a_{m}}{m+1}+\frac{a_{m+1}}{m+2}+ \cdots + \frac{a_{n-1}}{n}=\frac{1}{\textrm{lcm}\left ( 1,2, \cdots , n \right )}$$ Then by replacing $(a_{m+1},a_{m+2}, \ldots , a_{n-1})$ by $(a_m',a_{m+1}',a_{m+2}', \ldots , a_{n-1}') = (ka_{m+1},ka_{m+2}, \ldots, ka_{n-1})$ then $$\frac{a_{m}'}{m+1}+\frac{a_{m+1}'}{m+2}+ \cdots + \frac{a_{n-1}'}{n}=\frac{k}{\textrm{lcm}\left ( 1,2, \cdots , n \right )}$$ Then we need to prove that there exists $k>0$ and $m' \in [ \lfloor \frac{n+1}{2} \rfloor, n ]$ such that there exists $b_{m+1},b_{m+2}, \ldots , b_{n+1}$ such that $$\frac{b_{m'}}{m'+1}+\frac{b_{m'+1}}{m'+2}+ \cdots + \frac{b_{n}}{n+1}=\frac{1}{\textrm{lcm}\left ( 1,2, \cdots , n , n+1 \right )}$$ If $m \in [ \lfloor \frac{n+1}{2} \rfloor, n ]$ ($m$ from the induction of $k=n$), then Case 1: $n+1 \mid \textrm{lcm} \left ( 1,2, \cdots , n \right ) \implies \textrm{lcm} \left ( 1,2, \cdots , n \right ) = \left ( 1,2, \cdots , n, n+1 \right ) $ Now just choose $k=1$ and $a_n=0$, we complete the proof Case 2: $n+1 $ is not divided by $ \textrm{lcm} \left ( 1,2, \cdots , n \right )$ Let $p_1,p_2,p_3, \ldots , p_h$ be all the prime divisors of $n+1$, then we can bipartite these prime divisors into $2$ set $A,B$ such that \[\begin{array}{l} {v_{{p_i}}}(n + 1) = {v_{{p_i}}}({\rm{lcm}}\left( {1,2, \cdots ,n} \right)) \text{ for all } p_i \in A \\ \\ {v_{{p_j}}}(n + 1) = {v_{{p_i}}}({\rm{lcm}}\left( {1,2, \cdots ,n} \right)) + 1 \text{ for all } p_j \in B \end{array}\] Also note that since $n+1 $ is not divided by $ \textrm{lcm} \left ( 1,2, \cdots , n \right )$ , we have $|B| \ge 1$ Then \[\gcd (\frac{{{\rm{lcm}}\left( {1,2, \cdots ,n,n + 1} \right)}}{{{\rm{lcm}}\left( {1,2, \cdots ,n} \right)}},\frac{{{\rm{lcm}}\left( {1,2, \cdots ,n,n + 1} \right)}}{{{a_n}}}) = \gcd (\prod\limits_{{p_j} \in B} {{p_j}} ,\prod\limits_{p \notin (A \cup B)} {{p^{{v_p}({\rm{lcm}}\left( {1,2, \cdots ,n} \right))}}) = 1} \] Now by applying Bezout Theorem, there exists $(x,y)$ integer such that \[\frac{{{\rm{lcm}}\left( {1,2, \cdots ,n,n + 1} \right)}}{{{\rm{lcm}}\left( {1,2, \cdots ,n} \right)}}.x + \frac{{{\rm{lcm}}\left( {1,2, \cdots ,n,n + 1} \right)}}{{{a_n}}}.y = 1\] Now we just need to adjust $(x,y)$ such that $x>0$, but this can be done easily by replace $(x,y)$ as $(x+u,y-v)$ for $u$ sufficiently large such that $$ \frac{u}{v}= \frac{\textrm{lcm} \left ( 1,2, \cdots , n \right )}{n+1} $$ If $m \notin [ \lfloor \frac{n+1}{2} \rfloor, n ]$ ($m$ from the induction of $k=n$), this means $n$ is odd and $m = \lfloor \frac{n}{2} \rfloor$ Case 1: $n+1 \mid \textrm{lcm} \left ( 1,2, \cdots , n \right ) \implies \textrm{lcm} \left ( 1,2, \cdots , n \right ) = \left ( 1,2, \cdots , n, n+1 \right ) $ Now just choose $k$ such that $k \cdot a_{m+1} >0$ and $a_n+2ka_m= 1-k$ then we have \[\frac{k}{{{\rm{lcm}}\left( {1,2, \cdots ,n} \right)}} + \frac{{1 - k-2ka_m}}{{n + 1}} = \frac{1}{{{\rm{lcm}}\left( {1,2, \cdots ,n + 1} \right)}} = \frac{{k{a_{m + 1}}}}{{m + 2}} + \frac{{k{a_{m + 2}}}}{{m + 3}} + ... + \frac{{k{a_{n - 1}}}}{n} + \frac{{1 - k}}{{n + 1}}\] Case 2: $n+1 $ is not divided by $ \textrm{lcm} \left ( 1,2, \cdots , n \right )$ Then similar to the above, we can always find a pair $(x,y)$ by Bezout Theorem such that \[\frac{{{\rm{lcm}}\left( {1,2, \cdots ,n,n + 1} \right)}}{{{\rm{lcm}}\left( {1,2, \cdots ,n} \right)}}.x + \frac{{{\rm{lcm}}\left( {1,2, \cdots ,n,n + 1} \right)}}{{{a_n}}}.y = 1\] Now to finish the proof, we just need to adjust $x$ such that $x \cdot a_{m+1} > 0$ (But this also be done similarly as: If $a_{m+1}<0$ then replace $(x,y)$ as $(x-u,y+v)$ and if $a_{m+1}>0$ then replace $(x,y)$ as $(x+u,y-v)$ for a sufficiently large $u$ such that $\frac{u}{v}= \frac{\textrm{lcm} \left ( 1,2, \cdots , n \right )}{n+1} )$ So we finish the proof now!!!