# Certain property of the least common multiple of three integers

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. In this case $$dA=ua+vb+wc<3A$$, so $$d<3$$. This reduces to the $$d=2$$ case, which is the first statement.

• It may be true for triples, but it's not true for $4$-tuples, as one can see at math.stackexchange.com/questions/547634/… Nov 17, 2021 at 12:12
• You have two good answers to your question... you should select one (the older, if both equally good). Apr 13 at 16:45

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, $$n_2=k_2b_1+r_2$$ where $$0\leqslant r_2. 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.

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).
If $$lcm(a_1,a_2)=\frac nk, 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.