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.

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

2 Answers 2

  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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.