We know, If $(m_1,m_2)=(a,m_1)=(b,m_2)=1, \iff (am_2+bm_1, m_1m_2)=1$

I tried to generalize now.

Let $(a,m_1)=d_1, (b,m_2)=d_2$ where $d_1,d_2$ need not to be 1.

$(am_2+bm_1, m_1m_2)$

$=(am_2+bm_1, m_1)(am_2+bm_1, m_2)\ as\ (m_1,m_2)=1$

$=(am_2, m_1)(bm_1, m_2)$

$=(a, m_1)(b, m_2)\ as\ (m_1,m_2)=1$

So, $(am_2+bm_1, m_1m_2)=(a, m_1)(b, m_2)$

Now, I want to make $(m_1,m_2)=D$ where D is not necessarily 1.

Let $\frac{a}{A}=\frac{m_1}{M_1}=d_1$ and $\frac{b}{B}=\frac{m_2}{M_2}=d_2$,

so $(A,M_1)=1$ and $(B,M_2)=1$

$(am_2+bm_1, m_1m_2)=d_1.d_2(AM_2+BM_1, M_1M_2)=(a,m_1)(b,m_2)(AM_2+BM_1, M_1M_2)$

Now let $\frac{M_1}{M_{11}}=\frac{M_2}{M_{22}}=D_{12}$ i.e., $(M_1,M_2)=D_{12}$

so, $(M_{11},M_{22})=1$

then $(am_2+bm_1, m_1m_2)$

$=(a,m_1)(b,m_2)D_{12}(AM_{22}+BM_{11}, M_{11}M_{22}D_{12})$

$=(a,m_1)(b,m_2)(M_1,M_2)(AM_{22}+BM_{11}, M_{11}M_{22}D_{12})$

But, this $D_{12}$ is not necessarily co-prime with $M_{11}$ or $M_{22}$.

So, I could not proceed any further.

  • $\begingroup$ @RossMillikan, thanks for your observation, now it's rectified. $\endgroup$ – lab bhattacharjee Jul 29 '12 at 17:02

Part 1:

We have both $$ (am_2+bm_1,m_1m_2)=d_1d_2\,\left(\frac{a}{d_1}\!\!\frac{m_2}{d_2}+\frac{b}{d_2}\!\!\frac{m_1}{d_1} ,\frac{m_1}{d_1}\!\!\frac{m_2}{d_2}\right)\tag{1} $$ and $$ (am_2+bm_1,m_1m_2)=D\,\left(a\frac{m_2}{D}+b\frac{m_1}{D} ,m_1\frac{m_2}{D}\right)\tag{2} $$ Equations $(1)$ and $(2)$ show that $$ \mathrm{lcm}(d_1d_2,D)\,\vert\,(am_2+bm_1,m_1m_2)\tag{3} $$

Part 2:

Since $(m_1,m_2)=D$, let $$ m_1x+m_2y=D\tag{4} $$ Since $(a,m_1)=d_1$, let $$ au_1+m_1v_1=d_1\tag{5} $$ Since $(b,m_2)=d_2$, let $$ bu_2+m_2v_2=d_2\tag{6} $$ Now, $(4)$ and $(5)$ yield $$ \begin{align} (am_2+bm_1)y+m_1(ax-by)&=aD\\ (am_2+bm_1)u_1+m_1(m_2v_1-bu_1)&=m_2d_1 \end{align}\tag{7} $$ and $(4)$ and $(6)$ yield $$ \begin{align} (am_2+bm_1)x+m_2(by-ax)&=bD\\ (am_2+bm_1)u_2+m_2(m_1v_2-au_2)&=m_1d_2 \end{align}\tag{8} $$ Using $(7)$ and Bezout, we can write $$ (am_2+bm_1)w_1+m_1z_1=(aD,m_2d_1)\tag{9} $$ Using $(8)$ and Bezout, we can write $$ (am_2+bm_1)w_2+m_2z_2=(bD,m_1d_2)\tag{10} $$ Thus, taking the product of $(9)$ and $(10)$ yields $$ (am_2+bm_1)w+m_1m_2z_1z_2=(aD,m_2d_1)(bD,m_1d_2)\tag{11} $$ and therefore, $(11)$ and Bezout yield $$ (am_2+bm_1,m_1m_2)\,\vert\,(aD,m_2d_1)\,(bD,m_1d_2)=d_1d_2D^2\,\left(\frac{a}{d_1},\frac{m_2}{D}\right)\,\left(\frac{b}{d_2},\frac{m_1}{D}\right)\tag{12} $$


The best I have come up with so far is $$ \mathrm{lcm}(d_1d_2,D)\,\vert\,(am_2+bm_1,m_1m_2)\,\vert\,d_1d_2D^2\,\left(\frac{a}{d_1},\frac{m_2}{D}\right)\,\left(\frac{b}{d_2},\frac{m_1}{D}\right)\tag{13} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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