Certain property of the least common multiple of three integers

Question

My problem seems elementary. However a post in SE has not got an answer.

Let $a_1,a_2,a_3\geq1$ be integers and let $A=\mathrm{lcm}(a_1,a_2,a_3)$ be their least common multiple. I want to show the following.

If $m_1,m_2,m_3\geq0$ are natural numbers satisfying $m_1a_1+m_2a_2+m_3a_3=2A$, then there exist integers $m_1',m_2',m_3'$ satifying $0\leq m_i'\leq m_i$ for each $i$ and $m_1'a_1+m_2'a_2+m_3'a_3=A$.

The motivation for this problem is the following problem I conjecture but can not prove either.

Let $\mathbb Q[x,y,z]$ be the polynomial ring of three variables. Let $a,b,c\geq1$ be the degrees of $x,y,z$ respectively. Let $A=\mathrm{lcm}(a,b,c)$. Then $\mathbb Q[x,y,z]_{(A)}:=\bigoplus_{d\geq0}\mathbb Q[x,y,z]_{Ad}$ is generated by $\mathbb Q[x,y,z]_A$. The subscript in $\mathbb Q[x,y,z]_A$ denotes the degree $A$ subspace, i.e. $\mathbb Q[x,y,z]_A=\mathrm{span}\big\{x^uy^vz^w:u,v,w\geq0,\;ua+vb+wc=A\big\}$.

The first statement will prove the second. Consider $x^uy^vz^w\in\mathbb Q[x,y,z]_{Ad}$ with $ua+vb+wc=Ad$.

• It suffices to show that there exist $\begin{cases}0\leq u'\leq u\\0\leq v'\leq v\\0\leq w'\leq w\end{cases}$ and $u'a+v'b+w'c=A$. This is because we then have $x^uy^vz^w=\big(x^{u'}y^{v'}z^{w'}\big)\big(x^{u-u'}y^{v-v'}z^{w-w'}\big)\in\mathbb Q[x,y,z]_A\cdot\mathbb Q[x,y,z]_{A(d-1)}$, and we reduce $d$ to $d-1$.
• Also if $ua\geq A$ (or $vb\geq A$ or $wc\geq A$), we just take $\begin{cases}u'=A/a\\v'=0\\w'=0\end{cases}$ as a solution.
• So the difficult situation is when $\begin{cases}0\leq u<A/a\\0\leq v<A/b\\0\leq w<A/c\end{cases}$. In this case $dA=ua+vb+wc<3A$, so $d<3$. This reduces to the $d=2$ case, which is the first statement.

Thanks for any comments.

Answer 1

1. Without loss of generality $d:=\gcd(a_1,a_2,a_2)=1$, else divide $a_1,a_2,a_3$ and $A$ by $d$.

2. Denote $d_{ij}=\gcd(a_i,a_j)$. Now $d_{12}, d_{13},d_{23}$ are mutually coprime, we may write $a_1=d_{12}d_{13}b_1$ etc, $A=d_{12}d_{13}d_{23}b_1b_2b_3$, $m_1$ must be divisible by $d_{23}$ etc, say $m_1=n_1d_{23}$ and we get $n_1b_1+n_2b_2+n_3b_3=2b_1b_2b_3$ for mutually coprime $b_1$, $b_2$, $b_3$.

3. Assume the contrary. Denote $n_1=k_1b_2+r_1$ where $0\leqslant r_1<b_2$, $n_2=k_2b_1+r_2$ where $0\leqslant r_2<b_1$. Note that all numbers divisible by $b_1b_2$ and not exceeding $(k_1+k_2)b_1b_2$ are represented in the necessary form $t_1b_1+t_2b_2+t_3b_3$, $0\leqslant t_i\leqslant n_i$. Thus, assuming the contrary, we get $k_1+k_2\leqslant b_3-1$, and $$n_1b_1+n_2b_2\leqslant (k_1+k_2)b_1b_2+(b_2-1)b_1+(b_1-1)b_2\\ \leqslant (b_3-1)b_1b_2+(b_2-1)b_1+(b_1-1)b_2.$$ Summing up three such bounds we get $$4b_1b_2b_3=2(n_1b_1+n_2b_2+n_3b_3)\leqslant 3b_1b_2b_3+b_1b_2+b_1b_3+b_2b_3-2b_1-2b_2-2b_3,$$ and $$(b_1-1)(b_2-1)(b_3-1)<0,$$ a contradiction.

Answer 2

Although Fedor has beaten me to it, let me also sketch my proof. I've renamed $A$ to $n$.

1. This is the same, we can assume $gcd(a_1,a_2,a_3)=1$.

2. Assume that some prime $p$ divides $a_1$ and $a_2$ but not $a_3$.
   As $p$ also divides $n$, it divides $2n$, so also $m_3a_3$, thus $m_3$.
   Then $m_1\frac{a_1}p+m_2\frac{a_2}p+\frac{m_3}pa_3=2\frac np$.
   Using induction on your favorite parameter we can find $m_1',m_2',m_3'$ such that
   $m_1'\frac{a_1}p+m_2'\frac{a_2}p+m_3'a_3=2\frac np$ where $m_3'\le \frac{m_3}p$.
   But then $m_1'a_1+m_2'a_2+pm_3'a_3=2n$ is a good solution.
   Therefore $gcd(a_1,a_2)=1$, and similarly we can conclude that all the $a_i$'s are pairwise relative primes.

3. Wlog. $m_1a_1\ge \frac 23 n$ and $m_2a_2\ge \frac 12 n$ (as $m_1a_1<n$).
   If $lcm(a_1,a_2)=\frac nk<n$, then we can find $m_1',m_2'$ such that $m_1'a_1+m_2'a_2=n$.
   If $k$ is even, we can pick $m_1'a_1=m_2'a_2=\frac 12 n$.
   If $k=2l+1$, we can pick $m_1'a_1=\frac{l+1}{2l+1}n\le \frac 23 n$ and $m_2'a_2=\frac{l}{2l+1}n\le \frac 12 n$.
   Therefore $lcd(a_1,a_2)=n$, which implies $a_3=1$.
   In this case we can pick $m_1'=0$, or $m_2'=0$, and $m_3'$ appropriately.